校内省选比赛D1

(⊙o⊙)…T1又考了原题，但上回仍然没有订正。再加上第三题sort蜜汁使用出锅，数组开小，成功爆零。

xiz

• 题意有锅，其实S与T匹配的条件是，对于S有一个映射表，然后映射表与T是一一对应的。（注意映射表是一个排列，即不能有重复元素。）
• 其实，这题难在把判定条件的转化。跟是不是原题没有关系，还是自己菜。我们判断一个子串是否和T串匹配上，应该是一一对应的每个位置，它们分别代表的字母在这两个串里面出现的次数相同。这个条件可以转化为，每一个位置，它的last都相同。last即上次出现的位置。
• 直接KMP就好啦，把KMP判定字母相同的条件变为last相同就好。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e6+10;
int T,C,n,m,cnt,ans[N],a[N],b[N],last[N],lasta[N],lastb[N],f[N];
int read(){int k;scanf("%d",&k);return k;}
int main(){
	freopen("xiz.in","r",stdin);
	freopen("xiz.out","w",stdout);
	for(T=read(),C=read();T;T--){
		n=read(),m=read();cnt=0;
		memset(last,0,sizeof(last));
		for(int i=1;i<=n;++i){
			a[i]=read();
			lasta[i]=i-last[a[i]];
			last[a[i]]=i;
		}
		memset(last,0,sizeof(last));
		for(int i=1;i<=m;++i){
			b[i]=read();
			lastb[i]=i-last[b[i]];
			last[b[i]]=i;
		}
		for(int i=2,j=0;i<=m;++i){
			while(lastb[j+1]!=min(j+1,lastb[i])&&j) j=f[j];
			if(min(j+1,lastb[i])==lastb[j+1]) j++;
			f[i]=j;
		}
		for(int i=1,j=0;i<=n;++i){
			while((lastb[j+1]!=min(j+1,lasta[i])||j==m)&&j) j=f[j];
			if(min(j+1,lasta[i])==lastb[j+1]) j++;
			if(j==m) ans[++cnt]=i-m+1;
		}
		printf("%d\n",cnt);
		for(int i=1;i<=cnt;++i) printf("%d ",ans[i]);
		cout<<endl;
	}
	return 0;
}

• 当然，上述条件，也可以用Hash写。

zkb

• 20分数据，没有操作1。你可能想到了求个前缀积，O（1）求答案。但是不好意思，这个数可能是几百万位的。考虑我们把每一个数取以10为底的幂，用double存。那么区间乘法就变成了区间加法。求最高位是哪个数呢？把double的小数部分求一个pow其实就是啦。 20 get。
• 另20分数据，n<=1000。并且保证乘积不超过$2^{63}$263。呵呵，直接暴力肝，20 get。
• 另20分数据，n<=1000。不过这次不保证乘积大小了，还是取log求，暴力写。
• 60分暴力美滋滋。