[关闭]
@xzyxzy 2018-07-11T08:07:48.000000Z 字数 2232 阅读 466

哈希

字符串

作业部落

评论地址


一、概述

百度百科:
散列表(Hash table/哈希表),是根据关键码值(Key value)而直接进行访问的数据结构。

哈希表常用于比较两个字符串是否相同(可以把状态看作字符串,从而比较状态是否相同)

二、实现方式

一个例子

通常将其看成一个进制数,比如看成,那么哈希值就是可以自由决定,如果说状态量有限,可以使用较小的使得所有状态不冲突,若状态量较大且分散,可以采用取模或者自然溢出的方式尽可能避免冲突

优缺点

优点是可以比较(数组是如果用map就要加一个
缺点是会有冲突,为避免冲突可以选择双哈希或三哈希等(选取不同的模数)

哈希方式

1.进制哈希(用于判断状态/数组是否相同)

优点:方便好写
   状态量小时哈希过程可逆(见一双木棋
缺点:毒瘤出题人卡自然溢出,采用双哈希
   状态量大时哈希过程不可逆(不能通过Hash值还原数组)
使用范围:基本上这么写

2.树哈希(用于判断树的同构)

其实没有一定要求这么写,只是树的同构要求深度相同,孩子也同构但是与孩子的顺序无关,所以信息就是儿子的和深度和大小,可以灵活处理

千古神犇陈菊开安利的一种写法:

注意:base的选取原则是使得Hash值尽可能分散,尽可能少的冲突
优点:这里不用累乘而用异或和,使得Hash过程可逆(也就是在树DP中方便换根/删点
缺点:没有固定套路,灵活多变(有次考试不管怎么调总是过不了,把异或和改成累乘马上就过了,原因是数据范围小,Hash值密集容易造成冲突)

三、题单

四、代码

  1. // [九省联考2018]一双木棋chess
  2. #include<iostream>
  3. #include<cstdio>
  4. #include<cstdlib>
  5. #include<map>
  6. #define ll long long
  7. using namespace std;
  8. int N,M,A[11][11],B[11][11],b[11];
  9. map<ll,int>Map;
  10. ll HASH()
  11. {
  12. ll Hash=0;
  13. for(int i=1;i<=N;i++) Hash=Hash*11+b[i];
  14. return Hash;
  15. }
  16. void ReHash(ll Hash)
  17. {
  18. for(int i=N;i>=1;i--) b[i]=Hash%11,Hash/=11;
  19. }
  20. int DFS(int op,ll Hash)
  21. {
  22. if(Map[Hash]) return Map[Hash]==-1?0:Map[Hash];
  23. ReHash(Hash);int ans=1e9*(-op);
  24. for(int i=1;i<=N;i++)
  25. if(b[i]<b[i-1])
  26. {
  27. b[i]++;int tmp=DFS(-op,HASH());
  28. if(op==1) ans=max(ans,tmp+A[i][b[i]]);
  29. else ans=min(ans,tmp-B[i][b[i]]);
  30. b[i]--;
  31. }
  32. if(ans==1e9*(-op)) ans=0;
  33. Map[Hash]=(ans==0?-1:ans);
  34. return ans;
  35. }
  36. int main()
  37. {
  38. scanf("%d%d",&N,&M);
  39. for(int i=1;i<=N;i++)
  40. for(int j=1;j<=M;j++)
  41. scanf("%d",&A[i][j]);
  42. for(int i=1;i<=N;i++)
  43. for(int j=1;j<=M;j++)
  44. scanf("%d",&B[i][j]);
  45. b[0]=M;
  46. printf("%d\n",DFS(1,0));
  47. return 0;
  48. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注