CF1138

这么早的CF已经很少见了。


CF1138A
是的这题调了我半个小时。
别说了,丢人。
具体来说就是我写代码的时候默认nw总是较小的那个,但事实上有时候a[i]也有可能是较小的那个。


#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;

int a[1000005],b[1000005];
int n;

void init(){
	scanf("%d",&n);
	for(int i=1;i<=n;++i){
		scanf("%d",&b[i]);
	}
	a[1]=1;
	int nw=0,ans=0;
	for(int i=2;i<=n;++i){
		if(b[i]!=b[i-1]){
			nw=a[i-1];
			a[i]=1;
			ans=max(ans,min(nw,a[i]));
		}else{
			a[i]=a[i-1]+1;
			ans=max(ans,min(nw,a[i]));
		}
	}
	printf("%d\n",ans*2);
}
int main(){
	init();
	return 0;
}


CF1138B
这题我是松过去的。
一开始没看数据范围还有O(n)的幻想,看了以后就开始YY平方级的做法,但是编了半天没编出来。
最后决定破釜沉舟,写一个复杂度三方不满的暴力,居然一发入魂过了。Amazing!
一开始觉得复杂度是十亿左右,现在仔细算一算应该是一亿出头,加上常数小卡过去其实确实是有可能的。


#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;

int n;
char a[5005],b[5005];
int val[5005];
int mp[5005][5005];
bool vis[5005];
inline void prnt(int i,int j,int k,int l){
	int i1=0,j1=0,k1=0,l1=0;
	for(int t=1;t<=n;++t){
		if(val[t]==0&&i1<i){
			++i1;
			printf("%d ",t);
		}
		if(val[t]==1&&k1<k){
			++k1;
			printf("%d ",t);
		}
		if(val[t]==2&&j1<j){
			++j1;
			printf("%d ",t);
		}
		if(val[t]==3&&l1<l){
			++l1;
			printf("%d ",t);
		}
	}
}
void init(){
	scanf("%d",&n);
	cin>>a+1>>b+1;
	int q=0,w=0,e=0,r=0;
	for(int i=1;i<=n;++i){
		if(a[i]=='0'&&b[i]=='0'){
			++q;
			val[i]=0;
		}
		if(a[i]=='1'&&b[i]=='0'){
			++w;
			val[i]=1;
		}
		if(a[i]=='0'&&b[i]=='1'){
			++e;
			val[i]=2;
		}
		if(a[i]=='1'&&b[i]=='1'){
			++r;
			val[i]=3;
		}
	}
//	fst->w,scn->e
	for(int i=0;i<=min(n/2,q);++i){
		for(int j=0;j<=min(n/2-i,e);++j){
			for(int k=0;k<=min(n/2-i-j,w);++k){
				int l=n/2-i-j-k;
				if(l>r){
					continue;
				}
				if(i+k==e-j+q-i&&j+l==w-k+r-l){
					prnt(q-i,e-j,w-k,r-l);
					return;
				}
			}
		}
	}
	puts("-1");
	return;
}
int main(){
	init();
	return 0;
}


CF1138C
看到这题首先就可以想到离散化。
具体来说就是我们对于每一行和每一列都各自离散化,然后计算出每个格子在这一行/列的相对大小。
由于大小关系不能改变,所以这个相对大小必须取较大值,这样才能留下足够的空间。
同样的,比每个格子大的数量也要取较大值,也是为了留下足够的空间。
然后就可以了。
不过我离散化写丑了,丢人。


#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;

int n,m;
int a[1005][1005],a1[1005][1005],a2[1005][1005];
int b[1005];
int mx1[1005],mx2[1005];
void init(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;++i){
		for(int j=1;j<=m;++j){
			scanf("%d",&a[i][j]);
		}
	}
	int nw;
	for(int i=1;i<=n;++i){
		for(int j=1;j<=m;++j){
			b[j]=a[i][j];
		}
		sort(b+1,b+1+m);
		mx1[i]=unique(b+1,b+m+1)-b-1;
		for(int j=1;j<=m;++j){
			a1[i][j]=lower_bound(b+1,b+mx1[i]+1,a[i][j])-b;
		}
	}
	for(int i=1;i<=m;++i){
		for(int j=1;j<=n;++j){
			b[j]=a[j][i]; 
		}
		sort(b+1,b+1+n);
		mx2[i]=unique(b+1,b+n+1)-b-1;
		for(int j=1;j<=n;++j){
			a2[j][i]=lower_bound(b+1,b+mx2[i]+1,a[j][i])-b;
		}
	}
	for(int i=1;i<=n;++i){
		for(int j=1;j<=m;++j){
			printf("%d ",max(a1[i][j],a2[i][j])+max(mx1[i]-a1[i][j],mx2[j]-a2[i][j]));
		}
		puts("");
	}
}
int main(){
	init();
	return 0;
}


