首页 > 代码库 > csu 2014 summer trainning day 1 哈希
csu 2014 summer trainning day 1 哈希
POJ 1200
题意：给定串s，串中不同字符数nc，所求子串长度n，求长度为n的不同的子串的个数
分析：处理长度很短的字符串哈希，数据保证可以无冲突存储下来，利用hash思想快速查询以前便利的结果，关键在于优化搜索。
code：
1 #include <iostream> 2 #include <string.h> 3 #include <stdio.h> 4 #include <set> 5 using namespace std; 6 7 int c[270]; 8 bool Hash[13000000]; 9 char s[1000100];10 int d,l;11 void init(int len){12 memset(c,0,sizeof(c));13 memset(Hash,0,sizeof(Hash));14 int cnt=0;15 for(int i=0;i<len;i++){16 if (c[s[i]]==0){17 c[s[i]]=++cnt;18 }19 if (cnt==d) break;20 }21 return ;22 }23 void solve(int len){24 int ans=0;25 int v=0;26 int p=1;27 for(int i=1;i<l;i++) p*=d;28 for(int i=0;i<l;i++){29 v=v*d+c[s[i]];30 }31 Hash[v]=true;32 ans++;33 for(int i=l;i<len;i++){34 v=(v-c[s[i-l]]*p)*d+c[s[i]];35 if (!Hash[v]){36 ans++;37 Hash[v]=true;38 }39 }40 printf("%d\n",ans);41 return ;42 }43 int main(){44 while(~scanf("%d%d",&l,&d)){45 scanf("%s",s);46 int len=strlen(s);47 init(len);48 solve(len);49 }50 return 0;51 }
POJ 1635
题意：给定一棵有根树的最小表示，即便利的结果，远离树根表示0，靠近树根表示1，给定两串不同便得到的01序列，判断两棵树是否是同构的。
分析：1、判断树同构的方法，统计F(x)，表示子节点数为x的节点的个数，若两个树的F(x)在定义域内是完全相等的，则两棵树同构。
2、分析01串：在纸上举几个例子，就能得到规律。便利的结果是满足栈的结构的，所以处理出每个节点在串中出现（一个0，一个1）的两个位置，
那么这两个位置对应的节点的子节点的个数就是，字符串中这两个位置夹的0（或1）的个数。预处理O(n),统计O(n)
code:
1 #include <iostream> 2 #include <string.h> 3 #include <stdio.h> 4 #include <set> 5 #include <stack> 6 using namespace std; 7 8 int t; 9 char s1[3010],s2[3010];10 int px1[3010],py1[3010];11 int px2[3010],py2[3010];12 int num1[3010],num2[3010];13 int cnt1,cnt2,len;14 int S[3010],p;//手动开的栈15 bool check(){16 memset(num1,0,sizeof(num1));17 memset(num2,0,sizeof(num2));18 for(int i=1;i<=cnt1;i++){19 int x=px1[i];20 int y=py1[i];21 int c=0;22 for(int i=x+1;i<y;i++){23 if (s1[i]==‘0‘) c++;24 }25 num1[c]++;26 }27 for(int i=1;i<=cnt2;i++){28 int x=px2[i];29 int y=py2[i];30 int c=0;31 for(int i=x+1;i<y;i++){32 if (s2[i]==‘0‘) c++;33 }34 num2[c]++;35 }36 for(int i=0;i<=cnt2;i++){37 if (num1[i]!=num2[i]) return false;38 }39 return true;40 }41 void solve(){42 len=strlen(s1);43 if (len!=(int)strlen(s2)){44 puts("different");45 return ;46 }47 cnt1=0;p=0;48 for(int i=0;i<len;i++){49 if(s1[i]==‘0‘){50 S[++p]=++cnt1;51 px1[cnt1]=i;52 }53 if (s1[i]==‘1‘){54 py1[S[p--]]=i;55 }56 }57 //// for(int i=1;i<=cnt1;i++){58 //// cout<<px1[i]<<" "<<py1[i]<<endl;59 //// }60 cnt2=0;p=0;61 for(int i=0;i<len;i++){62 if(s2[i]==‘0‘){63 S[++p]=++cnt2;64 px2[cnt2]=i;65 }66 if (s2[i]==‘1‘){67 py2[S[p--]]=i;68 }69 }70 if (cnt1!=cnt2) {71 puts("different");72 return ;73 }74 if (check()){75 puts("same");76 }else puts("different");77 78 return ;79 }80 int main(){81 scanf("%d",&t);82 while(t--){83 scanf("%s",s1);84 scanf("%s",s2);85 solve();86 }87 return 0;88 }
POJ 1971
题意：给定1000个二维坐标节点，判断这些节点能构成的平行四边形有多少个。坐标范围<=1000000000
分析：数学知识是必要的，不然很难想到很快的搜索办法（反正开始时我没有），即平行四边形的两对对顶点的的中点是重合的。
那么，若存在两个重合的中点，那么这两条边交叉起来能构成一个平行四边形。
那么我们O(n^2)枚举任意两个点，处理出他们的中点（处理成整数，不除2）。
得到n^2/2个中点的我们现在要能快速找找到对于每种中点有几个是相等的。这道题不使用hash，排序后，成段扫描处理即可，当然，Hash更快。
1 #include <iostream> 2 #include <queue> 3 #include <string.h> 4 #include <stdio.h> 5 #include <algorithm> 6 using namespace std; 7 8 int t,n; 9 int x[1100],y[1100];10 struct N{11 int x,y;12 bool operator <(const N&X)const{13 if (x==X.x) return y<X.y;14 else return x<X.x;15 }16 bool operator==(const N&X)const{17 return x==X.x&&y==X.y;18 }19 20 }Ps[1100000];21 void print(int cnt){22 for(int i=0;i<cnt;i++){23 cout<<"("<<Ps[i].x<<","<<Ps[i].y<<")"<<endl;24 }25 }26 int cnt;27 int main(){28 scanf("%d",&t);29 while(t--){30 scanf("%d",&n);31 for(int i=0;i<n;i++){32 scanf("%d%d",&x[i],&y[i]);33 }34 cnt=0;35 for(int i=0;i<n-1;i++){36 for(int j=i+1;j<n;j++){37 Ps[cnt++]=(N){x[i]+x[j],y[i]+y[j]};38 }39 }40 sort(Ps,Ps+cnt);41 long long ans=0;42 int k=1;43 for(int i=1;i<cnt;i++){44 if (Ps[i]==Ps[i-1]){45 k++;46 }else{47 ans=ans+(long long)k*(k-1)/2;48 k=1;49 }50 }51 printf("%I64d\n",ans);52 }53 return 0;54 }
POJ 2002
题意：给定1000个二维坐标节点，判断它们能构成多少个正方形。
分析：1、不造为什么用上一题类似的方法会错？？？当然，要满足两个垂直一个重合
2、首先所有点(X^2+Y^2)%Mod哈希存一遍code
3、用到数学知识：
Point A=(Point){x[i]-y[i]+y[j],y[i]+x[i]-x[j]};Point B=(Point){x[j]-y[i]+y[j],y[j]+x[i]-x[j]};Point C=(Point){x[i]+y[i]-y[j],y[i]-x[i]+x[j]};Point D=(Point){x[j]+y[i]-y[j],y[j]-x[i]+x[j]};
枚举两点，公式求出另外两点，Hash查找这些点是否在图上，统计出个数，用组合数学即可处理
code：
1 #include <iostream> 2 #include <queue> 3 #include <string.h> 4 #include <stdio.h> 5 #include <algorithm> 6 #define Mod 49999 7 using namespace std; 8 struct Point{ 9 int x,y;10 int k;11 bool operator==(const Point&X){12 return x==X.x&&y==X.y;13 }14 };15 vector<Point>G[Mod+100];16 17 void init(){18 for(int i=0;i<Mod+10;i++) G[i].clear();19 }20 21 int Hash(Point P){22 return (P.x*P.x+P.y*P.y)%Mod;23 }24 25 int findx(Point P){26 int ha=Hash(P);27 int i;28 for(i=0;i<G[ha].size();i++){29 if (G[ha][i]==P) break;30 }31 if (i==G[ha].size()) return 0;32 return G[ha][i].k;33 }34 void Insert(Point P){35 int ha=Hash(P);36 int i;37 for(i=0;i<G[ha].size();i++){38 if (G[ha][i]==P) {39 G[ha][i].k++;40 break;41 }42 }43 if (i==G[ha].size()){44 G[ha].push_back((Point){P.x,P.y,1});45 }46 return ;47 }48 49 int n;50 int x[1100],y[1100];51 int main(){52 while(~scanf("%d",&n)&&n){53 init();54 for(int i=0;i<n;i++){55 scanf("%d%d",&x[i],&y[i]);56 Insert((Point){x[i],y[i],0});57 }58 int ans=0;59 for(int i=0;i<n-1;i++){60 for(int j=i+1;j<n;j++){61 Point A=(Point){x[i]-y[i]+y[j],y[i]+x[i]-x[j]};62 Point B=(Point){x[j]-y[i]+y[j],y[j]+x[i]-x[j]};63 Point C=(Point){x[i]+y[i]-y[j],y[i]-x[i]+x[j]};64 Point D=(Point){x[j]+y[i]-y[j],y[j]-x[i]+x[j]};65 int k1=findx(C);66 int k2=findx(D);67 int k3=findx(A);68 int k4=findx(B);69 ans+=(k1*k2)+(k3*k4);70 }71 }72 ans=ans/4;73 printf("%d\n",ans);74 }75 return 0;76 }
POJ 2549
题意：给定一集合S，给定集合中的所有数，统计A+B+C=D的个数，A、B、C、D皆取自S，且是各不相同的元素。集合的元素的个数<=1000
分析: 类似白书上的中途相遇法，等式可以这样看，A+B=D-C，两两枚举，Hash存储，再两两枚举D，A，统计即可。注意存的时候，要保留A、B，
因为A、B、C、D要不相同，所以要判断。
code：
1 #include <iostream> 2 #include <queue> 3 #include <string.h> 4 #include <stdio.h> 5 #include <algorithm> 6 #include <vector> 7 #define Mod 49999 8 9 using namespace std;10 struct Node{11 int add,a1,a2;12 };13 vector<Node>G[Mod+100];14 void init(){15 for(int i=0;i<Mod+10;i++) G[i].clear();16 }17 void Insert(int k,int b1,int b2){18 int key=k;19 while(key<0) key=key+Mod;20 key=key%Mod;21 int i;22 for(i=0;i<G[key].size();i++){23 int add=G[key][i].add;24 int a1=G[key][i].a1;25 int a2=G[key][i].a2;26 if (add == k && (a1+a2==b1+b2) && (a1-a2==b1-b2)) break;27 }28 if (i==G[key].size()) G[key].push_back(Node{k,b1,b2});29 return ;30 }31 bool Search(int d,int c){32 int key=d-c;33 while(key<0) key=key+Mod;34 key=key%Mod;35 int i;36 for(i=0;i<G[key].size();i++){37 int add=G[key][i].add;38 int a1=G[key][i].a1;39 int a2=G[key][i].a2;40 if (add==d-c && a1!=d && a2!=d && a1!=c && a2!=c) return true;41 }42 return false;43 }44 int a[1010];45 int n;46 int main(){47 while(~scanf("%d",&n)&&n){48 init();49 for(int i=0;i<n;i++) scanf("%d",&a[i]);50 for(int i=0;i<n-1;i++){51 for(int j=i+1;j<n;j++){52 Insert(a[i]+a[j],a[i],a[j]);53 }54 }55 int m=-536870913;56 for(int i=0;i<n-1;i++){57 for(int j=i+1;j<n;j++){58 if (Search(a[i],a[j])) m=max(m,a[i]);59 if (Search(a[j],a[i])) m=max(m,a[j]);60 }61 }62 if (m==-536870913) puts("no solution");63 else printf("%d\n",m);64 }65 return 0;66 }
列出一些Hash要用到的素数：
prime=997， prime=1999 ， prime=7993 ， prime=9973， prime=29989， prime=49999，prime=99991
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。