やっぱり雨は降るんだね | 题解：P10433 [JOISC 2024 Day2] 棋盘游戏

Petit_Souris · 2024-07-31 00:02:27 · 题解

这个题太难了。思考时间至少得有 1.5h，代码和 debug 难度也很高。放到正式比赛场上我不可能通过。

最初的观察

我们现在需要最小化棋子 1 走到点 T 的时间，假设棋子 1 经过了 c 个终止节点，那么 2\sim K 号棋子分别需要走 c 次。这时候我们容易发现剩下的棋子是独立的，我们只需要分别最小化他们的步数。

由于这是一张无向图，我们容易发现可以有一种很好的策略：先走到一个终止节点，从第二次开始每次走出一步再走回来，这样除了第一回合以外，每个回合对答案的贡献为固定的 2。

但是我们发现这样不一定是最优的：我们可能可以走到两个相邻的终止节点中的一个，并在两个终止节点之间反复横跳，这样除了第一回合以外每个回合只贡献 1 的答案。那么很容易想到走到最近的终止节点 / 相邻的一组终止节点并反复横跳。很可惜，这样并非完全正确——走到相邻的终止节点的路径上可能有其他的终止节点。

巧妙的补丁

我们分析一下走到一组相邻终止节点的路径情况：假设路径上经过了 c_1 个终止节点，路径长度为 d，而棋子 1 总共经过了 c 个终止节点，那么实际上贡献为 d+c-c_1。那么有个很简单的修补方式：将终止节点赋上 -1 的权值，给边赋上 1 的权值，这样跑 01 bfs。

你可能会好奇，这样为什么是对的？难道不会出现 c_1>c 的路径被计算的情况吗？很容易分析出这种情况下，如果前 c 个点中就已经有一对相邻点的，那么停在那个位置是更优的，否则如果不存在，每走一步，d 增加至少 2，而 c_1 只会增加 1，因此只会更劣。

问题的开端

现在 2\sim K 每个棋子的代价可以被表示为 \min(c+f_1,2c+f_2) 的形式。那么对于每个 c，剩下棋子的代价容易被计算出来（找出分段点，使用前缀和计算），是一个关于 c 的函数 F(c)。

现在我们的问题清晰许多了：对于一条 X_1\to T 的路径，如果长度为 D，经过了 c 个终止节点，那么答案为 \min(D+F(c))。

在繁琐的分析之后我们之后得出了多项式时间复杂度的做法：记录当前的 c 跑最短路，时间复杂度为 \mathcal O(n^2)。

最终的一击

考虑优化。我们发现当 K 比较大的时候，我们肯定倾向于控制 c 不要太大，因为 c 一旦增加 1，代价至少会增加 K-1。我们容易分析得到，设 X_1\to T 最少需要经过 x 个终止节点，最优解经过了 y 个终止节点，那么 y-x 是 \mathcal O(\frac{n}{K}) 级别的。我们轻松把上面的做法优化到了 \mathcal O(\frac{n^2}{K})。

既然除以 K 的字眼都出来了，再结合上部分分，最后一击只能是根号分治了。最后的最后，我们思考一下如何解决 K 较小的情况。

容易发现 F 这个函数是上凸的，且段数是 \mathcal O(K) 级别的，因此我们可以取出这 \mathcal O(K) 段线段并求解。如果我们将这条线段延申成直线，那么问题就好做了：把贡献拆到转移点上直接跑最短路。稍微分析一下就容易发现这样不可能把答案算小，且要算的答案肯定已经计算进去了。于是这部分是时间复杂度为 \mathcal O(nK\log n)。

平衡两边复杂度，取 K=\mathcal O(\frac{\sqrt{n\log n}}{\log n})，得到时间复杂度为 \mathcal O(n\sqrt {n\log n})。

代码细节相当繁琐。

