题解：CF1998D Determine Winning Islands in Race

· · 题解

有生之年第一次做到的水 D

我们不考虑 Bessie 怎么赢，反过来，我们来考虑 Elsie 在什么情况下会赢？

首先，如果 Elsie 跟着 Bessie 只走 "main bridge"，那么它是没有胜算的，这就是说它需要走一些 alternative bridge。

在什么情况下，Elsie 能通过走 alternative bridge 走到 Bessie 前面呢？这当然需要满足两个条件。

  1. Bessie 还没有走过这个 alternative bridge 的起点，也就是说这个起点还没有 Collapse。

  2. Bessie 还没有走过这个 alternative bridge 的终点，也就是说这个终点还没有 Collapse。

我们把两个条件同时考虑。

对于每一个岛（以下称作结点）i，如果 Bessie 选取这个结点为出发点，那么起点在点 i 后的 alternative bridge 全部是不能用，或者用不着的。为什么呢？

如果某一时刻 Elsie 走到了 Bessie 前面，说明 Bessie 已经不可能再超过 Elsie 了，那么其它 alternative bridge 就不用了。

反之，如果至始至终 Elsie 都没有走到 Bessie 前面，那么从 i 开始后面的结点由于被 Bessie 走过，都会 Collapse，这就是说 Elsie 不能用那些 alternative bridge 了。

那么回到正题，如果 Bessie 的起点在 i，那么 i 以前的所有 alternative bridge 全部可以为 Elsie 所用。我们从 1 到 n 扫一遍每一个结点，并更新所有与这个结点相连的结点的最短路。注意，这里的最短路是对于 Elsie 而言的，用 dis 数组储存。

我们想想怎么统计答案呢？这促使我们思考什么时候 Elsie 会走到 Bessie 前面。假设一个 alternative bridge，其起点为 u，终点为 v，使得 Elsie 超过了 Bessie，那么 Bessie 应该在什么点出发才会造成这种情况？

首先在 u 之前或者 u 出发是不可能的。前面说过。

其次，我们来想想什么情况下 Elsie 会比 Bessie 快？形象化的理解，当然是 Elsie 到达结点 v 比 Bessie 早。设 Bessie 的起点为 s，那么当且仅当 dis_v<v-s 的时候 Elsie 到达结点 v 的时间比 Bessie 早。

那么你可以看到，对于每一个 alternative bridge，我们会得到一个区间的始发点 s 使得 Bessie 无法获胜。具体地，这个区间为 [u+1,v-dis_v-1]。我们得到了所有的区间，要怎么合并区间呢？

这里有一个我某天突然想到的一个 trick：对于得到的每一个区间，把区间中每一个元素加上 1，这里用差分数组维护。然后对差分数组做一个前缀和，得到一个数组 s，这个数组里面每个点 i 表示 i 被几个区间覆盖。所有 s_i>0 的点都是 Bessie 必输的点，其他点都是 Bessie 必胜的点。

#include<bits/stdc++.h>
using namespace std;
const int MAXN=2e5+10;
int T,n,m;
int d[MAXN],s[MAXN],dis[MAXN];
vector<int> g[MAXN];
int main(){
    scanf("%d",&T);
    while(T--){
        scanf("%d%d",&n,&m);
        for(int i=0;i<=n;++i){
            d[i]=s[i]=0;
            g[i].clear();
            dis[i]=0x3f3f3f3f;
        }
        dis[1]=0;
        for(int i=0,u,v;i<m;++i){
            scanf("%d%d",&u,&v);
            g[u].push_back(v);
        }
        for(int u=1;u<=n;++u){
            dis[u]=min(dis[u],dis[u-1]+1);
            for(int v:g[u]){
                if(v-u>dis[u]+1){
                    ++d[u+1];
                    --d[v-dis[u]-1];
                }
                dis[v]=min(dis[v],dis[u]+1);
            }
        }
        for(int i=1;i<=n;++i){
            s[i]+=s[i-1]+d[i];
        }
        for(int i=1;i<n;++i){
            if(s[i]){
                putchar('0');
            }
            else{
                putchar('1');
            }
        }
        putchar('\n');
    }
    return 0;
}