codeforces #215 div2前四题(二)
mit per test 256 megabytes
input standard input
output standard output
Sereja has two sequences a and b and number p. Sequence a consists of n integers a1, a2, ..., an. Similarly, sequence b consists ofm integers b1, b2, ..., bm. As usual, Sereja studies the sequences he has. Today he wants to find the number of positions q (q + (m - 1)·p ≤ n; q ≥ 1), such that sequence b can be obtained from sequence aq, aq + p, aq + 2p, ..., aq + (m - 1)p by rearranging elements.
Sereja needs to rush to the gym, so he asked to find all the described positions of q.
Input
The first line contains three integers n, m and p (1 ≤ n, m ≤ 2·105, 1 ≤ p ≤ 2·105). The next line contains n integers a1, a2, ..., an (1 ≤ ai ≤ 109). The next line contains m integers b1, b2, ..., bm (1 ≤ bi ≤ 109).
Output
In the first line print the number of valid qs. In the second line, print the valid values in the increasing order.
Sample test(s)
input
5 3 1
1 2 3 2 1
1 2 3
output
2
1 3
input
6 3 2
1 3 2 2 3 1
1 2 3
output
2
1 2
题意：给两个数组a和b，找出a中所有可能的q (q + (m - 1)·p ≤ n; q ≥ 1)，使得序列aq, aq + p, aq + 2p, ..., aq + (m - 1)p，能够由数组b改变值的顺序排列而成。
解题思路：先根据%p分组，然后对组内进行处理，移动的时候可以使用两个指针，l和r不断右移。用mq记录b中每个数值能够使用的次数，当存在满足的情况时，mq中所有的数值都正好使用完，一组之内之后的情况需要减掉序列最前面的一个值的使用，加上序列之后新增加的值，并记录当前状态的满足情况。
题目地址：B.
Sereja ans Anagrams
AC代码：
[cpp]
#include
#include
#include
#include
#include
#include
using namespace std;
const int maxn=2e5+5;
map mq;
vector ans;
int a[maxn],b[maxn];
int main()
{
long long n,m,p,i,j;
while(cin>>n>>m>>p)
{
ans.clear();
for(i=1;i<=n;i++) scanf("%d",&a[i]);
for(i=1;i<=m;i++) scanf("%d",&b[i]);
for(i=1;i<=p&&(i+(m-1)*p)<=n;i++)
{
mq.clear();
for(j=1;j<=m;j++) mq[b[j]]++; //先把b的元素种类和个数都保存起来
int step=0;
for(j=i;;j+=p)
{
if(step==m) break;
mq[a[j]]--;
if(mq[a[j]]==0) mq.erase(a[j]);
step++;
}
int l,r; //用两个指针对一个组的进行遍历
l=i,r=l+m*p;
if(mq.size()==0) ans.push_back(l);
while(1)
{
if(r>n) break;
mq[a[l]]++,mq[a[r]]--;
if(mq[a[r]]==0) mq.erase(a[r]);
if(mq[a[l]]==0) mq.erase(a[l]);
l+=p,r+=p;
if(mq.size()==0) ans.push_back(l);
}
}
sort(ans.begin(),ans.end());
printf("%d\n",ans.size());