哈希
前言
这周作业有点多呀然后就没什么时间学，加上一开始看的是LCS然后又啃不下，就晚了点发，感觉期末30篇的flag会打脸_(xз」∠)_
Hash思维，其实平时经常会用到，只是自己没有意识用到了而已，比如上学期在做“Anagram单词”的时候，舍友把单词中的各个字母*1000累加成一个值，通过这个值来判断，本质上就是Hash思维嘛
另外这次看Hash感觉比较不可思议的是，再次用到了图论！
还有是Hash本身很多可以用STL中的map代替，但是容易超时，就看题目想不想卡你
- Hash表
https://blog.csdn.net/duan19920101/article/details/51579136 - ELFhash
https://blog.csdn.net/ltyqljhwcm/article/details/52966874 - Hash字符串匹配
https://www.cnblogs.com/zyf0163/p/4806951.html - 素数表
https://blog.csdn.net/zhhx2001/article/details/52150810 - 为什么要余一个质数？
https://segmentfault.com/q/1010000000593741
Equations - HDU 1496
题目大意
给定a,b,c,d，问方程 ax1^2+bx2^2+cx3^2+dx4^2=0在x属于[-100,0)U(0,100]有多少种解？
思路
最朴素的思想当然是四重循环啦，O(n^4)稳稳的超时
然后比较容易想到的是先枚举一个x，这里用x4举栗子。先枚举dx4^2，然后结果存数组下标，值记录为true，然后三重循环查最后的-dx4^2是否存在，O(n^3)，超不超时没试过
本题用Hash可以优化到O(n^2)，枚举ax1^2+bx2^2然后因为范围太大了所以Hash，然后再枚举cx3^2+dx4^2查找有没有-(ax1^2+bx2^2)在表中，统计答案就可以了
另外本题有个小技巧，可以枚举[1,100]，最后的答案为 16*ans，因为平方嘛
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = (int)1e5;
const int M = 50;
const int MOD = 1 << 15;
struct edge{
int val;
int cnt;
int next;
};
edge e[MOD<<1];
int tot;
int head[MOD<<1];
void init(){
memset(head, -1, sizeof(head));
tot = 0;
}
void hashInsert(int val){
int u = val%MOD + MOD; //+MOD是因为有负数
for(int i = head[u]; ~i; i = e[i].next){
if(e[i].val == val){
e[i].cnt++;
return;
}
}
e[tot].cnt = 1; //和图论中的加边代码是一样的，毕竟是简易版链表
e[tot].val = val;
e[tot].next = head[u];
head[u] = tot++;
}
int hashFind(int val){
int u = val%MOD + MOD;
for(int i = head[u]; ~i; i = e[i].next){
if(e[i].val == val) return e[i].cnt;
}
return 0;
}
int main(){
int a, b, c, d;
while(~scanf("%d%d%d%d", &a, &b, &c, &d)){
init();
int sum = 0;
for(int x = 1; x <= 100; x++){
for(int y = 1; y <= 100; y++){
hashInsert(a*x*x + b*y*y);
}
}
for(int x = 1; x <= 100; x++){
for(int y = 1; y <= 100; y++){
sum += hashFind(-c*x*x - d*y*y);
}
}
printf("%d\n", sum << 4);
}
}
Negative and Positive (NP) - HDU-5183
题目大意
给定数组a和数字k，求是否存在任意的a[i]−a[i+1]+a[i+2]+⋯+(−1)^(j−i)a[j]使得其结果等于k
思路
在51NOD做过类似的题然后完全没有意识，自己太菜 _(:_」∠)_
可以记录前缀和，那么这时方程化为 sum[j] - sum[i - 1] = k (i为奇数) 或者 -(sum[j] - sum[i - 1]) = k (i为偶数)，如果双重循环照样超时
可将方程化继续化为sum[j] = k + sum[i - 1] (i为奇数) 或者 sum[j] = -k + sum[i - 1] (i为偶数)，这时候就可以先求出前缀和sum[i]然后hash，再循环一遍查找是否存在值 k + sum[i - 1] (i为奇数) 或者 sum[j] = -k + sum[i - 1] (i为偶数)
此处hash的原因还是因为范围太大，需要缩小范围再存入数组，记得hash时还要存入前缀和当前i的位置，查找的时候还要满足j >= i
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <map>
using namespace std;
const int N = (int)1e6 + (int)1e5;
const int MOD = 999983;
typedef long long ll;
struct edge{
ll val, pos, next;
};
edge e[N];
int head[N << 1];
int tot;
ll a[N];
inline void init(){
memset(head, -1, sizeof(head));
memset(a, 0, sizeof(a));
tot = 0;
}
inline void hashInsert(ll val, int pos){
int u = val%MOD + MOD;
e[tot].val = val;
e[tot].pos = pos;
e[tot].next = head[u];
head[u] = tot++;
}
bool hashFind(ll val, int pos){
int u = val%MOD + MOD;
for(int i = head[u]; ~i; i = e[i].next){
if(e[i].val == val && e[i].pos >= pos) return true;
}
return false;
}
int main(){
int t;
int caseno = 1;
scanf("%d", &t);
while(t--){
init();
int n;
ll k;
bool flag = false;
scanf("%d%lld", &n, &k);
for(int i = 1; i <= n; i++){
scanf("%lld", &a[i]);
if(i&1){
a[i] = a[i - 1] + a[i];
}else{
a[i] = a[i - 1] - a[i];
}
hashInsert(a[i], i);
}
for(int i = 1; i <= n && (!flag); i++){
if(i&1){
flag = hashFind(a[i - 1] + k, i);
}else{
flag = hashFind(a[i - 1] - k, i);
}
}
printf("Case #%d: ", caseno++);
if(flag){
puts("Yes.");
}else{
puts("No.");
}
}
return 0;
}
Flying to the Mars - HDU 1800
题目大意
士兵学骑扫帚，等级高的可以教等级低的，并且可以传递，比如给定士兵等级A>B>C=D>E，那么A教B,B教C，C教E他们共用一把扫帚，D只能再用一把扫帚，最少总共需要两把扫帚。现在给定士兵等级，求最少需要用几把扫帚
思路
本题求的是出现重复数字中重复数量的最大值，重点在于”less than 30 digits”，说明不能用unsigned long long存，得用字符串，那就得用hash了，注意去掉前导0,这里因为是要hash一个字符串所以选用比较简单的ELFHash，hash的时候顺便统计一下数量，维护数量最大值，hash完成输出就可以了
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <map>
using namespace std;
const int N = 3005;
const int MOD = 7003;
typedef long long ll;
struct edge{
int next;
int cnt;
char str[35];
};
edge e[N];
int head[MOD + 5];
int tot;
inline int ELFhash(char *str){ //具体看上面的博文
unsigned long val = 0;
unsigned long x;
while(*str){
val = (val << 4) + * str;
x = val & 0xf0000000;
if(x){
val ^= (x >> 24);
val &= ~x;
}
str++;
}
return val;
}
inline void init(){
memset(head, -1, sizeof(head));
tot = 0;
}
inline void hashInsert(char* str, int& ans){
while(*str == '0') str++; //去前导0
int u = ELFhash(str)%MOD + 1;
for(int i = head[u]; ~i; i = e[i].next){
char* vstr = e[i].str;
if(strcmp(vstr, str) == 0){
e[i].cnt++;
ans = max(ans, e[i].cnt);
return;
}
}
e[tot].cnt = 1;
ans = max(ans, 1);
strcpy(e[tot].str, str);
e[tot].next = head[u];
head[u] = tot++;
}
int main(){
int n;
char str[35];
while(~scanf("%d", &n)){
init();
getchar();
int ans = 0;
while(n--){
gets(str);
hashInsert(str, ans);
}
printf("%d\n", ans);
}
return 0;
}
Oulipo - POJ 3461
题目大意
给定W串，问其在T串中出现了几次
思路
这题之前用KMP算法做过，其实也可以用hash做，比较迷醉的就是不一定能对，因为hash值有小概率相同，万一错了怎么办？换个base值试试
具体原理看上面博文
个人不太清楚的是：就算溢出也能保证值相同？可以用数论结论推一下但是题目能过我就懒得推了
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <map>
#include <queue>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int N = 1e6 + 15;
const int MOD = 1 << 20;
const int M = 10005;
const ull base = 1e8 + 7;
ull p[N];
ull g[N];
char a[M], b[N];
inline void init(){
p[0] = 1;
for(int i = 1; i < N; i++) p[i] = p[i - 1] * base;
}
int main(){
init();
int t;
scanf("%d", &t);
while(t--){
scanf("%s%s", a + 1, b + 1);
int lena = strlen(a + 1), lenb = strlen(b + 1);
int ans = 0;
ull aval = 0;
g[lenb + 1] = 0;
for(int i = lena; i >= 1; i--){
aval = aval*base + (a[i] - 'A'); //W串的hash值，a[0] * base^0 + a[1] * base^1 + .....
}
for(int i = 1; i <= lenb; i++){
g[i] = g[i - 1] + (b[i] - 'A') * p[i - 1]; //T串前缀和的hash， g[i] = b[0] + b[1] * base^1 + ... + b[i] * base^i
}
for(int i = 1; i + lena - 1 <= lenb; i++){
int l = i, r = i + lena - 1;
ull bsval = g[r] - g[l - 1]; //在l到r区间的hash就为 g[r] - g[l - 1]
if(bsval == aval * p[l - 1]) ans++; //aval要乘上 p[l - 1]，对齐上面的区间
}
printf("%d\n", ans);
}
return 0;
}
