Hash做题记录
本人由于 \(\texttt{hash}\) 太菜，所以有了这个东西。
T1 互斥的数
link
分析题目，求两两不互斥的最大子集。换句话说，就是删除互斥的元素。
考虑贪心，将数组从小到大排序。
如果 \(a_i\) 与 \(a_j\) 是互斥的，这两个数当中必须要删掉一个。显然删掉 \(a_j\) 是更划算的，因为 \(a_i\) 只是影响到了 \(a_j\) ，而 \(a_j\) 还会影响 \(p × a_j\) 。
由于 \(a_i\) 的值很大，所以我们用 \(\texttt{hash}\) 维护即可。
点击查看代码
#include
using namespace std;
const int P = 1e8 + 7, p = 31;
int n, k;
int a[100005], ans;
bool b[P + 5];
int get_hash(int x) {
return (p + x) % P;
}
signed main() {
scanf("%d %d", &n, &k);
for (int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
}
sort(a + 1, a + n + 1);
for (int i = 1; i <= n; i++) {
if (!b[get_hash(a[i])]) {
ans++;
b[get_hash(a[i] * k)] = true;
}
}
printf("%d", ans);
return 0;
}
T2 Power Strings
link
再来一道模板题吧。
一道字符串 \(\texttt{hash}\) 。
我们可以利用 \(\texttt{hash}\) 的一个特点：当知道整个字符串的 \(\texttt{hash}\) 值时，就可以在 \(\mathcal{O} (1)\) 的时间负责度内算出其字串的 \(\texttt{hash}\) 值。
然后将原字符串进行拆分，使拆分出来的子字符串 \(\texttt{hash}\) 值相等即可。
双倍经验：link
点击查看代码
#include
#include
#include
#define int unsigned long long
using namespace std;
const int base = 17;
int n;
char op[1000005];
int Hash[1000005], Pow[1000005];
void get_hash(char c[]) {
int len = strlen(c + 1);
for (int i = 1; i <= len; i++) {
Hash[i] = Hash[i - 1] * base + c[i];
}
}
int ans;
int get(int l, int r) {
return Hash[r] - Hash[l - 1] * Pow[r - l + 1];
}
signed main() {
Pow[1] = base;
for (int i = 2; i <= 1000000; i++) Pow[i] = Pow[i - 1] * base;
ios::sync_with_stdio(false);
while (cin >> op + 1) {
if (op[1] == '.') break;
get_hash(op);
int len = strlen(op + 1);
for (int i = 1; i <= len; i++) {
if (len % i != 0) continue;
int p1 = get(1, i);
bool f = true;
for (int j = i + 1; j <= len; j += i) {
int t = get(j, j + i - 1);
if (t != p1) {
f = false;
break;
}
}
if (f) {
printf("%d\n", len / i);
break;
}
}
}
return 0;
}