Field Day (USACO Silver 2023 Open)

这个题难点在于基于数据规模选择合适的算法。我们要计算的是所有 $N(10^5)$ 个字串之间两两的编辑距离edit distance的最大值，每个字串最长为C=18。

直观地计算两两距离显然导致TLE，解决的办法，就是观察到C的值很小， $2^C \approx 2.6 \cdot 10^5$ 。所以我们考虑使用在整个状态空间暴力BFS的办法。

首先最长距离不好算，我们找到一个办法可以把最长距离转化成最短距离： $L_x = C - S_{\bar x}$ ，其中 $L_x$ 是从所有字串出发到 $x$ 的最长距离， $S_x$ 是从所有字串出发到 $x$ 的最短距离， $\bar x$ 是 $x$ 的反（G变成H，H变成G）。

然后我们就用BFS算法，来计算多起点多终点最短距离（Multi-Source Multi-Destination Shortest Path）。我们从每个数字出发进行广度优先搜索（BFS），每次往前走一步（改变一个字符），距离加1，并将没有见过的点设置上最短距离，并加入队列。重复上述过程，直到所有 $2^C$ 个状态都被访问。

用bitmask来表示字符串比较方便，计算和比较也更快。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
int n, c;
int d[1<<18];
queue<int> q;
vector<int> a;
 
int main() {
    scanf("%d %d", &c, &n);
    memset(d, -1, sizeof(d));
    for (int i = 0; i < n; i++) {
        char s[20];
        scanf("%s", s);
        int x = 0;
        for (int j = 0; j < c; j++) {
            x = (x << 1) | (s[j] - 'G');
        }
        a.push_back(x);
        d[x] = 0;
        q.push(x);
    }
 
    while (!q.empty()) {
        int x = q.front();
        q.pop();
        for (int i = 0; i < c; i++) {
            int y = x ^ (1 << i);
            if (d[y] == -1) {
                d[y] = d[x] + 1;
                q.push(y);
            }
        }
    }
 
    for (auto x : a) {
        printf("%d\n", c - d[(1 << c) - 1 - x]);
    }
 
    return 0;
}