@xzyxzy
2018-07-11T16:07:48.000000Z
字数 2232
阅读 1412
字符串
百度百科:
散列表(Hash table/哈希表),是根据关键码值(Key value)而直接进行访问的数据结构。
哈希表常用于比较两个字符串是否相同(可以把状态看作字符串,从而比较状态是否相同)
通常将其看成一个进制数,比如看成,那么哈希值就是,可以自由决定,如果说状态量有限,可以使用较小的使得所有状态不冲突,若状态量较大且分散,可以采用取模或者自然溢出的方式尽可能避免冲突
优点是可以比较(数组是如果用map就要加一个)
缺点是会有冲突,为避免冲突可以选择双哈希或三哈希等(选取不同的模数)
1.进制哈希(用于判断状态/数组是否相同)
2.树哈希(用于判断树的同构)
千古神犇陈菊开安利的一种写法:
注意:base的选取原则是使得Hash值尽可能分散,尽可能少的冲突
优点:这里不用累乘而用异或和,使得Hash过程可逆(也就是在树DP中方便换根/删点)
缺点:没有固定套路,灵活多变(有次考试不管怎么调总是过不了,把异或和改成累乘马上就过了,原因是数据范围小,Hash值密集容易造成冲突)
// [九省联考2018]一双木棋chess
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<map>
#define ll long long
using namespace std;
int N,M,A[11][11],B[11][11],b[11];
map<ll,int>Map;
ll HASH()
{
ll Hash=0;
for(int i=1;i<=N;i++) Hash=Hash*11+b[i];
return Hash;
}
void ReHash(ll Hash)
{
for(int i=N;i>=1;i--) b[i]=Hash%11,Hash/=11;
}
int DFS(int op,ll Hash)
{
if(Map[Hash]) return Map[Hash]==-1?0:Map[Hash];
ReHash(Hash);int ans=1e9*(-op);
for(int i=1;i<=N;i++)
if(b[i]<b[i-1])
{
b[i]++;int tmp=DFS(-op,HASH());
if(op==1) ans=max(ans,tmp+A[i][b[i]]);
else ans=min(ans,tmp-B[i][b[i]]);
b[i]--;
}
if(ans==1e9*(-op)) ans=0;
Map[Hash]=(ans==0?-1:ans);
return ans;
}
int main()
{
scanf("%d%d",&N,&M);
for(int i=1;i<=N;i++)
for(int j=1;j<=M;j++)
scanf("%d",&A[i][j]);
for(int i=1;i<=N;i++)
for(int j=1;j<=M;j++)
scanf("%d",&B[i][j]);
b[0]=M;
printf("%d\n",DFS(1,0));
return 0;
}