P3405. Cities and States S

考点

• 哈希函数

题解

#include <bits/stdc++.h>
using namespace std;
const int LEN = 23333, P = 131;
//拉链法处理冲突
//pair第一个元素保存字符串哈希值，第二个元素保存字符串哈希值出现的个数
vector<pair<int, int>> hsh[LEN];

int gethash(string a, string b)
{
    return (a[0] - 'A') * P * P * P + (a[1] - 'A') * P * P + (b[0] - 'A') * P + (b[1] - 'A');
}

void insert(int x)
{
    int idx = x % LEN;
    for (int i = 0; i < hsh[idx].size(); ++i)
    {
        //哈希表中存在该字符串哈希值，增加次数即可
        if (hsh[idx][i].first == x)
        {
            ++hsh[idx][i].second;
            return;
        }
    }
    //若不存在，新增
    hsh[idx].emplace_back(x, 1);
}

int find(int x)
{
    int idx = x % LEN;
    for (int i = 0; i < hsh[idx].size(); ++i)
    {
        if (hsh[idx][i].first == x)
            return hsh[idx][i].second;
    }
    return 0;
}

int main()
{
    int n;
    long long ans = 0;
    string a, b;
    cin >> n;
    while (n--)
    {
        cin >> a >> b;
        if (a[0] == b[0] && a[1] == b[1])
            continue;
        ans += find(gethash(b.substr(0, 2), a.substr(0, 2)));
        insert(gethash(a.substr(0, 2), b.substr(0, 2)));
    }
    cout << ans;
    return 0;
}

思路

输入城市+州，要你去找州+城市的字符串个数，手写哈希表并用拉链法处理冲突即可

哈希本身不难，看题解即可。下面着重讲一下重点：

去重

统计对数，一般都是离线操作，即统计完所有各类字符串的个数后，从头扫到尾

比如字符串ab有2个，字符串ba有3个，那么就有2 * 3 = 6对；但遇到字符串ba会再去寻找ab，重复计算

如果是在线操作，就不会重复了，相当于当前字符串与前面满足条件的字符串各组一次

比如有满足条件的字符串A和B，与之配对的有C和D

离线操作中，迭代到字符串A和B时，有A -- c、A -- D、B -- C、B -- D

迭代到字符串C和D时，又会重复C -- A、C -- B、D -- A、D -- B

所以直接在线操作就好，只留后者那一种情况

坑

假设有组合城市a、州b，城市c、州d

按照题目的要求，寻找a == d且b == c的一对组合进行配对

考虑一个满足条件的特例，如果a == b，此时a == d且a == c，那么b == d == a == c

然而题目说同一个州内不会有两个同名的城市，该特例虽满足配对条件，但与前提不符，应当删去

就是下面这段代码的由来：

if (a[0] == b[0] && a[1] == b[1])
            continue;