P6700 [PA2015]Edycja

Fan_sheng · 2023-04-02 00:19:53 · 题解

省选两天已经考完了，出考场的时候整个人都是麻着的。这大概是我退役前最后一篇题解了，写一道有价值的黑题纪念一下吧。

性质一：一定存在一种最优的操作顺序，使得所有二操作都在一操作之前。

证明：假如先把 a[i] 用一操作改成 X，再用二操作把所有 X 改成 Y。显然等价于先用二操作把所有 X 改成 Y，再把 a[i] 用一操作改成 Y。

性质二：同一个字母不可能进行多于一次的二操作。

证明：假如已经对字母 a 用了二操作，此时场上就没有 a 了。如果再进行一次二操作 a\rightarrow b，必然先前存在 c\rightarrow a。不如直接 c\rightarrow b。

对每个字母建点。每个点对 (u,v)，u 向 v 连一条单向边。其中边权为：s[i]=u\land t[i]\neq v 的位置数，如果 u\neq v，再加上 c。之后会讲这张图的含义。

原问题就可以转化：我们有 n 颗棋子，第 i 颗所在节点代表当前 i 位置的字符，初始放在 s[i] 上。如果进行 u\rightarrow v 的二操作，相当于把 u 上所有棋子移到 v 上。然而这些移过来的棋子还需要通过一操作改成 t[i]，再加上二操作的代价，总代价就是 u 到 v 的边权。

如果感觉抽象的话可以看看图。比如说 b 上面有两颗棋子（分别是 2 号和 4 号）。我们可以用二操作把 b 变成 a，但是 4 号的终态应该是 b，需要再用一次一操作修改，总代价就是 b\rightarrow a 的边权 1+c。

根据性质二，我们要为每个点都确定一条唯一的出边，形成内向基环树森林，每颗棋子都要能通过这些边到达它的终点，同时总代价最小。考虑每个点都先贪心地选最小边权出边，看看会发生什么。

对于一棵树（根节点自环），按反拓扑序依次挪动棋子就好了，不会产生任何冲突。

对于一棵基环树（如上图），只借助基环树上的边是不行了。可以考虑先把 a 上的棋子通过二操作挪到 d 上，这样 a 节点空出来，就不会冲突了。算出来代价和原来一样。

对于一个大小 >1 的环，由于不存在叶子节点，必须借助环外的一个点来“中转”才行。如果森林中存在大小 >1 的树/基环树，可以先操作完那棵树/基环树，其叶子节点会空出来。比如这张图，你可以把 g 上棋子都挪到 d 上，再挪到 f 上，就不会冲突了。这样做的代价比原来增加了 c。如果图上不存在大小 >1 的树/基环树，就不可能完成挪动，无解。

由于每个环都会额外贡献 c，我们开始的贪心策略可能不是最优的，考虑修改某些点的出边。

性质三：存在一种最优的修改策略，使得新图不会产生原图没有的环。

证明：如果出现了新环，环上一定存在一个点的出边被修改过。如果把它改回去，不仅边权会变小，同时新环也会被破开，肯定更优。

所以做法就出来了：先预处理出原图中所有的环。设 dp[i][S][0/1] 表示当前要为第 i 个点选择出边，S 集合中的环已被破开，是否有点的出边被修改过，最小代价。

转移直接枚举出边，如果策略与原来不一样，就可以破开自己所在的环与对方所在的环。根据性质三，我们不需要考虑这么做是否会产生新的环。0/1 那一维用于规避无解情况，那种情况下必须要修改策略才行。我的代码里这样会好写一点，你也可以用其他方式特判；还要注意，全是自环是一种可行的方案。

最多有 13 个大小 >1 的环，时间复杂度 \mathbb O(\Sigma^2 2^{\frac{\Sigma}{2}})。

Code

#include<bits/stdc++.h>
#define H(x) ((x)-'a'+1)
using namespace std;
typedef long long ll;
int n,c,w[27][27],nxt[27],cnt,b[27],in[27],spj=1,W[27][27];
char s[1000003],t[1000003];
ll dp[27][1<<13][2];
inline void ckmin(ll &a,ll b){a=(a<b?a:b);}
inline void toposort(){
    for(int i=1;i<=26;i++)in[nxt[i]]++;
    queue<int>q;
    for(int i=1;i<=26;i++)if(!in[i])q.emplace(i),spj=0;
    while(q.size()){
        int h=q.front();q.pop();
        if(!(--in[nxt[h]]))q.emplace(nxt[h]);
    }
    for(int i=1;i<=26;i++)if(in[i]&&nxt[i]!=i){
        ++cnt;
        int now=i;
        while(in[now]){
            in[now]=0,b[now]=cnt;
            now=nxt[now];
        }
    }
    if(!cnt){
        ll ans=0;
        for(int i=1;i<=26;i++)ans+=w[i][nxt[i]];
        printf("%lld",ans),exit(0);
    }
}
inline void DP(){
    memset(dp,0x3f,sizeof(dp)),dp[0][0][0]=0;
    for(int i=1;i<=26;i++)
    for(int S=0;S<(1<<cnt);S++)
    for(int t=0;t<2;t++)
    for(int j=1;j<=26;j++){
        int T=S;
        if(b[i]&&nxt[i]!=j)T|=(1<<(b[i]-1));
        if(b[j]&&(nxt[i]!=j||b[i]!=b[j]))T|=(1<<(b[j]-1));
        ckmin(dp[i][T][t|(nxt[i]!=j)],dp[i-1][S][t]+w[i][j]);
    }
    ll ans=LLONG_MAX;
    for(int S=0;S<(1<<cnt);S++)
    for(int t=spj;t<2;t++)
    ckmin(ans,dp[26][S][t]+1ll*c*(cnt-__builtin_popcount(S)));
    printf("%lld",ans),exit(0);
}
int main(){
    scanf("%d%d%s%s",&n,&c,s+1,t+1);
    for(int i=1;i<=n;i++)W[H(s[i])][H(t[i])]++;
    for(int i=1;i<=26;i++){
        w[i][0]=0x3f3f3f3f;
        int tot=0;
        for(int j=1;j<=26;j++)tot+=W[i][j];
        for(int j=1;j<=26;j++){
            w[i][j]=tot-W[i][j];
            if(i!=j)w[i][j]+=c;
            if(w[i][j]<w[i][nxt[i]])nxt[i]=j;
        }
    }toposort(),DP();
}

我果然还是想在洛谷留下一点我的足迹。谢谢你看到这里，你们还有无限的可能，祝前程似锦。

欢迎找 bug，虽然我不太可能有精力修就是了……