#include<bits/stdc++.h>
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
#define pii pair<ll,ll>
#define rep(i,a,b) for(ll i=(a);i<=(b);++i)
#define per(i,a,b) for(ll i=(a);i>=(b);--i)
using namespace std;
bool Mbe;
ll read(){
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
void write(ll x){
    if(x<0)putchar('-'),x=-x;
    if(x>9)write(x/10);
    putchar(x%10+'0');
}
const ll N=5e4+9,INF=1e12;
ll n,m,K,X[N],tod[2][N],tag[N],md[N],cst[N];
vector<ll>to[N];
char s[N];
void run1(){
    queue<ll>q;
    rep(i,0,n)tod[0][i]=-1;
    rep(i,1,n){
        if(s[i]=='1'){
            for(ll j:to[i])q.push(j),tod[0][j]=1;
        }
    }
    rep(i,1,n){
        if(~tod[0][i])q.push(i);
    }
    while(!q.empty()){
        ll u=q.front();q.pop();
        for(ll v:to[u]){
            if(!~tod[0][v]){
                tod[0][v]=tod[0][u]+1;
                q.push(v);
            }
        }
    }
}
void run2(){
    deque<ll>q;
    rep(i,0,n)tod[1][i]=-1;
    rep(i,1,n){
        if(tag[i]){
            for(ll j:to[i])tod[1][j]=1;
        }
    }
    rep(i,1,n){
        if(~tod[1][i])q.push_back(i);
    }
    while(!q.empty()){
        ll u=q.front();q.pop_front();
        for(ll v:to[u]){
            if(s[u]=='1'){
                if(!~tod[1][v]||tod[1][v]>tod[1][u])tod[1][v]=tod[1][u],q.push_front(v);
            }
            else {
                if(!~tod[1][v]||tod[1][v]>tod[1][u]+1)tod[1][v]=tod[1][u]+1,q.push_back(v);
            }
        }
    }
}
void run3(){
    rep(i,0,n)md[i]=INF;
    md[X[1]]=0;
    queue<ll>q;
    q.push(X[1]);
    while(!q.empty()){
        ll u=q.front();q.pop();
        if(u!=X[1]&&s[u]=='1')continue;
        for(ll v:to[u]){
            if(md[v]>md[u]+1){
                md[v]=md[u]+1;
                q.push(v);
            }
        }
    }
}
namespace S1{
    ll minc[N],f[N][505];
    void solve(){
        rep(i,1,n)minc[i]=INF;
        deque<ll>q;
        q.push_back(X[1]);
        minc[X[1]]=0;
        while(!q.empty()){
            ll u=q.front();q.pop_front();
            for(ll v:to[u]){
                ll w=(s[u]=='1'&&u!=X[1]);
                if(minc[v]>minc[u]+w){
                    minc[v]=minc[u]+w;
                    if(!w)q.push_front(v);
                    else q.push_back(v);
                }
            }
        }
        rep(i,0,n){
            rep(j,0,min(500ll,n/K))f[i][j]=INF;
        }
        queue<pii>q1;
        f[X[1]][0]=0;
        q1.push({X[1],0});
        while(!q1.empty()){
            pii now=q1.front();q1.pop();
            ll u=now.first,i=now.second;
            for(ll v:to[u]){
                ll j=minc[u]+i-minc[v]+(u!=X[1]&&s[u]=='1');
                if(j<=min(500ll,n/K)){
                    if(f[v][j]>f[u][i]+1)f[v][j]=f[u][i]+1,q1.push({v,j});
                }
            }
        }
        rep(i,1,n){
            ll ans=md[i];
            rep(j,0,min(500ll,n/K))ans=min(ans,f[i][j]+cst[minc[i]+j]);
            write(ans),putchar('\n');
        }
    }
}
namespace S2{
    ll dis[N][2],ans[N];
    bool ok[N][2];
    struct Node{
        ll u,tp,d;
        bool operator<(const Node&a)const{return d>a.d;}
    };
    void dijk(ll k,ll sp){
        priority_queue<Node>q;
        rep(i,0,n+1){
            rep(j,0,1)dis[i][j]=INF,ok[i][j]=0;
        }
        dis[X[1]][0]=0;
        q.push({X[1],0,0});
        while(!q.empty()){
            Node now=q.top();q.pop();
            ll u=now.u,tp=now.tp;
            if(ok[u][tp])continue;
            ok[u][tp]=1;
            for(ll v:to[u]){
                ll w=1+k*(u!=X[1]&&s[u]=='1');
                ll ntp=tp||(u!=X[1]&&s[u]=='1');
                if(dis[v][ntp]>dis[u][tp]+w){
                    dis[v][ntp]=dis[u][tp]+w;
                    q.push({v,ntp,dis[v][ntp]});
                }
            }
        }
        rep(i,1,n)ans[i]=min(ans[i],sp+dis[i][1]);
    }
    void solve(){
        rep(i,1,n)ans[i]=md[i];
        rep(i,2,n){
            if(i==n||cst[i]*2!=cst[i-1]+cst[i+1])dijk(cst[i]-cst[i-1],cst[i]-(cst[i]-cst[i-1])*i);
        }
        rep(i,1,n)write(ans[i]),putchar('\n');
    }
}
bool Med;
int main(){
    cerr<<fabs(&Med-&Mbe)/1048576.0<<"MB\n";
    n=read(),m=read(),K=read();
    rep(i,1,m){
        ll x=read(),y=read();
        to[x].push_back(y);
        to[y].push_back(x);
    }
    scanf("%s",s+1);
    rep(i,1,K)X[i]=read();
    rep(i,1,n){
        if(s[i]=='1'){
            for(ll j:to[i]){
                if(s[j]=='1')tag[i]=1;
            }
        }
    }
    run1(),run2(),run3();
    if(!count(s+1,s+n+1,'1')){
        rep(i,1,n)write(md[i]),putchar('\n');
        return 0;
    }
    rep(i,2,K){
        cst[2]+=2;
        if(~tod[1][X[i]])cst[tod[1][X[i]]-tod[0][X[i]]+2]--;
    }
    rep(i,2,n)cst[i]+=cst[i-1];
    rep(i,2,K)cst[1]+=tod[0][X[i]];
    rep(i,2,n)cst[i]+=cst[i-1];
    if(K>=100)S1::solve();
    else S2::solve();
    cerr<<"\n"<<clock()*1.0/CLOCKS_PER_SEC*1000<<"ms\n";
    return 0;
}