【ARC072E】Alice in linear land DP

时间:2023-02-04 09:08:06

题目大意

  有一个人要去直线上\(lm\)远处的地方,他会依次给他的机器发出\(n\)个指令。第\(i\)个指令为\(d_i\)。他的机器收到一个指令\(x\)后,如果向目的地方向前进\(xm\)后比当前离目的地更近,就会向前移动\(xm\),否则什么都不会做。

  现在,给你\(q\)个询问,第\(i\)个询问为\(a_i\),问你能不能改变\(d_{a_i}\),使得这个人不能到达目的地。你可以决定把\(d_{a_i}\)改成什么数。

  \(n,q\leq 500000,1\leq d_i\leq {10}^9\)

题解

  首先我们先算出执行前面\(i\)个指令后离终点的距离\(c_i\)

  暴力的做法是用DP算出\(g_{i,j}\):执行后面\(i\)~\(n\)的指令,离终点的距离为\(j\),执行完后能不能到达终点。

  然后就会发现一旦出现一个\(0\),后面的\(1\)就会无意义。(因为可以修改成直接走到\(0\)这里)

  那么我们只需要维护前面有多少个\(1\)。

  \(f_i\)表示执行后面\(i\)$n$的指令,前面$g_{i,0}$\(g_{0,f_i}\)全部是\(1\),\(g_{i,f_i+1}\)是\(0\)。

  那么如果\(d_i\leq 2f_{i+1}+1\),那么\(f_i=f_{i+1}+d_i\)。否则\(f_i=f_{i+1}\)。

  可以发现,第一种情况\(0\)~\(f_i\)之间不会有空洞。

  询问\(a_i\)时直接判断\(c_{a_i-1}\)是不是比\(f_{a_i+1}\)大。这样直接走到\(f_{a_i+1}+1\)就可以了。

  时间复杂度:\(O(n)\)

代码

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<ctime>
#include<utility>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
int n,q;
ll m;
ll d[500010];
ll c[500010];
ll f[500010];
void rd(int &s)
{
int c;
while((c=getchar())<'0'||c>'9');
s=c-'0';
while((c=getchar())>='0'&&c<='9')
s=s*10+c-'0';
}
void rd(ll &s)
{
int c;
while((c=getchar())<'0'||c>'9');
s=c-'0';
while((c=getchar())>='0'&&c<='9')
s=s*10+c-'0';
}
int abs(int x)
{
return x>0?x:-x;
}
void yes()
{
putchar('Y');
putchar('E');
putchar('S');
putchar('\n');
}
void no()
{
putchar('N');
putchar('O');
putchar('\n');
}
int main()
{
#ifdef DEBUG
freopen("a.in","r",stdin);
freopen("a.out","w",stdout);
#endif
scanf("%d%lld",&n,&m);
int i;
ll x;
c[0]=m;
for(i=1;i<=n;i++)
{
rd(d[i]);
c[i]=min(c[i-1],abs(c[i-1]-d[i]));
}
f[n+1]=0;
for(i=n;i>=1;i--)
{
f[i]=f[i+1];
if(d[i]<=2*f[i+1]+1)
f[i]=max(f[i],f[i+1]+d[i]);
}
scanf("%d",&q);
for(i=1;i<=q;i++)
{
rd(x);
if(c[x-1]>f[x+1])
yes();
else
no();
}
return 0;
}

