总目录

在线测评地址(ybt)

在线测评地址(LOJ)

在线测评地址(LUOGU)

ybt测试点30运行超时   LOJ AC   LUOGU AC

在浩瀚的题海中，不追求ybt所有测试点的通过，此题就此别过。

ybt

未通过

测试点	结果	内存	时间
测试点1	答案正确	632KB	2MS
测试点2	答案正确	636KB	2MS
测试点3	答案正确	632KB	1MS
测试点4	答案正确	632KB	1MS
测试点5	答案正确	640KB	1MS
测试点6	答案正确	644KB	2MS
测试点7	答案正确	632KB	1MS
测试点8	答案正确	632KB	1MS
测试点9	答案正确	648KB	1MS
测试点10	答案正确	652KB	2MS
测试点11	答案正确	644KB	2MS
测试点12	答案正确	640KB	1MS
测试点13	答案正确	684KB	2MS
测试点14	答案正确	648KB	2MS
测试点15	答案正确	1612KB	24MS
测试点16	答案正确	2176KB	42MS
测试点17	答案正确	1204KB	13MS
测试点18	答案正确	2560KB	55MS
测试点19	答案正确	1348KB	21MS
测试点20	答案正确	4524KB	132MS
测试点21	答案正确	2060KB	50MS
测试点22	答案正确	5508KB	178MS
测试点23	答案正确	2412KB	66MS
测试点24	答案正确	8440KB	330MS
测试点25	答案正确	3456KB	64MS
测试点26	答案正确	14304KB	684MS
测试点27	答案正确	5612KB	54MS
测试点28	答案正确	17236KB	867MS
测试点29	答案正确	6624KB	123MS
测试点30	运行超时	19448KB	1000MS

LOJ

LUOGU

困扰了许久的问题，笔算就解决了，如下。

样例中，k=4，分成5个字串

(1,1,1,2),(2,2,3,3),(3,1,2,3),(3,1,2,2),(1,3,3,2)
中的
(3,1,2,3)，(1,3,3,2)是同一子串吗？
不是 同一子串。
请注意题干：子串都是可以反转的。

因为反转：
(3,1,2,3)同一子串是(3,2,1,3)

n=200000,需要比较子串的次数，编程如下：

#include <bits/stdc++.h>
using namespace std;
int main(){
	int n,cnt=0,i;
	scanf("%d",&n);
	for(i=1;i<=n;i++)
		cnt+=n/i;
	printf("cnt=%d\n",cnt);
	return 0;
} 

对应的输入输出数据如下：

200000
cnt=2472113

不会超时，放心了。

该题的难点在于找出字串，与反转字串的坐标映射关系。

字串总长度len
字串的位置区间[x,y]
对应的反转字串的位置区间[len-(y-1),len-(x-1)]

推导如下：

顺序    123456789
字串    123456789
反转字串987654321

字串总长度9
字串中的4567对应顺序区间[4,7]
反转字串中的7654对应的顺序区间[3,6]

字串的位置4，对应反转字串的位置6，换算关系9-(4-1)=6
字串的位置7，对应反转字串的位置3，换算关系9-(7-1)=3

字串总长度len
字串的位置区间[x,y]
对应的反转字串的位置区间[len-(y-1),len-(x-1)]

验证如下
字串中的1234对应顺序区间[1,4]
反转字串中的4321对应的顺序区间[9-(4-1),9-(1-1)]即[6,9]

找大于200000的质数，上线性筛

#include <bits/stdc++.h>
#define maxn 200010
using namespace std;
int prime[maxn],tot,b[maxn];
void linear(int x){
	int i,j;
	for(i=2;i<=x;i++)b[i]=0;
	for(i=2;i<=x;i++){
		if(b[i]==0)prime[++tot]=i;
		for(j=1;j<=tot&&prime[j]*i<=x;j++){
			b[prime[j]*i]=1;
			if(i%prime[j]==0)break;
		}
	}
}
int main(){
	int x,i;
	scanf("%d",&x);
	linear(x);
	for(i=tot;i>=1;i--)
		if(prime[i]>=200000)printf("%d ",prime[i]);
	return 0;
} 

上述代码对应的输入输出数据：

200008
200003

找到质数200003

想开个数组，去重，但一看ULL范围，不可行，还是要借助STL，印象中可以借助set还是map，没用过，那就现学呗。

研究了，发现map好用，可以以局部变量的形式使用，免去了自主初始化。

ybt测试点30运行超时   LOJ AC   LUOGU AC 代码如下：

#include <bits/stdc++.h>
#define maxn 200010
#define B 200003
#define ULL unsigned long long
using namespace std;
int a[maxn],b[maxn],N,c[maxn],pos[maxn]; 
ULL ah[maxn],bh[maxn],n[maxn];
int main(){
	int i,j,k,xa,ya,aval,bval,xb,yb,v,mx=-1,kn=0;
	scanf("%d",&N);
	for(i=1;i<=N;i++){
		scanf("%d",&a[i]);//顺序存储 
		b[N-i+1]=a[i];//逆序存储 
	}
	n[0]=1;
	for(i=1;i<=N;i++)n[i]=n[i-1]*B;
	ah[0]=0,bh[0]=0;
	for(i=1;i<=N;i++){
		ah[i]=ah[i-1]*B+a[i];
		bh[i]=bh[i-1]*B+b[i]; 
	} 
	for(k=1;k<=N;k++){
		map<ULL,int> mp;
		v=0;
		for(j=1;j+k-1<=N;j+=k){//j代表初始位置，j+k-1代表末了位置 
			xa=j,ya=j+k-1;
			aval=ah[ya]-ah[xa-1]*n[ya-(xa-1)];
			xb=N-(ya-1),yb=N-(xa-1);
			bval=bh[yb]-bh[xb-1]*n[yb-(xb-1)];
			if(mp[aval]==0)mp[aval]=++v,mp[bval]=v;//顺序子串,逆序子串 效果等同 
		}
		c[k]=v;
		mx=max(mx,v);
	}
	for(k=1;k<=N;k++)
		if(c[k]==mx)++kn,pos[kn]=k;
	printf("%d %d\n",mx,kn);
	printf("%d",pos[1]);
	for(i=2;i<=kn;i++)printf(" %d",pos[i]);
	return 0;
}

该题除了翻阅STL map知识外，未查阅任何资料，编码全部独立完成。耗时半天。

提高+/省选-   需要补充的知识是 STL map的使用