P13810 [CERC 2022] Differences 题解

· · 题解

题解区怎么空空如也。

哈希的一种方式是集合哈希（可以是可重集），具体方式是将集合的每一种数都映射成在一个大的范围内随机的一个数，集合的哈希值就是每种数的映射值乘上出现次数。

回到此题，思考与其它串的编辑距离为 k 等价于什么。

对每个位置，都会有一个与当前字符串这一位不同的字符串集合，每一位的集合的并加上 k 个自己等于 \{1,2,\cdots,n\} \times k 就等价于与其它串的编辑距离为 k。

因为字符集大小只有 4，所以上述的东西直接拿数组存一下，最后 check 每个字符串即可。

#include <bits/stdc++.h>
#define lowbit(o) o & -o
#define pb push_back
#define x first
#define y second
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;
const int N = 100005;
const int mod = 998244353;
const int inf = 0x3f3f3f3f;
const LL INF = 2e18;
int n, m, k;
string a[N];
mt19937 rnd(time(0));
LL w[N], sum[N][4];
void work()
{
    cin >> n >> m >> k;
    for (int i=0;i<n;i++)
        w[i] = rnd();
    vector<char> row(m);
    for (int i=0;i<n;i++)
        cin >> a[i];
    for (int j=0;j<m;j++)
        for (char c='A';c<='D';c++)
            for (int i=0;i<n;i++)
                if (a[i][j] != c)
                    sum[j][c - 'A'] += w[i];
    LL all = 0;
    for (int i=0;i<n;i++)
        all += w[i] * k;
    int ans = 0;
    for (int i=0;i<n;i++)
    {
        LL res = 0;
        for (int j=0;j<m;j++)
            res += sum[j][a[i][j] - 'A'];
        if (res + w[i] * k == all)
        {
            cout << i + 1;
            return;
        }
    }
}
signed main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int _T = 1;
    //cin >> _T;
    while (_T--)
        work();
    return 0;
}