1.P1102 A-B 数对

#include<stdio.h>
long long int a[1000000],sum;
struct node
{long long int wei,ci;//这个位置对应的数，这个数出现了几次
}h[1000000];long long int hash(long long int x)//存入散列表的函数 
{long long int key;key=x%1000001;return key;
}long long int find(long long int x)//找到x的位置
{int y;y=hash(x);while(h[y].wei&&h[y].wei!=x)//冲突时，用开放定址法 {y++;y=hash(y);}return y;
}int main()
{long long int n,c;scanf("%lld%lld",&n,&c);for(long long int i=1;i<=n;i++)//将数据存入散列表{scanf("%lld",&a[i]);h[find(a[i])].wei=a[i];h[find(a[i])].ci++;}for(long long int i=1;i<=n;i++){sum=sum+h[find(a[i]-c)].ci;//统计个数在散列表中出现的次数}printf("%lld",sum);//输出return 0;
}

题解:题目要求求出A-B=C,可以转换为B=A-C（因为C的值时是恒定不变的，不妨一边放置一个变量），之后将所有输入的数存入散列表，出现相同的数就记其出现次数加1，之后一旦出现满足B=A-C（例如输入样例中3=2-1）的情况就在统计结果上记录其出现次数（加到sum里）。

2.P3370 【模板】字符串哈希

#include<stdio.h>
#include<string.h>
int len[2000];//记录当前长度的字符串有几个（len[10]存的就是长度为10的字符串） 
int wei[10000][10000];//记录字符存入散列表后的位置 
int hash1[10000],hash2=0;
char s[10000][10000];//存输入的字符串 
int main()
{int sum,n;scanf("%lld",&n);for(int i=1;i<=n;i++){scanf("%s",s[i]);int slen;slen=strlen(s[i]);len[slen]++;//记录当前长度字符串的数组++wei[slen][len[slen]]=i;//长度为ln的字符串记录下位置for(int j=1;j<=slen;j++){int A;A=s[i][j]-'0';hash2=hash2*10000+A;}hash1[i]=hash2;//记录下每个串的值k以便后续遇到长度一样的时候进行判断 for(int j=1;j<len[slen];j++)//对每个与当前字符串长度相同字符串开始检验 {if(hash1[wei[slen][j]]==hash2)//如果找到hash值相同的，那就是一样的字符串{sum++;break;}}hash2=0;//hash值清零以便对下一个输入的字符串进行处理 }printf("%lld",n-sum);//用输入的的减去重复的就得到一共有几种 return 0;
}

题解：对于输入的字符串，首先对其长度进行判断，并将其存入对应的2维字符串中，同时，记录该长度字符串数量的数组+1（如存入了一个长度为3的字符串后，len[3]+1），存入后，对字符串进行其hash值的判断，长度不一样的肯定不是同一字符串，长度一样的就对其hash值进行判断，hash值一样肯定就是同一字符串，将出现的（相同字符串）的情况进行统计，输入数量减去重复数量就是字符串的种类数。

3.P2957 [USACO09OCT]Barn Echoes G

#include<stdio.h>
#include<string.h>
char s1[81],s2[81];
int x,y;
int len1,len2;
int main()
{int sum;scanf("%s",s1);scanf("%s",s2);len1=strlen(s1);len2=strlen(s2);for(int i=0;i<len1;i++){for(int j=i;j>=0;j--){if(s1[j]!=s2[len2-1-i+j]){x=1;break;}}if(x==0){y=i;if(sum>y){sum=sum;}else{sum=y;}}x=0;}for(int i=0;i<len2;i++){for(int j=i;j>=0;j--){if(s2[j]!=s1[len1-1-i+j]){x=1;break;}}if(x==0){y=i;if(sum>y){sum=sum;}else{sum=y;}}x=0;}printf("%d",sum+1);
}

题解：输入的字符串分为两类：输出的（s1）和反射回的（s2），处理分为两轮，第一轮是从输出的第一个字符开始，同时从反射回的倒数第一个字符开始找，同时依次推进（s1向后推，s2向前推),每扫到一个一样的就将储存重复长度的变量（sum）+1，一旦发现不同的字符，就将变量（x）设置为1以表示后续再扫到相同的字符也不再计入重复长度，第二轮是从输出的倒数第一个字符开始，同时从反射回的第一个字符开始找，大致过程相同，最后保留最大的重复长度并输出。

