CodeForces 367 B Sereja ans Anagrams

这是我在比赛中写的第一道尺取，这也算是一道很明显的尺取题，但是看了其他人的题解都说司马stl……
实际上代码还是我短很多……

但是第一次的尺取搞得我WA了7发，其中忘记排序4发……
总的来说还是不熟练吧……

题意：
给你两个序列分别为n,m个，和位置差，要你求出有多少个起始位置，使得从这位置开始后连续的m个元素与第二个序列相同。不要求顺序。

思路：
尺取，用一个map记录第二个序列各个元素的序列，再用一个map在尺取途中记录元素个数，只要小于原map的元素个数就可以继续往后取，最终结果必然是取得数目与m相同，每次取完判断一下即可。

AC Code

#include <cstdio>
#include <map>
#include <algorithm>
using namespace std;
typedef long long ll;

const int maxn = 2e5+5;

map<int,int> ma;
map<int,int> mb;
int ary[maxn];
int kao[maxn];

int main()
{
    int n,m,p,a,b;
    scanf("%d %d %d",&n,&m,&p);
    for(int i=1;i<=n;i++)
        scanf("%d",ary+i);
    for(int i=0;i<m;i++) {
        scanf("%d",&a);
        mb[a]++;
    }
    int ans =0;
    for(int i=1;i<=p;i++) {
        int a=i,b=i;
        ma.clear();
        while(a<=n)
        {
            if(b<a)
                b=a;
            while(b<=n && ma[ary[b]]<mb[ary[b]]) {
                ma[ary[b]]++;
                b+=p;
            }
            if((b-a)/p==m)
                kao[ans++]=a;
            if(ma[ary[a]]>0)
                ma[ary[a]]--;
            a+=p;
        }
    }
    printf("%d\n",ans);
    sort(kao,kao+ans);
    for(int i=0;i<ans;i++)
        printf("%d ",kao[i]);
    return 0;
}