CF1138D
第一个想法是暴力循环,但是那样子好像会WA9。
仔细考虑一下发现需要处理出最大非本身Border,然后分两段乱搞。
当然是要上一个KMP了。
但是我乱搞还是写丑了,WA在几十个点。现在想来应该是输出剩余的东西的时候写得丑了。最后参考了小粉兔的才通过。


#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;

char a[500005],b[500005];
int x,y,n,m;
int nxt[500005];
void init(){
	cin>>a+1;
	cin>>b+1;
	n=strlen(a+1);
	m=strlen(b+1);
	for(int i=1;i<=n;++i){
		if(a[i]=='1'){
			++x;
		}else{
			++y;
		}
	}
	int l1;
	int j=0;
    for(int i=2;i<=m;i++){
        while(j&&(b[i]!=b[j+1])){
            j=nxt[j];
        }
        if(b[j+1]==b[i]){
            j++;
        }
        nxt[i]=j;
    }
    l1=nxt[m];
	j=0;
    for(int i=1;i<=n;++i){
    	if(b[j+1]=='1'&&x){
    		putchar('1');
    		--x;++j;
    		if(j==m){
    			j=l1;
			}
		}else if(b[j+1]=='0'&&y){
			putchar('0');
			--y;++j;
			if(j==m){
				j=l1;
			}
		}else{
			putchar(b[j+1]=='0'?'1':'0');
		}
	}
}
int main(){
	init();
	return 0;
}

lp3809 【模板】后缀排序

我们考虑一下前缀排序。
很显然可以上一个后缀自动机。按顺序深度搜索输出即可。
那么对于后缀排序,只需要倒着插入然后输出parent树即可。

#include<iostream>
#include<cstdio>
#include<cstring>
#define MAXN 2000005

inline int hsh(char C){
	return 'a'<=C&&C<='z'?C-'a'+36:('A'<=C&&C<='Z'?C-'A'+10:C-'0');
}

int l[MAXN],r[MAXN],nxt[MAXN][62],fa[MAXN],fst[MAXN],bckt[MAXN],a[MAXN];
int loc[MAXN];
char ch[1000005];
int cnt,nw;
int n;

int v[MAXN],to[MAXN],h[MAXN],et=0;
inline void add(int U,int V){
	++et,v[et]=V,to[et]=h[U],h[U]=et;
}

inline void prpr(){
	fa[0]=-1,cnt=nw=0;
}
int p,q,np,nq;
inline void psh(int C,int I){
	np=++cnt;r[np]=l[np]=l[nw]+1;p=nw;nw=np;loc[np]=I;
	while(p>=0&&!nxt[p][C]){
		nxt[p][C]=np;
		p=fa[p];
	}
	if(p==-1){
		fa[np]=0;
		return;
	}
	q=nxt[p][C];
	if(l[p]+1==l[q]){
		fa[np]=q;
		return;
	}
	nq=++cnt;
	l[nq]=l[p]+1,fa[nq]=fa[q],fa[q]=fa[np]=nq,r[nq]=r[q];
	for(int i=0;i<62;++i){
		nxt[nq][i]=nxt[q][i];
	}
	while(p>=0&&nxt[p][C]==q){
		nxt[p][C]=nq;
		p=fa[p];
	}
}
inline void srt(){
	for(int i=1;i<=cnt;++i){fst[i]=hsh(ch[n-r[i]+1+l[fa[i]]]),++bckt[fst[i]];}
	for(int i=0;i<62;++i){bckt[i]+=bckt[i-1];}
	for(int i=1;i<=cnt;++i){a[bckt[fst[i]]--]=i;}
	for(int i=cnt;i;--i){add(fa[a[i]],a[i]);}
}
int tp=0;
inline void dfs(int X){
	if(loc[X]){
		printf("%d ",loc[X]); 
	}
	for(int i=h[X];i;i=to[i]){
		dfs(v[i]);
	}
}
void init(){
	std::cin>>ch+1;
	n=strlen(ch+1);
	for(int i=n;i;--i){
		psh(hsh(ch[i]),i);
	}
	srt();dfs(0);
	puts("");
	
}

int main(){
	prpr(); 
	init();
	return 0;
}

lp3804 【模板】后缀自动机

