Codeforces 1236E. Alice and the Unfair Game

传送门

首先可以注意到对于固定的起点 $S$ ，它最终能走到的终点一定是一段区间

这个用反证法容易证明，假设合法区间存在断点，这个点左右都可以作为终点

那么分成区间断点在起点左边和起点右边讨论一下即可，起点本身显然一定可以作为终点

然后现在只要考虑从每个起点出发能走到的最左和最右的位置即可算出答案

首先考虑往右（以下为了方便把第 $i$ 次询问说成第 $i$ 天）

设起点为 $x$ 那么我们可以一直往右走直到遇到某一天刚好询问原本要走的下一个位置，那么此时就要停一次

设连续走了 $y$ 天遇到这个情况，那么有 $x+y=a[y]$ ，即 $x=a[y]-y$，然后等完一步以后我们就要找到下一个 $y$ 使得 $x+1+y=a[y]$

设 $f(x,y)$ 表示在第 $y$ 天从 $x$ 出发最右能到达的位置，那么只要求出 $f(x,y)$ 往右第一个停止位置那么就变成了位置更右，天数更大的的子问题

设 $z$ 为最小的满足 $x+z=a[y+z]$ 的数，那么转化一下等价于 $x-y=a[y+z]-(y+z)$

往右第一个停止位置显然是可以维护的，只要按时间倒过来一个个考虑，用一个 $map$ 维护一下当前时间往后最左的第一个 $a[i]-i$ 的询问

同时注意到只有当恰好在位置 $a[i]-1$，时间在 $i$ 时才会停止一次，那么我们想要知道的位置就只和询问时间有关，所以维护时间即可

那么总结一下就是按时间 $i$ 从大到小枚举，搞个 $map$ 维护一下当前最小的 $j>i$ 使得 $a[j]-j==(a[i]-1)-i$

然后就可以求出 $R[i]$ 表示往右走刚好在时间 $i$ 停止一天后继续走能走到的最右端（$R[i]=R[j]$,$j=map[(a[i]-1)-i]$，意思就是找到下一个停止的时间点转移）

当然如果 $map$ 里没有合法的 $j$ ，那么就说明不用停，走到时间结束即可

对于往左也是同样的做法，学着上面的思路自己推一下吧

事实上 $map$ 完全可以用桶替代，只要把下标集体加 $m$ 即可

代码参考： Farhod_Farmon

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cstring>

#include<cmath>

#include<map>

using namespace std;

typedef long long ll;

inline int read()

{

    int x=,f=; char ch=getchar();

    while(ch<''||ch>'') { if(ch=='-') f=-; ch=getchar(); }

    while(ch>=''&&ch<='') { x=(x<<)+(x<<)+(ch^); ch=getchar(); }

    return x*f;

}

const int N=1e5+;

int n,m,A[N],L[N],R[N];

map <int,int> ml,mr;

inline int find_r(int x,int i) { return mr[x-i] ? R[mr[x-i]] : min(x+(m-i)+,n); }

inline int find_l(int x,int i) { return ml[x+i] ? L[ml[x+i]] : max(x-(m-i)-,); }

int main()

{

    n=read(),m=read();

    for(int i=;i<=m;i++) A[i]=read();

    if(n==)  { printf("0\n"); return ; }

    for(int i=m;i>=;i--)

    {

        L[i]=find_l(A[i]+,i); R[i]=find_r(A[i]-,i);

        ml[A[i]+i]=i; mr[A[i]-i]=i;

    }

    ll ans=;

    for(int i=;i<=n;i++)

        ans+=find_r(i,)-i++i-find_l(i,);//中间那个+1是起点本身作为终点的贡献

    printf("%lld\n",ans);

    return ;

}

巴特西

Codeforces 1236E. Alice and the Unfair Game

最新文章

热门文章