Alice and the Unfair Game(Div.2-E1236)(贪心，脑洞，Dp)

题目

CF

思路

我们首先可以发现一个贪心策略，假设我们从 $p$ 出发所能达到的最远处构成区间 $[L_p,R_p]$ 中每个点都可以到达。
比较好证明，假设到了 $i$ 点后如果下一次要查询 $i$ 就挪一挪，然后挪回来就行了。
那现在就是找每个点最左和最右就行了。
发现很难搞。。。
然后翻了翻别人的代码理解了很久发现可以这样做
我们处理出从每个位置出发被阻挡的次数(到最远端)
理解一下这段代码：

for(int i=m;i>=1;i--)cnt[a[i]-i]=cnt[a[i]-i-1]+1;

$cnt[a[i]?i]$ : 0 时刻从 $a[i]?i$ 出发(只出现 $[i,m]$ 时刻的障碍物)被阻碍次数
非常抽象。。。

我们发现 $cn{t}^{\prime }[a[i]?i]$ ( $i+1$ 时刻的 $cnt$ ) 对于 $cnt[a[i]?i]$ 已经没有用了，因为会被阻挡使得之后你到达被阻挡的地方的时间减小，也就是不会被阻挡了，于是我们需要用到 $a_i?i?1$ 的信息更新它，又因为这个点本身会被阻挡，在 $i$ 时刻会到 $a_i?1$ ，
可以理解为两个点的信息在 $a_i?1$ 完成了一次传递（好吧我讲的不好，你可以再看看别人的）
注意这里 $a_i?i?1$ 并不需要考虑边界问题，$a_i?i?1$ 的存在是一种假设
知道阻挡数后由于最多只会走 $m+1$ 步，进而可以确定每个数最左和最右，问题得到解决。

代码

#include<set>
#include<map>
#include<stack>
#include<ctime>
#include<cmath>
#include<queue>
#include<cstdio>
#include<vector>
#include<climits>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define LL long long
using namespace std;
int read(){
    bool f=0;int x=0;char c=getchar();while(c<'0'||'9'<c){
    if(c=='-')f=1;c=getchar();}while('0'<=c&&c<='9') x=(x<<3)+(x<<1)+(c^48),c=getchar();return !f?x:-x;
}
#define MAXN 100000
#define INF 0x3f3f3f3f
map<int,int> cnt;
int a[MAXN+5],L[MAXN+5],R[MAXN+5];
int main(){
    int n=read(),m=read();for(int i=1;i<=m;i++)a[i]=read();if(n==1){
    puts("0");return 0;}for(int i=m;i>=1;i--)//cnt[a[i]-i]: 0 时刻从 a[i]-i 出发(只出现[i,m]时刻的障碍物)被阻碍次数cnt[a[i]-i]=cnt[a[i]-i-1]+1;for(int i=1;i<=n;i++)R[i]=min(i+m+1-cnt[i],n);cnt.clear();for(int i=m;i>=1;i--)cnt[a[i]+i]=cnt[a[i]+i+1]+1;for(int i=1;i<=n;i++)L[i]=max(i-m-1+cnt[i],1);LL ans=0;for(int i=1;i<=n;i++)ans+=R[i]-L[i]+1;printf("%lld\n",ans);return 0;
}

思考

遇到这种T神出的题，也只能给跪了