Description

在数轴上有一个点，开始在原点，它要到位置T， 有一个操作序列，第i个元素为 xi x i ，每次它会判断，如果它走了 xi x i 个单位距离会离T更近，那么它就会走，否则原地不动（走动不限方向，可能走过T再走回来） 有m个询问，每次问是否存在一个y，使得如果把操作序列的第i个更改成y，从原点无法走到T。

Solution

考虑暴力怎么做，对于每个点维护一个bool数组，表示当前如果在哪些位置就可以到达T， 进一步发现，其实没有必要维护全部，直接记录离T最近的，无法达到T的位置即可， 因为你的策略是如果能更近就走，所以相当于把数组的某一段复制以后强行覆盖到另一段上， 如：当前要走x步，先把数组对称过去，复制数组的x~(T+x/2)位，强行覆盖到1~(T-x/2)位上，

所以对于每个操作i，离T最近的，无法达到T的位置（设为 fi f i ）一定是单调的，计算方式也简单：

f[i]=f[i+1]-((T-f[i+1])*2+1>=x[i]?x[i]:0);

Code

#include <cstdio> #include <cstdlib> #define fo(i,a,b) for(int i=a;i<=b;i++) #define fod(i,a,b) for(int i=a;i>=b;i--) #define min(q,w) ((q)>(w)?(w):(q)) #define abs(q) ((q)<0?-(q):(q)) using namespace std; const int N=500500; int read(int &n) { char ch=' ';int q=0,w=1; for(;(ch!='-')&&((ch<'0')||(ch>'9'));ch=getchar()); if(ch=='-')w=-1,ch=getchar(); for(;ch>='0' && ch<='9';ch=getchar())q=q*10+ch-48;n=q*w;return n; } int m,n,ans; int f[N],a[N],c[N]; int main() { int q,w; read(n),read(m); c[0]=m; fo(i,1,n)read(a[i]),c[i]=min(c[i-1],abs(c[i-1]-a[i])); f[n+1]=0; fod(i,n,1)f[i]=f[i+1]+(f[i+1]*2+1>=a[i]?a[i]:0); read(m); fo(i,1,m) { read(q); if(c[q-1]>f[q+1])printf("YES\n");else printf("NO\n"); } return 0; }