https://codeforces.com/contest/903/problem/E
题目大意
有某未知长为 $n$ 的串 $s$ 和 $k$ 个由串 $s$ 通过交换两个不同下标字符构成的串 $s_i$。其中 $k \le 2500, nk \le 5000$。输入未必合法。问是否有这样的串 $s$，如果没有输出 $-1$，否则给出任意合法的串。
简要题解
观察：
- 两个串 $s_i$ 和 $s_j$ 之间最多只会有 $4$ 个位置不一样，否则原串一定不存在。（因为一次交换可以最多让两个位置不同）。
- 两个串如果只有 $1$ 个位置不同，则说明字符频率不同，这无法通过 $s$ 交换得到。
- 两个串如果没有不同，则可能是原串的某个相同交换。
- $3$ 个或者 $4$ 个不同是可能的。
- 某串只可能与原串有 $2$ 个不同，或者当原串有重复字符时，与原串有 $0$ 个不同。
于是我们找出和 $s_0$ 不同最多的串 $s_i$。
- 如果最多不同个数是 $0$ 则我们直接任意交换 $s_0$ 的两个元素就可以作为原串。
- 对于 $2, 3, 4$ 的情况，我们直接枚举 $s_0$ 和 $s_i$ 不同位置的字母的所有交换后的可能。如果有解则一定可以找出，否则无解。
这里证明一下为什么这样是对的。
$4$ 的情况是最显然的，因为 $4$ 个不同意味着这里必然包含了两次交换的所有位置，则其他位置的元素都是定死的。则枚举不同位置的字母的排列显然可以遍历所有可能情况。
$3$ 的情况是类似的，两次交换一定覆盖了同一个公共位置和两个不同的位置。所以其他位置也都是定死的。
$2$ 不太显然。能得到 $2$ 只有以下两种可能。
aba
12 baa
23 aab
abcc
12 bacc
34 abcc
注意到这两种可能中都需要有重复字母存在，而所有的串和 $s_0$ 的差别只有 $2$，因此我们总可以将 $s_0$ 作为 $s$。
复杂度
$T$：$O(nk)$ 这里有个较大常数 $4!$
$S$：$O(nk)$
代码实现
#include <bits/stdc++.h>
using namespace std;
int io_=[](){ ios::sync_with_stdio(false); cin.tie(nullptr); return 0; }();
using LL = long long;
using ULL = unsigned long long;
using LD = long double;
using PII = pair<int, int>;
using VI = vector<int>;
using MII = map<int, int>;
template<typename T> void cmin(T &x,const T &y) { if(y<x) x=y; }
template<typename T> void cmax(T &x,const T &y) { if(x<y) x=y; }
template<typename T> bool ckmin(T &x,const T &y) {
return y<x ? (x=y, true) : false; }
template<typename T> bool ckmax(T &x,const T &y) {
return x<y ? (x=y, true) : false; }
template<typename T> void cmin(T &x,T &y,const T &z) {// x<=y<=z
if(z<x) { y=x; x=z; } else if(z<y) y=z; }
template<typename T> void cmax(T &x,T &y,const T &z) {// x>=y>=z
if(x<z) { y=x; x=z; } else if(y<z) y=z; }
// mt19937 rnd(chrono::system_clock::now().time_since_epoch().count());
// mt19937_64 rnd_64(chrono::system_clock::now().time_since_epoch().count());
/*
---------1---------2---------3---------4---------5---------6---------7---------
1234567890123456789012345678901234567890123456789012345678901234567890123456789
*/
void solve() {
int k, n; cin >> k >> n;
vector<string> s(k);
for (int i = 0; i < k; i++) {
cin >> s[i];
}
int p = 0, mx = 0;
for (int i = 1; i < k; i++) {
int diff = 0;
for (int j = 0; j < n; j++) {
if (s[0][j] != s[i][j]) diff++;
}
if (diff == 1 || diff > 4) {
cout << "-1\n";
return;
}
if (diff > mx) {
mx = diff;
p = i;
}
}
if (mx == 0) {
swap(s[0][0], s[0][1]);
cout << s[0] << '\n';
return;
}
bool has_same = false;
map<char, int> cnt;
for (int i = 0; i < n; i++) {
cnt[s[0][i]]++;
}
for (auto [v, c] : cnt) {
if (c >= 2) has_same = true;
}
vector<char> chs;
vector<int> pos;
for (int i = 0; i < n; i++) {
if (s[0][i] != s[p][i]) {
chs.push_back(s[0][i]);
pos.push_back(i);
}
}
vector<int> ord(mx);
iota(ord.begin(), ord.end(), 0);
string ans = s[0];
vector<int> dpos;
do {
for (int i = 0; i < mx; i++) {
ans[pos[ord[i]]] = chs[i];
}
bool f = 1;
for (int i = 0; i < k; i++) {
dpos.clear();
for (int j = 0; j < n; j++) {
if (ans[j] != s[i][j]) {
dpos.push_back(j);
}
}
int sz = dpos.size();
if (sz > 2 || sz == 1) {
f = 0;
break;
}
if (sz == 0) {
if (has_same) {
continue;
} else {
f = 0;
break;
}
}
if (ans[dpos[0]] != s[i][dpos[1]] || ans[dpos[1]] != s[i][dpos[0]]) {
f = 0;
break;
}
}
if (f) {
cout << ans << '\n';
return;
}
} while (next_permutation(ord.begin(), ord.end()));
cout << "-1\n";
}
int main() {
int t = 1;
// cin >> t;
while (t--) {
solve();
}
return 0;
}
标答做法
标答做法是 $O(n ^ 2 k)$ 的。
先统计每个串和 $s_0$ 之间不同的位置。
直接暴力枚举交换 $s_0$ 中的要交换的两个位置。看这组交换之后对 $k$ 个串不同位置的影响。如果修复到了 $2$ 个或 $0$ 个且有重复字母则成立。
Next: [CF] E. Cheap Dinner - Educational Codeforces Round 104 (Rated for Div. 2)