[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;

}

巴特西

[AT2401] [arc072_e] Alice in linear land

题目链接

Solution

最新文章

热门文章