题解：P6700 [PA 2015 Final] Edycja

· · 题解

挺好的题，模拟赛只写出来了一个搜子。

首先先有显然的性质。

证明显然，首先，一个位置最多做一次一操作。那么我们假设一种方案中位置 i 先被进行一操作，然后再进行二操作，那我们直接把他放在所有二操作后面，变成最终的颜色，也一定是等价的。

这个性质让我们可以针对二操作进行思考。

我们不妨用图上连边的方式来描述这个性质。不妨用 i \rightarrow j 这样一条边来描述，在最终未进行一操作的图上，所有字母 i 全部变成了 j。请注意，这个边不等于二操作。

但是显然这样一个图和我们的二操作执行是有非常紧密的联系的。首先你发现这个图显然是基环树，因为每个点显然只有一条出边。然后观察一下。

首先如果这个图类似于一颗“树”：

你发现从上往下操作即可。

进一步的，如果他是一个基环树，并且有树枝：

你发现可以先这样做一次二操作：

此时的图就和这个图等价了：

然后像刚才一样做即可。

但是你发现这个必须要依赖于有一个“树枝”，那没有树枝的纯环呢？你发现，此时必须依赖一个外部的、不在环上的点来进行“周转”。比如说 aaabbb 要变成 bbbaaa，必须先把 aaa 变成 ccc，然后像刚才那么做。

也就是说，对于一般的基环树，要变成这样的图的代价是边数（抛开自环）乘 c，但是对于纯环，还要多一个 c 的代价。

那你考虑怎么刻画这件事。不妨先不看这个纯环多出的代价。一种方式是直接爆搜出边。但是你发现，这个一操作的次数实际上是极其容易计算的。

我们设 cnt_i 表示字符 i 在 A 中出现了 cnt_i 次，sum_{i,j} 表示 A 中位置上是 i，B 中对应位置是 j 的位置数量。

那此时我们不妨直接把基环树上边赋上边权，i \rightarrow j 的边权是：

cnt_i-sum_{i,j}+[i \ne j]k

那基环树的总代价就是边权之和。

考虑先不看纯环多出来的代价应该怎么选。你发现此时你直接每个位置贪心选边权最小出边即可。这个图显然是极其优秀的，我们考虑在上面改一改。

你发现我们实际上环数（抛开自环）是很少的，因此我们想到可以对于环数进行状压。设 dp_{S} 表示 S 中的环外面接了树枝或者环断掉，比“贪心方案”不算纯环时的代价多了多少。

转移就是枚举新加边，像背包一样转移。

但是你发现这样还是有些问题，比如说有一个 a 到 x 的大环，还有一个 y 和 z 的自环，你发现这时也是无法做的。

具体的你规约一下，如果这个基环树森林是一堆纯环（包括自环），一定不行。

那你发现这个条件如果就只有目前这一位其实是不好刻画的，因此不妨引入第二维，我们重新定义 dp_{S,flag} 表示 S 中的环外面接了树枝或者环断掉，是不是由一堆纯环组成，比“贪心方案”不算纯环时的代价多了多少。

简单转移即可。

可能会有疑问，会不会改着改着把两个环拼成一个环了，这样显然一定是不优的，不会被保留。

AC Code

#include<bits/stdc++.h>
using namespace std ;
const int MAXN = 1e6 + 7 ;
const int MAXK = 30 ;
const int INF = 1e9 + 7 ;
const int MAXG = 14 ;
int n , k ;
int cnt[MAXK] ;
int sum[MAXK][MAXK] ;

char d[MAXK] , lst ;    //字符集
int vis[MAXK] ; 

int a[MAXN] , b[MAXN] ;
char s[MAXN] , t[MAXN] ;

int c[MAXK][MAXK] ;

int bel[MAXK] ; //属于哪个环
int nxt[MAXK] ; //初始贪心选边 

vector<int> dir[MAXN] ;

