题解 CF514C 【Watto and Mechanism】

Juanzhang · 2018-07-19 10:34:26 · 题解

思路：

• hash ： 读入时将所有满足题意的字符串hash放入set

@ZJQ90202 巨佬已经说得很清楚了，此题可以用Trie。就让我来发一个hash的题解吧。

当时以为能过

二、 双hash + unsigned long long + unsigned int 自然溢出

• WA$ $on$ $test$ $27

悲剧，就只多过了一个测试点

三、 hash + 10^9+7 大质数取模

• WA$ $on$ $test$ $16

没有料到emm，此题数据真的毒瘤

四、 hash + 10^9+7 + 10^9+9 孪生质数、大质数取模

• AC

终于过了emm

AC苦旅

我这只小蒟蒻已经卒了

代码

• 双hash + unsigned long long + unsigned int 自然溢出

#include <bits/stdc++.h>
using namespace std;

typedef unsigned long long ull;
typedef unsigned int ui;
typedef pair <ui, ull> puu;
const int maxn = 6e5 + 10;
int n, m;
ui pow1[maxn];
ull pow2[maxn];
char str[maxn];

set <puu> s;

ui hash1(char* str) {
    ui res = 0;
    for (int i = 0; i < strlen(str); i++) {
        res = (res << 1) + res + (str[i] - 'a');
    }
    return res;
}

ull hash2(char* str) {
    ull res = 0;
    for (int i = 0; i < strlen(str); i++) {
        res = (res << 1) + res + (str[i] - 'a');
    }
    return res;
}

int main() {
    pow1[0] = pow2[0] = 1;
    for (int i = 1; i <= 6e5; i++) {
        pow1[i] = (pow1[i - 1] << 1) + pow1[i - 1];
        pow2[i] = (pow2[i - 1] << 1) + pow2[i - 1];
    }
    scanf("%d %d", &n, &m);
    gets(str);
    for (int i = 1; i <= n; i++) {
        gets(str);
        ui t1 = hash1(str);
        ull t2 = hash2(str);
        int len = strlen(str);
        for (int j = 0; j < len; j++) {
            for (int k = 0; k < 3; k++) {
                if (k != str[j] - 'a') {
                    s.insert(make_pair(t1 - (pow1[len - j - 1] * (str[j] - 'a')) + (pow1[len - j - 1] * k), t2 - (pow2[len - j - 1] * (str[j] - 'a')) + (pow2[len - j - 1] * k)));
                }
            }
        }
    }
    for (; m--; ) {
        gets(str);
        puts(s.count(make_pair(hash1(str), hash2(str))) ? "YES" : "NO");
    }
    return 0;
}

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair <ll, ll> pll;
const ll mod1 = 1e9 + 7;
const ll mod2 = 1e9 + 9;
const int maxn = 6e5 + 10;
int n, m;
char str[maxn];
ll pow1[maxn], pow2[maxn];

set <pll> s;

ll hash1(char* str) {
    ll res = 0;
    for (int i = 0; i < strlen(str); i++) {
        res = ((res << 1) + res + str[i] - 'a') % mod1;
    }
    return res;
}

ll hash2(char* str) {
    ll res = 0;
    for (int i = 0; i < strlen(str); i++) {
        res = ((res << 1) + res + str[i] - 'a') % mod2;
    }
    return res;
}

int main() {
    pow1[0] = pow2[0] = 1;
    for (int i = 1; i <= 6e5; i++) {
        pow1[i] = ((pow1[i - 1] << 1) + pow1[i - 1]) % mod1;
        pow2[i] = ((pow2[i - 1] << 1) + pow2[i - 1]) % mod2;
    }
    scanf("%d %d", &n, &m);
    gets(str);
    for (int i = 1; i <= n; i++) {
        gets(str);
        int len = strlen(str);
        ll t1 = hash1(str), t2 = hash2(str);
        for (int j = 0; j < len; j++) {
            for (int k = 'a'; k <= 'c'; k++) {
                if (k != str[j]) {
                    s.insert(make_pair((t1 + (pow1[len - j - 1] * (k - str[j])) + (mod1 << 1) + mod1) % mod1, (t2 + (pow2[len - j - 1] * (k - str[j])) + (mod2 << 1) + mod2) % mod2));
                }
            }
        }
    }
    for (; m--; ) {
        gets(str);
        puts(s.count(make_pair(hash1(str), hash2(str))) ? "YES" : "NO");
    }
    return 0;
}