[AT2401] [arc072_e] Alice in linear land

题目链接

AtCoder:https://arc072.contest.atcoder.jp/tasks/arc072_c

洛谷:https://www.luogu.org/problemnew/show/AT2401

Solution

很巧妙的题。

我们考虑从后往前推,设\(b[i]\)表示\(i\sim n\)一定可以到达目的地的点的\(mex-1\),也就是\(0\sim b[i]\)都必然可以到目的地,假设其他的所有点都可以通过某种方式修改\(a[i-1]\)使之不可行。

设当前\(dp​\)到\(i​\),\(i​\)的移动距离为\(a[i]​\),画个图可以知道\((b[i+1],\lfloor\frac{a[i]}{2}\rfloor]​\)这个区间是不能到达目的地的,其余所有在\([0,b[i+1]+a[i]]​\)的位置都可以到。

所以我们只需要判一下上面那个区间存不存在就好了,然后直接转移\(b[i]​\),复杂度\(O(n)​\)。

#include<bits/stdc++.h>
using namespace std; #define int long long void read(int &x) {
x=0;int f=1;char ch=getchar();
for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-f;
for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0';x*=f;
} void print(int x) {
if(x<0) putchar('-'),x=-x;
if(!x) return ;print(x/10),putchar(x%10+48);
}
void write(int x) {if(!x) putchar('0');else print(x);putchar('\n');} #define lf double
#define ll long long #define pii pair<int,int >
#define vec vector<int > #define pb push_back
#define mp make_pair
#define fr first
#define sc second const int maxn = 5e5+10;
const int inf = 1e9;
const lf eps = 1e-8; int n,q,d,a[maxn],b[maxn],dis[maxn]; signed main() {
read(n),read(d);dis[0]=d;
for(int i=1;i<=n;i++) read(a[i]),dis[i]=min(dis[i-1],abs(dis[i-1]-a[i]));
for(int i=n;i;i--) b[i]=b[i+1]+a[i]*(a[i]/2<=b[i+1]);read(q);
for(int i=1,x;i<=q;i++) read(x),puts(dis[x-1]>b[x+1]?"YES":"NO");
return 0;
}
上一篇:SKSpriteNode对象初始化在iPhone 6 plus中显示不正确的分析及解决


下一篇:LoadRunner的简单使用《第一篇》