int dfn[MAXN] , low[MAXN] , lst1 , lst2 ;
bool instack[MAXN] ;
stack<int> g ;
void tarjan(int u) {
    dfn[u] = low[u] = ++lst1 ;
    instack[u] = 1 ;
    g.push(u) ;

    int v = nxt[u] ;

    if (!dfn[v]) {
        tarjan(v) ;
        low[u] = min(low[u] , low[v]) ;
    }
    else {
        low[u] = min(low[u] , dfn[v]) ;
    }

    if (low[u] == dfn[u]) {
        if (g.top() != u) {
            lst2 ++ ;
            while (1) {
                int p = g.top() ;
                g.pop() ;
                bel[p] = lst2 ;

                if (p == u) {
                    break ;
                }
            }
        }
        else {
            g.pop() ;
        }
    }

    return ;
}

int dp[1 << MAXG][2] ;
int f[1 << MAXG][2] ;

signed main()
{
//  freopen("" , "r" , stdin) ;
//  freopen("" , "w" , stdout) ;

    ios::sync_with_stdio(0) ;
    cin.tie(0) ;
    cout.tie(0) ;

    cin >> n >> k ;

    cin >> s + 1 >> t + 1 ;

//  cout << s + 1 << "\n" << t + 1 ;

    for (int i = 1 ; i <= n ; i ++) {
        if (!vis[s[i] - 'a']) {
            d[++lst] = s[i] ;
            vis[s[i] - 'a'] = lst ;
        }
        if (!vis[t[i] - 'a']) {
            d[++lst] = t[i] ;
            vis[t[i] - 'a'] = lst ;
        }

        a[i] = vis[s[i] - 'a'] ;
        b[i] = vis[t[i] - 'a'] ;
    }

    for (int i = 1 ; i <= n ; i ++) {
        cnt[a[i]] ++ ;

        sum[a[i]][b[i]] ++ ;
    }

    for (int i = 0 ; i < 26 ; i ++) {
        if (!vis[i]) {
            d[++lst] = (char)(i + 'a') ;
        }
    }

    int s = 0 ;
    for (int i = 1 ; i <= lst ; i ++) {
        int mi = 0 ;
        c[i][0] = INF ;

        for (int j = 1 ; j <= lst ; j ++) {
            c[i][j] = cnt[i] - sum[i][j] + (i != j ? k : 0) ;
            if (c[i][j] < c[i][mi]) {
                mi = j ;
            }
        }

        nxt[i] = mi ;
        dir[i].push_back(mi) ;
        dir[mi].push_back(i) ;

        s += c[i][mi] ;
    }

    for (int i = 1 ; i <= lst ; i ++) {
        if (!dfn[i]) {
            tarjan(i) ;
        }
    }

    if (!lst2) {
        cout << s ;
        return 0 ;
    }

    bool g = 0 ;
    for (int i = 1 ; i <= lst ; i ++) {
        if (dir[i].size() != 2) {
            g = 1 ;
        }
    }

    memset(dp , 0x3f , sizeof(dp)) ;
    dp[0][g] = 0 ;

    for (int i = 1 ; i <= lst ; i ++) {
        memcpy(f , dp ,sizeof(dp)) ;

        for (int j = 1 ; j <= lst ; j ++) {
            int w = c[i][j] - c[i][nxt[i]] ;

            for (int k = 0 ; k < (1 << lst2) ; k ++) {
                int g = k ;

                if (bel[i] and j != nxt[i]) {
                    g |= (1 << (bel[i] - 1)) ;
                }

                if (bel[j] and bel[j] != bel[i]) {
                    g |= (1 << (bel[j] - 1)) ;
                }

                for (int p = 0 ; p <= 1 ; p ++) {
                    bool flag = p | (j != nxt[i]) ;

                    f[g][flag] = min(f[g][flag] , dp[k][p] + w) ;
                }
            }
        }

        memcpy(dp , f , sizeof(dp)) ;
    }

    int ans = INF ;

    for (int i = 0 ; i < (1 << lst2) ; i ++) {
        ans = min(ans , s + dp[i][1] + (lst2 - __builtin_popcount(i)) * k) ;
    }

    cout << ans ;

    return 0 ;
}