以下是我今天解题的题解报告：
[1] 哈希
题目描述
在数据结构中，我们学过哈希表。我们知道，哈希存储方法是一种根据关键码值(Key value)而直接进行访问的数据结构方法。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做哈希函数H(key)，存放记录的数组叫做哈希表。
在哈希表的构造中，哈希函数的选取显得异常重要。比如，在存储一个班级所有学生的某一门学科成绩的时候（假设该班人数<100），每个学生的学号有10~12位，我们不可能开出这么大的数组来储存，由于每个学生的学号末2位均不相同，我们可以开一个大小为100的数组，假设一个同学的学号为090104100151,那么，我们可以将该同学的成绩记录在下标为51数组元素中。这里我们用到的哈希方法叫做除留余数法，即H(key)=key % p(此处的p为100)。但是，这种哈希函数经常会产生冲突，即对于key1!=key2，却有H(key1)==H(key2)。现给定p以及n个关键码(key)，问：按这种哈希函数对着n个关键码进行映射，是否有冲突。
输入
输入文件中包含多个测试数据。每个测试数据占两行。每个测试数据的第一行为2个数p和n，第二行为n个关键码。其中p和n为不大于10000的正整数，其它的数均为不大于10000000的正整数。
最后一行为0 0，表示输入结束。
输出
对于每个测试数据，如果存在冲突，则输出"Conflict"，否则输出"All right"。
样例输入
100 3
1002 1103 2111
13 5
2 3 5 13 15
0 0
样例输出
All right
Conflict
题目类型：
哈希算法
思路：
根据哈希存储数据的方法计算每个数据的哈希值,
然后判断有无重复的哈希值即可
#include<bits/stdc++.h>
#include<iostream>
#include<stdio.h>
#include<string>
#include<cmath>
#include<set>
typedef long long ll;
using namespace std;
int main()
{
int p,n;
while(scanf("%d %d",&p,&n)!=EOF){
if(p==0 && n==0) break;
int a[n+5],b[n+5],flag = 1;
for(int i = 0 ; i < n ; i++){
cin>>a[i];
b[i] = a[i] % p;
}
sort(b,b+n);
for(int i = 1 ; i < n ;i++){
if(b[i]==b[i-1]) {
flag = 0;
break;
}
}
if(flag == 0) cout<<"Conflict"<<endl;
else cout<<"All right"<<endl;
}
return 0;
}
[2] Oulipo
题目描述
给出两个串S1,S2(只有大写字母)，求S1在S2中出现了多少次。例如S1=“ABA”，S2=“ABABA”，答案为 2。
输入T组数据，对每组数据输出结果。
每组数据保证strlen(S1)<=104,strlen(S2)<=106。
输入
输入T,表示T组数据接下来每行一个S1,每行一个S2。
输出
输出T行，表示每组的答案。
样例输入
3
BAPC
BAPC
AZA
AZAZAZA
VERDI
AVERDXIVYERDIAN
样例输出
1
3
0
思路:
参考何同学的ppt,先算出在相同长度下两个字符串的哈希值，进行比较，然后后一个字符串不断向下，删掉前一个字母，补上后一个字母，再比较哈希值…….直到结束
#include<bits/stdc++.h>
#include<iostream>
#include<stdio.h>
#include<string>
#include<cmath>
#include<set>
typedef unsigned long long ull;
using namespace std;
const int maxm = 1e4+5;
const int maxn = 1e6+5;
ull p = 131;
char w[maxm],t[maxn];
int main()
{
int k;
cin>>k;
while(k--){
cin>>w>>t;
int lenw = strlen(w);
int lent = strlen(t);
if(lenw>lent)
{
cout<<"0"<<endl;
continue;
}
ull k = 1;
for(int i = 0 ; i < lenw ; i++)
k*=p;
ull wh = 0 , th = 0;
for(int i = 0 ; i < lenw ; i++)
{
wh = wh*p + w[i]-'A'+1;
th = th*p + t[i]-'A'+1;
}
int cnt = 0;
for(int i = 0 ; i+lenw <= lent ; i++)
{
if(wh==th)cnt++;
if(i + lenw < lent)
{
th = th*p + (t[i+lenw]-'A'+1) - (t[i]-'A'+1)*k;
}
}
cout<<cnt<<endl;
}
return 0;
}
[3] Power Strings
题目描述：
Given two strings a and b we define ab to be their concatenation. For example, if a = “abc” and b = “def” then ab = “abcdef”. If we think of concatenation as multiplication, exponentiation by a non-negative integer is defined in the normal way: a^0 = “” (the empty string) and a^(n+1) = a*(a^n).
输入
Each test case is a line of input representing s, a string of printable characters. The length of s will be at least 1 and will not exceed 1 million characters. A line containing a period follows the last test case.
输出
For each s you should print the largest n such that s = a^n for some string a.
样例输入
abcd
aaaa
ababab
.
样例输出
1
4
3
思路:
使用kmp思想做的
题目翻译过来意思就是求最短的循环的字串长度的循环次数,如果不存在符合要求的字串就以字符串S为字串,循环次数就是1,
定理：假设字符串S的长度为len，则S存在循环子串，当且仅当，len可以被len - next[len]整除，最短循环子串为S[len - next[len]]
证明：
设S=q1q2q3q4q5q6q7q8，并设next[8] = 6，此时str = S[len - next[len]] = q1q2，由字符串特征向量next的定义可知，q1q2q3q4q5q6 = q3q4q5q6q7q8，即有q1q2＝q3q4，q3q4＝q5q6，q5q6＝q7q8，即q1q2为循环子串，且易知为最短循环子串。由以上过程可知，若len可以被len - next[len]整除，则S存在循环子串，否则不存在。
解法：利用KMP算法，求字符串的特征向量next，若len可以被len - next[len]整除，则最大循环次数n为len/(len - next[len])，否则为1。
#include<iostream>
#include<algorithm>
#include<stdio.h>
#include<string.h>
using namespace std;
int len,nex[1000005];
char s[1000005];
void getnex()
{
int j=-1;
for (int i=0;i<len;i++)
{
while(j!=-1 && s[j+1]!=s[i]) j=nex[j];
if (s[j+1]==s[i] && i!=0) j++;
nex[i]=j;
}
}
int main()
{
while(~scanf("%s",s))
{
if (s[0]=='.') return 0;
len=strlen(s);
getnex();
if (len%(len-nex[len-1]-1)==0&&len!=nex[len-1]+1)
printf("%d\n",len/(len-nex[len-1]-1));
else
printf("1\n");
}
return 0;
}
京公网安备 11010502036488号