题解：CF1998D Determine Winning Islands in Race

· · 题解

又没打到勇者，恼火。

码速太差 /ll

首先只要敌方可以跃到我方的前面就赢了。

考虑从前向后动态更新答案，那么容易发现可达的点是不断增加的，同时注意到这个图是个 dag，所以可以直接 dag dp 向后加贡献维护最短路。

那么只要有一个点满足敌方最短路短于我方最短路就输了。

假设出发点是 i，并且敌方到达点 x 的最短路长度为 d，所以一个点对于敌方合法当且仅当 x-i>d，由于 i 一直在变所以把等式改写成 i<x-d。

我们维护 d 的时候求 x-d 的最大值，动态维护这个最大值和 i 作比较即可。

时间复杂度线性。

#include<bits/stdc++.h>
#define lowbit(x) x&-x
#define int long long
#define N 200000
using namespace std;
vector<int>ve[N+5];
int dis[N+5];
void solve(){
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    ve[i].clear();
    for(int i=1;i<=n;i++)
    dis[i]=1e17;
    dis[1]=0;
    while(m--){
        int u,v;
        cin>>u>>v;
        if(u>v)swap(u,v);
        ve[u].push_back(v);
    }
    int mx=-1;
    for(int i=1;i<n;i++)
    ve[i].push_back(i+1);
    for(int i=1;i<=n;i++)
    mx=max(mx,i-1-dis[i]);
    cout<<'1';
    for(int i:ve[1])
    dis[i]=min(dis[i],dis[1]+1),
    mx=max(mx,i-1-dis[i]);
    for(int i=2;i<n;i++){
        if(mx<i)cout<<1;
        else cout<<0;
        for(int j:ve[i])
        if(dis[i]+1<dis[j]){
            dis[j]=dis[i]+1;
            mx=max(mx,j-1-dis[j]);
        }
    }
    cout<<'\n';
}
signed main(){
    int t;
    cin>>t;
    while(t--)solve();
    return 0;
}
// 哎，确实是那样啦。

// 感觉她们每天都拚了命地活着。
// 感觉她们莽撞得令人操心。
// 面对或许会丧命的战斗，不知道是迟钝或胆量过人，她们都具备不改平常心的精神力。