【ARC072E】Alice in linear land DP的更多相关文章

  1. 【ARC072E】Alice in linear land

    题目 瑟瑟发抖,这竟然只是个蓝题 题意大概就是初始在\(0\),要到坐标为\(D\)的地方去,有\(n\)条指令,第\(i\)条为\(d_i\).当收到一条指令\(x\)后,如果向\(D\)方向走\( ...

  2. 【ARC072 E】Alice in linear land

    被智商题劝退,告辞 题意 有一个人在一条数轴的距离原点为 \(D\) 的位置,他可以执行 \(n\) 次操作,每次操作为给定一个整数 \(d_i\),这个人向原点的方向走 \(d_i\) 个单位,但如 ...

  3. 【BZOJ3291】Alice与能源计划 二分图最大匹配

    [BZOJ3291]Alice与能源计划 Description 在梦境中,Alice来到了火星.不知为何,转眼间Alice被任命为火星能源部长,并立刻面临着一个严峻的考验. 为了方便,我们可以将火星 ...

  4. 【线性代数】1-1&colon;线性组合&lpar;Linear Combinations&rpar;

    title: [线性代数]1-1:线性组合(Linear Combinations) toc: true categories: Mathematic Linear Algebra date: 201 ...

  5. 【题解】ARC101F Robots and Exits&lpar;DP转格路&plus;树状数组优化DP&rpar;

    [题解]ARC101F Robots and Exits(DP转格路+树状数组优化DP) 先删去所有只能进入一个洞的机器人,这对答案没有贡献 考虑一个机器人只能进入两个洞,且真正的限制条件是操作的前缀 ...

  6. 【BZOJ2073】&lbrack;POI2004&rsqb;PRZ 状压DP

    [BZOJ2073][POI2004]PRZ Description 一只队伍在爬山时碰到了雪崩,他们在逃跑时遇到了一座桥,他们要尽快的过桥. 桥已经很旧了, 所以它不能承受太重的东西. 任何时候队伍 ...

  7. 【CF506E】Mr&period; Kitayuta&&num;39&semi;s Gift dp转有限状态自动机&plus;矩阵乘法

    [CF506E]Mr. Kitayuta's Gift 题意:给你一个字符串s,你需要在s中插入n个字符(小写字母),每个字符可以被插在任意位置.问可以得到多少种本质不同的字符串,使得这个串是回文的. ...

  8. 【BZOJ1187】&lbrack;HNOI2007&rsqb;神奇游乐园 插头DP

    [BZOJ1187][HNOI2007]神奇游乐园 Description 经历了一段艰辛的旅程后,主人公小P乘坐飞艇返回.在返回的途中,小P发现在漫无边际的沙漠中,有一块狭长的绿地特别显眼.往下仔细 ...

  9. UOJ &num;17&period; 【NOIP2014】飞扬的小鸟 背包DP

    #17. [NOIP2014]飞扬的小鸟 Time Limit: 10 Sec  Memory Limit: 162 MBSubmit: 4902  Solved: 1879 题目连接 http:// ...

随机推荐

  1. json(http&colon;&sol;&sol;www&period;cnblogs&period;com&sol;lanxuezaipiao&sol;archive&sol;2013&sol;05&sol;24&sol;3096437&period;html)

    http://www.cnblogs.com/lanxuezaipiao/archive/2013/05/24/3096437.html

  2. LCS nlog&lpar;n&rpar; 但最坏情况还是比较悲剧 转载的文章;

    最长公共子序列问题: 给定2个字符串,求其最长公共子串.如abcde和dbada的最长公共字串为bd. 动态规划:dp[i][j]表示A串前i个和B串前j个的最长公共子串的长度. 则 若A[i] == ...

  3. MS-SQL索引类型

    一.索引的概念     索引就是加快检索表中数据的方法.数据库的索引类似于书籍的索引.在书籍中,索引允许用户不必翻阅完整个书就能迅速地找到所需要的信息.在数据库中,索引也允许数据库程序迅速地找到表中的 ...

  4. BZOJ1726&colon; &lbrack;Usaco2006 Nov&rsqb;Roadblocks第二短路

    1726: [Usaco2006 Nov]Roadblocks第二短路 Time Limit: 5 Sec  Memory Limit: 64 MBSubmit: 768  Solved: 369[S ...

  5. 读改善c&num;代码157个建议:建议10~12

    目录: 建议10:创建对象时需要考虑是否实现比较器 建议11:区别对待==与Equals 建议12:重写Equals时也要重写GetHashCode 一.建议10:创建对象时需要考虑是否实现比较器 比 ...

  6. python脚本文件删除

    昨天有需求需要用python脚本删除一个目录下的文件.遇到了点麻烦. 使用的是shutil.rmtree(dir)函数,这个函数可以删除有内容的目录,而shutil.rmdir(dir)只能删除空目录 ...

  7. swift 创建九宫格在后面加按钮

    项目中的需求是前面图片,在图片最后面始终有按钮如图 图片 let space:CGFloat = 10 for i in 0..model.count{ let itemWidth:CGFloat = ...

  8. Mysql&sol;Mariadb配置日志

    1. 创建日志存放目录: mkdir /var/log/mysql && chown mysql:mysql /var/log/mysql 2.修改Mysql配置日志: vi /etc ...

  9. CentOS 7 防火墙端口配置

    CentOS 7 防火墙端口配置查看防火墙是否开启systemctl status firewalld 若没有开启则开启systemctl start firewalld 查看所有开启的端口firew ...

  10. Spring Boot热部署(springloader)

    使用方式一 在pom.xml文件添加依赖包: <plugin> <groupId>org.springframework.boot</groupId> <ar ...