如题所示,这是一道模板题。
事实上,尽管后缀自动机有着较为强大和完整的功能,但它的实现却是比较简单的。
概括地说,后缀自动机是一种用线性的时间复杂度和字符数与字符集的乘积的空间复杂度来储存一个字符串里每一个前缀的所有后缀,并且相同的字符串只会被表达一次的一类自动机。
下面我们考虑如何构造这个自动机。
构造后缀自动机使用的是一种被称为「增量算法」的构造方法。这种构造方法将所有的节点依次加入自动机。
后缀自动机由以下四个部分组成:
根节点,前缀节点,父亲边和字符边。
根节点一开始就存在,它象征着空串。而每一次加入的是一个前缀节点。
前缀节点表示的是原串中的某一个前缀。
每个前缀节点都有一条父亲边连向另一个节点。
每个前缀节点都有数条字符边连向另一些节点。
对于每个前缀节点,它储存的都是一些字符串。
具体而言,是这个点表示的最长串的所有长度严格大于它的父亲的最长串的长度的后缀。考虑到这个性质,每个点事实上不必记录整个字符串集合,而只需记录字符串的最长长度即可。
从这个节点沿着父亲边走到根的路径上的所有点表示的字符串集合构成的新集合,不重复不遗漏地表示了当前点的所有后缀。

我们记录一个节点nw,表示的是当前插入最长的一个前缀所在的点。
当我们加入了一个新的字符c,我们进行如下判断和操作。
新建一个点np,然后沿着nw到根的路径向上搜索,对路径上的每个点进行判断,如果这个点没有拉出过字符为c的边,就将它连一条字符为c的边连向新点。否则进行如下特殊处理。
如果沿着nw到根的每一个点都连向了新点,则表示新节点表示的每一个非空后缀都无法在已有的自动机内找到,那么它的后缀序列需要且仅需要两个点来表达:它本身,以及象征空字符串的根节点。
否则,我们考虑这个已经有字符为c的边的点,我们令它为p,它通过c连向的点为q。很明显这意味着,np代表的后缀集合与q代表的后缀集合有交集。
仍然是分类讨论。如果q表示的字符串数量是1的话,那么它代表的后缀集合显然一定是np代表的后缀集合的一个真子集。并且这个集合关于np代表的后缀集合的补集正好是np代表的字符串集合。
那么我们就可以把np的父亲边连向q。
如果q表示的字符串数量大于1,这就意味着两者的后缀集合含有交际并且互不包含。
于是我们需要把q节点拆成q和nq两个节点,其中nq表示被np包含的字符串集合,而q表示不被np包含的字符串集合。
显然需要修改字符边c的点只有p到根的路径上的所有点。因为只有这些点才能够拉出被np包含的字符串集合。
当然,这些需要修改c的点也一定是一段连续的区间。这由每个点包含的后缀集合不重复不遗漏可以得到。
而q与np的父亲都应该修改到点nq,这也很显然,因为拆点后q表示的后缀集合包含nq表示的后缀集合。
同时,原来的q点的字符出边也都应该复制到nq上。这是因为一个字符出边表示的是目的点包含了所有出发点所包含的每一个字符串末尾添上字符边代表的字符所构成的集合。
故而拆点前的q点给其他的点贡献的一部分字符串的字符出边的出发点在拆点后变成了nq。

这就完成了后缀自动机的构建。

对于这一题,我们考虑一个显而易见的性质:
一个子串在原串中出现的次数,等价于以它作为后缀的前缀个数。
因此,只要计算父亲边构成的树上的子树大小乘以节点最长字符串长度的最值即可。

#include<iostream>
#include<cstdio>
#include<cstring>
 
inline long long Max(long long A,long long B){
	return A>B?A:B;
}
int n;
int l[2000005],fa[2000005],nxt[2000005][26],sz[2000005];
int h[2000005],v[2000005],to[2000005];
char ch[2000005];
int cnt,nw,et;
inline void add(int U,int V){
	++et,v[et]=V,to[et]=h[U],h[U]=et;
}
inline void prpr(){
	l[0]=0,fa[0]=-1,sz[0]=0;
	cnt=nw=0;
}
int p,q,np,nq;
inline void psh(int c){
	np=++cnt,p=nw,l[np]=l[nw]+1,sz[np]=1,nw=np;
	while(p>=0&&!nxt[p][c]){
		nxt[p][c]=np;
		p=fa[p];
	}
	if(p==-1){
		fa[np]=0;
		return;
	}
	q=nxt[p][c];
	if(l[p]+1==l[q]){
		fa[np]=q;
		return;
	}
	nq=++cnt;
	for(int i=0;i<26;++i){
		nxt[nq][i]=nxt[q][i];
	}
	fa[nq]=fa[q],fa[q]=fa[np]=nq,l[nq]=l[p]+1;
	while(p>=0&&nxt[p][c]==q){
		nxt[p][c]=nq;
		p=fa[p];
	}
}
long long ans=0;
inline void dfs(int X){
	for(int i=h[X];i;i=to[i]){
		dfs(v[i]);
		sz[X]+=sz[v[i]];
	}
	if(sz[X]>1){
		ans=Max(ans,1ll*sz[X]*l[X]);
	}
}
void init(){
	std::cin>>ch+1;
	n=strlen(ch+1);
	for(int i=1;i<=n;++i){
		psh(ch[i]-'a');
	}
	for(int i=1;i<=cnt;++i){
		add(fa[i],i);
	}
	dfs(0);
	printf("%lld",ans);
}

