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;
}