4.P2580 于是他错误的点名开始了

#include<bits/stdc++.h>
using namespace std;
map<string,int>a;
int main()
{int n,m;char s1[51];scanf("%d",&n);for(int i=0;i<n;i++){scanf("%s",s1);a[s1]=1;}scanf("%d",&m);for(int i=0;i<m;i++){scanf("%s",s1);if(a[s1]==1){printf("OK\n");a[s1]++;}else if(a[s1]!=1){if(a[s1]==2){printf("REPEAT\n");}else{printf("WRONG\n");}}}return 0;
}

题解：基础的STL中的map应用，输入的字符串映射数组中的数，在第一轮输入的字符串所映射的数定为1，在第二轮输入的字符串中，判断其映射的数，若是1，做输出OK，表示正确，并将其映射的数改为2，若是2，则输出REPEAT表示重复点名，若既非1也非2，则表示第一轮输入时没有这个字符串，输出WRONG。

5.P3375 【模板】KMP字符串匹配

#include<stdio.h>
#include<string.h>
int s1len,s2len;
char s1[1000002],s2[1000002];
int next[1000002],next1;
int main()
{scanf("%s",s1+1);scanf("%s",s2+1);s1len=strlen(s1+1);s2len=strlen(s2+1);for(int i=1;i<=s2len;i++)//求s2的next数组值 {     if(i==1){next[i]=0;}else{while(next1!=0&&s2[i]!=s2[next1+1]){next1=next[next1];}if(s2[next1+1]==s2[i]){next1++;next[i]=next1;} 	}}next1=0;//归零以便下步对s1进行处理 for(int i=1;i<=s1len;i++){while(next1!=0&&s1[i]!=s2[next1+1]){next1=next[next1];}if(s2[next1+1]==s1[i]){next1++;}if(next1==s2len)//此时出现匹配的位置 {printf("%d\n",i-s2len+1);next1=next[next1];}}for(int i=1;i<=s2len;i++)//依次输出border{printf("%d ",next[i]);}return 0;
}

题解：KMP模板题，对于s1和s2是否匹配的问题，先求出s2的next值，之后按照next值依次对s1进行匹配，匹配长度(next1）等于s2的长度时，s2头部所在s1的位置即为匹配开始的位置，border值实际上就是s2的next值，依次输出即可。

6.CF1200E Compress Words

#include<bits/stdc++.h>
using namespace std;
char s1[10000010],s2[10000010];
int s1len,s2len,len;
int nex[10000010];
int main()
{int n;scanf("%d",&n);for(int i=1;i<=n;++i){scanf("%s",s2+1);s2len=strlen(s2+1);if(s1len>s2len){len=s2len;}else{len=s1len;}string s3;s3+='\0';for(int i=1;i<=len;i++){s3+=s2[i];}s3+='!';for(int i=s1len-len+1;i<=s1len;i++){s3+=s1[i];}for(int i=0;i<=len*2+1;++i){nex[i]=0;}int j=0;for(int i=2;i<=len*2+1;i++){while(j&&s3[j+1]!=s3[i]){j=nex[j];}if(s3[j+1]==s3[i]){++j;}nex[i]=j;}for(int i=nex[len*2+1]+1;i<=s2len;i++){s1[++s1len]=s2[i];}}puts(s1+1);return 0;
}

题解:对于输入的一整句话，每一个单词都看做一个单独的字符串，首先找到第一个字符串的后缀和第二个字符串前缀中重合的部分拼接为一个新的字符串（s1)  ，在对下一个单词进行判断时，一定是要用s1与后续字符串（单词）相比较，且为了防止求出的长度超过原长度，要在隔开的字符串之间加入特殊符号来隔开。