int main(){
	prpr();
	init();
	return 0;
}

sp7586 NUMOFPAL

求一个字符串的回文子串个数。
凡是这类问题,优先考虑麻辣烫。
我们可以发现,依据题意,任意两个对称轴不同的回文串,都是「本质不同」的。
并且,每个回文串,和它对称轴相同的所有子串都必然是回文串。
故而我们先用麻辣烫处理,然后统计一遍即可。

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define Max(_A,_B) ((_A)>(_B)?(_A):(_B))
#define Min(_A,_B) ((_A)<(_B)?(_A):(_B))
int n,f[200005];
char ch[100005],s[200005];
inline void manacher(){
	int mx=0,nw;
	for(int i=2;i<=n;++i){
		if(i<mx){
			f[i]=Min(f[(nw<<1)-i],f[nw]-(i-nw));
		}else{
			f[i]=1;
		}
		while(s[i+f[i]]==s[i-f[i]]){
			++f[i];
		}
		if(i+f[i]>mx){
			mx=i+f[i];
			nw=i;
		}
	}
}
void init(){
	cin>>(ch+1);
	n=strlen(ch+1);
	s[1]=s[2]='#';
	for(int i=1;i<=n;++i){
		s[(i<<1)+1]=ch[i];
		s[(i<<1)+2]='#';
	}
	n=(n<<1)+2;
	s[n+1]=0;
	manacher();
	int ans=0;
	for(int i=1;i<=n;++i){
		ans+=f[i]/2;
	} 
	printf("%d\n",ans);
}
int main(){
	init();
	return 0;
}

 

lp4555 国家集训队 最长双回文串

一开始以为是和最长双倍回文串一样的题,不过仔细看一下发现还是简单很多。
总之是麻辣烫(Manacher)的模板题。

Manacher是一\(O(n)\)种处理回文子串的通用方法。
具体来说,对于任意回文串,以它的对称轴为对称轴的所有子串都是回文串;不以它的对称轴为对称轴的所有子串都是对称的。
因此,我们可以分别考虑用着两种情况,使得我们只需要双指针扫一遍即可。
我们记\(f[i]\)表示,以第\(i\)个点为对称轴,最长的回文串半径。
首先我们维护当前对称轴\(mid\)以及当前右端点\(mx\),那么对于第一种情况,只需要拓展右端点即可。
下面我们考虑第二种情况。
首先,对于当前点\(i\),总是有\(i>mid\)。
那么,如果\(i<mx\),那么显然,在对称轴的另一边的点\(j=mid-(i-mid)\),在\(mx\)的范围内,两者必然是拥有共同的子串的。
这样算法就设计完了。

因为是双指针移动,所以复杂度是对的。
然后呢,对于每一个位置\(i\),我们考虑,维护\(l_{i}\)和\(r_{i}\),分别表示,\(i\)所在的回文串中最左的左端点和最右的右端点。
那么,\(ans=Max(r_{i}-l_{i})\)
处理方法的话,维护一个双指针即可。

#include
#include
#include
using namespace std;
#define Max(_A,_B) ((_A)>(_B)?(_A):(_B))
#define Min(_A,_B) ((_A)<(_B)?(_A):(_B))

int n,f[200005],l[200005],r[200005];
char ch[100005],s[200005];
inline void manacher(){
	int mx=0,nw;
	for(int i=2;i<=n;++i){
		if(imx){
			mx=i+f[i];
			nw=i;
		}
	}
}
void init(){
	cin>>(ch+1);
	n=strlen(ch+1);
	s[1]=s[2]='#';
	for(int i=1;i<=n;++i){
		s[(i<<1)+1]=ch[i];
		s[(i<<1)+2]='#';
	}
	n=(n<<1)+2;
	s[n+1]=0;
	manacher();
	int nw=1;
	for(int i=1;i<=n;++i){
		while(nw<=i+f[i]-1){
			l[nw]=i;
			++nw;
		}
	}
	nw=n+1;
	for(int i=n;i>=1;--i){
		while(nw>=i-f[i]+1){
			r[nw]=i;
			--nw;
		}
	}
	int ans=0;
	for(int i=1;i<=n;++i){
		ans=Max(ans,r[i]-l[i]);
	}
	printf("%d\n",ans);
}
int main(){
	init();
	return 0;
}