题解：P6681 [CCO 2019] Bad Codes

· · 题解

模拟赛 T2，以下为作者的赛时想法。

看到的第一眼估计大部分人觉得是 dp。

首先，考虑一个串串可以记到答案里的条件:

  1. 可以被表示。

  2. 可以有两种不同表示方法。

首先想第二个限制。我们考虑两种表示方法 A，B。他们第一个选的字符串肯定不一样。所以我们枚举第一个选的字符串，这样就只要找到最优的可以把一开始选的两个字符串给填成相同的最小长度。

上面黑色表示一个我们要填平的字符串，而下面的黑色为输入的一个字符串，我们可以用红色的部分后面加一个黑的来填。

我们假设红色为 A，下面的黑色长度为 lenw，上面的黑色为 B。

那么有：

f_B=f_A+lenw

这个转移是有环的，所以考虑直接跑最短路。

#include <bits/stdc++.h>
#define int long long 

using namespace std;
const int N = 55;
const int M = 1e6 + 5;
int a[N]; char x[N][N];
int tot;
map <int, int> mp;
struct Edge {
    int v, nxt, w;
} e[M << 1]; int etot, hd[M];
void add_edge(int u, int v, int w) { e[++ etot] = (Edge){v, hd[u], w}; hd[u] = etot; }
int newnode(int x, int len) {
    x += (1ll << len);
    if (mp[x] == 0) mp[x] = ++ tot; 
    return mp[x];
}
struct Node {
    int v, w;
    bool operator > (Node b) const { return w < b.w; }
    bool operator < (Node b) const { return w > b.w; }
};
priority_queue <Node> q;
int dis[M]; bool vis[M]; 
const int inf = 1e9;
void Dis() {
    fill(dis, dis + tot + 1, inf);
    q.push((Node){newnode(0, 0), 0}); dis[newnode(0, 0)] = 0;
    while (!q.empty()) {
        int u = q.top().v; q.pop();
        if (vis[u]) continue; vis[u] = 1;
        for (int i = hd[u] ; i ; i = e[i].nxt) {
            int v = e[i].v; 
            if (dis[v] > dis[u] + e[i].w) {
                dis[v] = dis[u] + e[i].w;
                q.push((Node){v, dis[v]});
            } 
        }
    }
}
signed main() {
    freopen("string.in", "r", stdin);
    freopen("string.out", "w", stdout);
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int n, m; cin >> n >> m;
    for (int i = 1 ; i <= n ; i ++) {
        cin >> x[i] + 1;
        for (int j = 1 ; j <= strlen(x[i] + 1) ; j ++)
            a[i] = a[i] * 2 + (x[i][j] - '0');
    }
    for (int i = 1 ; i <= n ; i ++) {
        int u = 0;
        for (int j = 1 ; j <= strlen(x[i] + 1) ; j ++) {
            u = u * 2 + (x[i][j] - '0');
            for (int k = 1 ; k <= n ; k ++) {
                int lenk = strlen(x[k] + 1);
                bool flag = 0;
                for (int A = j, B = lenk ; A >= 1 && B >= 1 ; A --, B --) 
                    if (x[i][A] != x[k][B]) {
                        flag = 1;
                        continue;
                    } 
                if (flag) continue;
//              cout << i << ' ' << j << ' ' << k << '\n';
                int v = abs(u - a[k]), w = min(j, lenk), len = max(j, lenk);
                v >>= w;
                add_edge(newnode(v, len - w), newnode(u, j), lenk);
            }
        }
    }
    Dis();
    int res = inf;
    for (int i = 1 ; i <= n ; i ++) 
        for (int j = 1 ; j <= n ; j ++)
            if (i != j) { bool flag = 0;
                int leni = strlen(x[i] + 1), lenj = strlen(x[j] + 1);
                for (int A = leni, B = lenj ; A >= 1 && B >= 1 ; A --, B --) {
                    if (x[i][A] != x[j][B]) {
                        flag = 1;
                        break;
                    } 
                }
                if (flag) continue;
                int v = abs(a[i] - a[j]); 
                int w = min(leni, lenj), lenv = max(leni, lenj);
                v >>= w; 
                if (dis[newnode(v, lenv - w)] == inf || dis[newnode(v, lenv - w)] == 0) continue;
                res = min(res, dis[newnode(v, lenv - w)] + leni + lenj);
            }
    if (res == inf)  cout << -1;
    else cout << res / 2;
    return 0;
}
/*
4 6
00000
00100
00010
0001
*/

这是考前的题解，所以祝愿大家 NOIP2025 unsigned long long rp = 0; rp --;