http://codeforces.com/contest/368/problem/D

題意：有a、b兩個數組，a數組有n個數，b數組有m個數，現在給出一個p，要你找出所有的位置q，使得位置q? q+p?? q+2*p? .....q+(m-1)*p?? 經過一定的操作（不改變數據大小）全等于b數組。

思路：首先肯定對a數組離散，然后二分對a、b數組分配好離散后的值。其實我們只需要枚舉0————p位置，哈希記錄，然后從q----一直滾到q(m-1)*p>=n，對于一個數據，出來第一個數，進去最后一個數。

這樣，如果沒有避免對b數組掃描一次，那么還是會超時，額，我在這里超時了幾次。這個題目的核心就是如何避免再一次掃描b數組，因為我要判斷挑出來的m個值與b數組全等........其實可以這樣，我們把b數組里的數據都記錄一次，比如b[10]={1,2,3,1,2,3,4,5,1,2}；

那么我們對于b數組哈希的話，就是vist[1]=3??? vist[2]=3??? vist[3]=2??? vist[4]=1??? vist[5]=1?? 那么，如果說要有一個數來記錄b有幾種不想等的數據的話，那么k=5；

那么同樣的，我們會對于從a數組里面挑出來的m個值進行哈希，那么有vist1[1]?? vist1[2]?? vist1[3]?? vist1[4]?? vist1[5]；

當且僅當，vist[1]==vist1[1]?? vist[2]==vist1[2]?? vist[3]==vist1[3]?? vist[4]==vist1[4]?? vist[5]==vist1[5]時，與b全等，那么也就是說

在嚴格挑選出來的m各值，要有m種數，并且，這m種數要等于k，如此就可以說挑出來的m個數就是b數組.........

那么其實，只要有vist[i]>0時? 有vist[i]==vist1[i]??? 那就m++??? 如果某個操作，彈出來一個值，使得原本vist[i]>0時? 有vist[i]==vist1[i]的，現在不想等了，那么就m--；

ac代碼：

額，還需要注意一點，這個數據有的地方會超int型，所以，用__int64比較好把 #include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; int vist[200005],vist1[200005]; int a[200005],b[200005],s[200005]; int total[200005],vist2[200005]; int vist3[200005]; int erfen(int ll,int rr,int ans) {while(ll<=rr){int mid=(ll+rr)/2;if(s[mid]>ans)rr=mid-1;else ll=mid+1;}return rr; } int main() {int n,m,p;while(scanf("%d%d%d",&n,&m,&p)>0){for(int i=0; i<n; i++){scanf("%d",&a[i]);s[i]=a[i];}sort(s,s+n);int cnt=1;for(int i=1; i<n; i++)if(s[i]!=s[i-1])s[cnt++]=s[i];sort(s,s+cnt);memset(vist,0,sizeof(vist));memset(vist1,0,sizeof(vist1));memset(vist2,0,sizeof(vist2));memset(vist3,0,sizeof(vist3));//for(int i=0;i<n;i++)//vist[s[i]]=i+1;for(int i=0; i<m; i++)scanf("%d",&b[i]);for(int i=0; i<n; i++){int id=erfen(0,cnt-1,a[i]);vist[id]=1;a[i]=id;}int flg=1;int ans=0,ans1=0;for(int i=0; i<m; i++){int id=erfen(0,cnt-1,b[i]);if(b[i]==s[id]){if(vist1[id]==0)ans++;vist1[id]++;}else{flg=0;break;}b[i]=id;//vist2[id]=1;}if(flg==0){printf("0\n");continue;}int sum=0;for(int i=0; i<p; i++){if((__int64)i+(__int64)(m-1)*(__int64)p>=n)break;for(int j=0; j<m; j++){if((__int64)i+(__int64)j*(__int64)p>=n)break;int y=a[i+j*p];if(vist1[y]){vist2[y]++;if(vist2[y]==vist1[y]){ans1++;vist3[y]=0;}if(vist2[y]>vist1[y]&&vist3[y]==0){ans1--;vist3[y]=1;}}}if(ans1==ans){total[sum++]=i;}for(int j=i+p; (__int64)j+(__int64)(m-1)*(__int64)p<n;j+=p){int y=a[j-p];if(vist1[y]){if(vist2[y]==vist1[y]){ans1--;vist3[y]=0;}vist2[y]--;if(vist2[y]==vist1[y]){ans1++;vist3[y]=0;}}y=a[j+(m-1)*p];if(vist1[y]){vist2[y]++;if(vist2[y]==vist1[y]){ans1++;vist3[y]=0;}if(vist2[y]>vist1[y]&&vist3[y]==0){ans1--;vist3[y]=1;}}if(ans1==ans){total[sum++]=j;}}for(int k=0;k<m;k++){vist2[b[k]]=0;vist3[b[k]]=0;ans1=0;}}printf("%d\n",sum);sort(total,total+sum);for(int i=0; i<sum; i++){if(i==0)printf("%d",total[i]+1);elseprintf(" %d",total[i]+1);}printf("\n");}return 0; }

?

總結

以上是生活随笔為你收集整理的Codeforces Round #215 (Div. 2) D. Sereja ans Anagrams的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。