【CF#526D/51nod1554】欧姆诺姆和项链

  • 本文为博主原创，未经许可不得转载

这道题非常玄妙啊

首先我们把$S$拆成循环串，即$S=PPPPPPPPT$，其中$T$是$P$的前缀

设$S$中含有$R$个$T$，因为$S=A+B+…+B+A$，所以设$A$中含有$x$个$T$，则AB中含有$\frac{R-x}{k}$个T，且$k|(R-x)$

所以B中含有$\frac{R-x}{k}-x$ 个T，我们需要满足$x>=0$的同时使得$\frac{R-x}{k}-x>0$

设$f(x)= \frac{R-x}{k}-x$，我们要保证$f(x)>0$,也就是说保证$f(x)$的最大值大于$0$

我们发现$f(x)$为减函数，所以$x$的取值应该尽量小，同时又要满足$k|(R-x)$，所以$x=R\%k$

所以我们只需要令$x=R\%k$，然后判断$f(x)$是否大于$0$即可

特别的如果$P=T$，那么$B$串是可以为空的，也就是说保证的是$f(x)>=0$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include<bits/stdc++.h>
#define FILE "read"
#define MAXN 1000010
using namespace std;
int n,k,pre[MAXN];
char ch[MAXN];
inline int read(){
	int x=0,f=1;  char ch=getchar();
	while(!isdigit(ch))  {if(ch=='-')  f=-1;  ch=getchar();}
	while(isdigit(ch))  {x=x*10+ch-'0';  ch=getchar();}
	return x*f;
}
int main(){
	freopen(FILE".in","r",stdin);
	freopen(FILE".out","w",stdout);
	n=read();  k=read();
	scanf("%s",ch+1);  pre[1]=0;
	for(int i=2,j=0;i<=n;++i){
		while(ch[j+1]!=ch[i]&&j)  j=pre[j];
		if(ch[j+1]==ch[i])  ++j;  pre[i]=j;
	}
	for(int i=1;i<=n;++i){
		int R=i/(i-pre[i]);
		if(i%(i-pre[i])){
			if(R/k-R%k>0)  putchar('1');
			else putchar('0');
		}
		else{
			if(R/k-R%k>=0)  putchar('1');
			else putchar('0');
		}
	}
	return 0;
}

本文标题:【CF#526D/51nod1554】欧姆诺姆和项链

文章作者:chty

发布时间:2017年04月20日 - 08时13分

最后更新:2018年07月02日 - 20时31分

许可协议:本文为博主原创，未经许可不得转载。

文章目录
,