兔子与兔子
这题的话很好解,先预处理一下再暴力求值。
记我们选取的DNA序列为S,根据我们刚才提到的字符串Hash算法,设表示前缀子串
的Hash值,有
于是可以得到任一区间
的
。当两个区间的Hash值相同时,我们就认为对应的两个子串相等。整个算法的时间复杂度为
。 ......
「算进」[基构]HASH
首先,「算进」是什么?
就是《算法竞赛进阶》,大神写的书,一个蒟蒻怎么能不好好磕一下呢,于是就有了这第一篇文章。
[基构]是什么?
就是基础数据结构的意思呢,基础不扎实就要好好学基构。
从我最不好的地方开始学习,来Hash把! ......
Snowflake Snow Snowflake
Snowflake Snow Snowflakes
这题的话就是明显可以用哈希表来做啦,对于两篇形状相同的雪花,那么他们的乘积也是一样的,但是又为了避免偶然,所以哈希函数的计算中增加了他们的和,这样就可以很好的做统计了。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 |
#include<set> #include<map> #include<list> #include<queue> #include<cmath> #include<vector> #include<cstdio> #include<cctype> #include<cstdlib> #include<cstring> #include<iostream> #include<algorithm> #define qread(x) x=read() #define mes(x,y) memset(x,y,sizeof(x)) #define mpy(x,y) memcpy(x,y,sizeof(x)) #define Maxn 100000 #define Maxs 6 #define HashMod 99991 #define INF 2147483647 inline int read(){ int f=1,x=0;char ch; while(!(ch>='0'&&ch<='9')){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return f*x; } int tot,snow[Maxn+1][Maxs],head[Maxn+1],next[Maxn+1]; int Hash(int *a){ int sum=0,mul=1; for(int i=0;i<Maxs;i++){ sum=(sum+a[i])%HashMod; mul=(long long)mul*a[i] % HashMod; } return (sum+mul)%HashMod; } bool bk; bool Check(int *a,int *b){ for(int i=0;i<Maxs;i++){ for(int j=0;j<Maxs;j++){ bk=true; for(int k=0;k<Maxs;k++){ if(a[(i+k)%Maxs]!=b[(j+k)%Maxs]){ bk=false;break; } } if(bk==true)return true; bk=true; for(int k=0;k<Maxs;k++){ if(a[(i+k)%Maxs]!=b[(j-k+Maxs)%Maxs]){ bk=false;break; } } if(bk==true)return true; } } return false; } int tmp; bool insert(int *a){ tmp=Hash(a); for(int k=head[tmp];k>0;k=next[k]){ if(Check(snow[k],a)==true){ return true; } } tot++; mpy(snow[tot],a); next[tot]=head[tmp]; head[tmp]=tot; return false; } int n,a[Maxs]; int main(){ //freopen("poj-3349.in","r",stdin); //freopen("poj-3349.out","w",stdout); qread(n); tot=0; for(int i=1;i<=n;i++){ int a[Maxs]; for(int j=0;j<Maxs;j++)qread(a[j]); if(insert(a)==true){ printf("Twin snowflakes found."); return 0; } } printf("No two snowflakes are alike."); } |
......