526互联

Educational Codeforces Round 128 (Rated for Div. 2)

发布时间 2023-11-02 17:02:25作者: gan_coder

添加链接描述

C题显然二分0的数量，然后双指针，算一下前缀和后缀1的数量即可。

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<map>
#include<vector>
#include<set>
#define A puts("YES")
#define B puts("NO")
#define fo(i,a,b) for (int (i)=(a);(i)<=(b);(i)++)
#define fd(i,b,a) for (int (i)=(b);(i)>=(a);(i)--)
#define mk(x,y) make_pair((x),(y))
#define lc (o<<1)
#define rc (o<<1|1)
using namespace std;
//typedef __int128 i128;
typedef double db;
typedef long long ll;
const int mo=1e9+7;
const int N=2e5+5;
int l,r,mid,n,t[N];
char s[N];
bool pd(int x){
	int j=0;
	int tot=0;
	for (int i=1;i<=n;i++) {
		if (j<i) {
			j=i;
			if (s[i]=='0') ++tot;
		}
		
		while (tot<x && j<n) {
			j++;
			if (s[j]=='0') tot++;
		}
		while (j<n && s[j+1]!='0') j++;
		
		if (t[i-1]+ t[n+1]-t[j] <=x) return 1;
		
		if (s[i]=='0') tot--;

	}
	return 0;
}
int main()
{
//	freopen("data.in","r",stdin);
//	freopen("ans.out","w",stdout);
	
	int T;
	scanf("%d",&T);
	while (T--){
		scanf("%s",s+1);
		n=strlen(s+1);
		fo(i,1,n) {
			t[i]=t[i-1]+(s[i]=='1');
		}
		t[n+1]=t[n];
		
		l=0; r=n;
		while (l<r){
			mid=(l+r)>>1;
			if (pd(mid)) r=mid;
			else l=mid+1;
		}
		printf("%d\n",l);
	}

	return 0;
}

E题开始写了一大坨，先将那些连成一块的直接合并，然后又是讨论，写起来很麻烦。

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<map>
#include<vector>
#include<set>
#define A puts("YES")
#define B puts("NO")
#define fo(i,a,b) for (int (i)=(a);(i)<=(b);(i)++)
#define fd(i,b,a) for (int (i)=(b);(i)>=(a);(i)--)
#define mk(x,y) make_pair((x),(y))
#define lc (o<<1)
#define rc (o<<1|1)
using namespace std;
//typedef __int128 i128;
typedef double db;
typedef long long ll;
const int mo=1e9+7;
const int inf=1<<30;
const int N=2e5+5;
char a[N],b[N],s[N][2];
int n,tot,sz[N],l[N],r[N];
int t[N][2];
int f[N][2][2];
int get(int p){
	if (!p) return 0;
	return (a[p]=='.')*2+(b[p]=='.');
}
void cmin(int &x,int y){
	x=min(x,y);
}
int main()
{
//	freopen("data.in","r",stdin);
//	freopen("ans.out","w",stdout)
	
	int T;
	scanf("%d",&T);
	while (T--){
		scanf("%d",&n);
		
		scanf("%s",a+1);
		scanf("%s",b+1);
		
		fo(i,1,n) if (a[i]=='.') a[i]='*'; else a[i]='.';
		fo(i,1,n) if (b[i]=='.') b[i]='*'; else b[i]='.';
		
		tot=0;
		fo(i,1,n) {	
			if (!get(i)) continue;
			if (!(get(i)&get(i-1))){
				++tot;
				sz[tot]=(a[i]=='.')+(b[i]=='.');
				l[tot]=i;
			}
			else {
				sz[tot]+=(a[i]=='.')+(b[i]=='.');
			}
		
			if (i==n) r[tot]=n;
			else if (!(get(i)&get(i+1))) r[tot]=i;

		}
		fo(i,0,tot) {
			f[i][0][0]=f[i][0][1]=inf;
			f[i][1][0]=f[i][1][1]=inf;
		}


		
//		fo(i,1,n) s[i][0]=a[i],s[i][1]=b[i];
//		fo(i,1,n) t[i][0]=l[i],t[i][1]=r[i];
//		
//		fo(x,0,1) fo(y,0,1) {
//			f[1][x][y]=sz[1]-s[][y];
//		}
		
		if (a[l[1]]=='.') f[1][0][0]=sz[1]-1; else f[1][0][0]=sz[1];
		if (b[l[1]]=='.') f[1][0][1]=sz[1]-1; else f[1][0][1]=sz[1];
		if (a[r[1]]=='.') f[1][1][0]=sz[1]-1; else f[1][1][0]=sz[1];
		if (b[r[1]]=='.') f[1][1][1]=sz[1]-1; else f[1][1][1]=sz[1];
		
		fo(i,2,tot) {
		
			if (a[l[i]]=='.') {
				cmin(f[i][0][0], f[i-1][0][0]+l[i]-l[i-1]);  
				cmin(f[i][0][0], f[i-1][0][1]+l[i]-l[i-1]+(b[l[i]]!='.'));
				cmin(f[i][0][0], f[i-1][1][0]+l[i]-r[i-1]);
				cmin(f[i][0][0], f[i-1][1][1]+l[i]-r[i-1]+(b[l[i]]!='.'));
			}
			else {
				cmin(f[i][0][0], f[i-1][0][0]+l[i]-l[i-1]+1);  
				cmin(f[i][0][0], f[i-1][0][1]+l[i]-l[i-1]+1);
				cmin(f[i][0][0], f[i-1][1][0]+l[i]-r[i-1]+1);
				cmin(f[i][0][0], f[i-1][1][1]+l[i]-r[i-1]+1);
			}
		
			if (b[l[i]]=='.') {
				cmin(f[i][0][1], f[i-1][0][0]+l[i]-l[i-1]+(a[l[i]]!='.')); 
				cmin(f[i][0][1], f[i-1][0][1]+l[i]-l[i-1]);
				cmin(f[i][0][1], f[i-1][1][0]+l[i]-r[i-1]+(a[l[i]]!='.'));
				cmin(f[i][0][1], f[i-1][1][1]+l[i]-r[i-1]);
			}
			else {
				cmin(f[i][0][1], f[i-1][0][0]+l[i]-l[i-1]+1); 
				cmin(f[i][0][1], f[i-1][0][1]+l[i]-l[i-1]+1);
				cmin(f[i][0][1], f[i-1][1][0]+l[i]-r[i-1]+1);
				cmin(f[i][0][1], f[i-1][1][1]+l[i]-r[i-1]+1);
			}
		
			
 
			cmin(f[i][1][0], f[i-1][0][0]+l[i]-l[i-1]+(a[l[i]]!='.')+(a[r[i]]!='.'));
			cmin(f[i][1][0], f[i-1][0][1]+l[i]-l[i-1]+(b[l[i]]!='.')+(a[r[i]]!='.'));
			cmin(f[i][1][0], f[i-1][1][0]+l[i]-r[i-1]+(a[l[i]]!='.')+(a[r[i]]!='.'));
			cmin(f[i][1][0], f[i-1][1][1]+l[i]-r[i-1]+(b[l[i]]!='.')+(a[r[i]]!='.'));
 
		
			cmin(f[i][1][1], f[i-1][0][0]+l[i]-l[i-1]+(a[l[i]]!='.')+(b[r[i]]!='.'));
			cmin(f[i][1][1], f[i-1][0][1]+l[i]-l[i-1]+(b[l[i]]!='.')+(b[r[i]]!='.'));
			cmin(f[i][1][1], f[i-1][1][0]+l[i]-r[i-1]+(a[l[i]]!='.')+(b[r[i]]!='.'));
			cmin(f[i][1][1], f[i-1][1][1]+l[i]-r[i-1]+(b[l[i]]!='.')+(b[r[i]]!='.'));
		
			if (l[i]==r[i]) {
				f[i][1][0]=f[i][0][0];
				f[i][1][1]=f[i][0][1];
			}
		
		
//			cmin(f[i][0][0], f[i-1][0][0]+ l[i]-l[i-1]+ (a[l[i]]!='.' ));
//			cmin(f[i][0][0], f[i-1][0][1]+ l[i]-l[i-1]+1+ (a[l[i]]!='.'));
//			cmin(f[i][0][0], f[i-1][1][0]+ l[i]-l[i-1]+ (a[l[i]]!='.'));
//			cmin(f[i][0][0], f[i-1][1][1]+ l[i]-l[i-1]+1+ (a[l[i]]!='.'));
//			
//	
//			cmin(f[i][0][1], f[i-1][0][0]+ l[i]-l[i-1]+1 + (b[l[i]]!='.'));
//			cmin(f[i][0][1], f[i-1][0][1]+ l[i]-l[i-1]+ (b[l[i]]!='.'));
//			cmin(f[i][0][1], f[i-1][1][0]+ l[i]-r[i-1]+1+ (b[l[i]]!='.'));
//			cmin(f[i][0][1], f[i-1][1][1]+ l[i]-r[i-1]+ (b[l[i]]!='.'));
//		
//		
//			cmin(f[i][1][0], f[i-1][0][0]+ r[i]-l[i-1] + (a[r[i]]!='.'));
//			cmin(f[i][1][0], f[i-1][0][1]+ r[i]-l[i-1]+1+ (a[r[i]]!='.'));
//			cmin(f[i][1][0], f[i-1][1][0]+ r[i]-r[i-1]+ (a[r[i]]!='.'));
//			cmin(f[i][1][0], f[i-1][1][1]+ r[i]-r[i-1]+1+ (a[r[i]]!='.'));
//				
//			cmin(f[i][1][1], f[i-1][0][0]+ r[i]-l[i-1] + (b[r[i]]!='.'));
//			cmin(f[i][1][1], f[i-1][0][1]+ r[i]-l[i-1]+1+ (b[r[i]]!='.'));
//			cmin(f[i][1][1], f[i-1][1][0]+ r[i]-r[i-1]+ (b[r[i]]!='.'));
//			cmin(f[i][1][1], f[i-1][1][1]+ r[i]-r[i-1]+1+ (b[r[i]]!='.'));
//			
			fo(x,0,1) fo(y,0,1) f[i][x][y]+=sz[i]-1;
		}
		int ans=inf;
		fo(i,0,1) fo(j,0,1) ans=min(ans, f[tot][i][j]);
		printf("%d\n",ans);
		
//		printf("%d\n",f[3][1][1]);
	}

	return 0;
}

但其实有更加清真的写法，不用一整个块考虑，直接一列一列转移就行。

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<map>
#include<vector>
#include<set>
#define A puts("YES")
#define B puts("NO")
#define fo(i,a,b) for (int (i)=(a);(i)<=(b);(i)++)
#define fd(i,b,a) for (int (i)=(b);(i)>=(a);(i)--)
#define mk(x,y) make_pair((x),(y))
#define lc (o<<1)
#define rc (o<<1|1)
using namespace std;
//typedef __int128 i128;
typedef double db;
typedef long long ll;
const int mo=1e9+7;
const int inf=1<<30;
const int N=2e5+5;
int n,f[N][2],c;
char a[N],b[N];
void cmin(int &x,int y){
	x=min(x,y);
}
int main()
{
//	freopen("data.in","r",stdin);
//	freopen("ans.out","w",stdout)
	
	int T;
	scanf("%d",&T);
	while (T--){
		scanf("%d",&n);
		
		scanf("%s",a+1);
		scanf("%s",b+1);
			
		fo(i,0,n) f[i][0]=f[i][1]=inf;
		int l=0;
		fo(i,1,n) {
			if (a[i]!='*' && b[i]!='*') continue;
			if (!l) {
				c=(a[i]=='*')+(b[i]=='*')-1;
				f[i][0]=c+(a[i]!='*');
				f[i][1]=c+(b[i]!='*');
				l=i;
			}
			else {
				c=(a[i]=='*')+(b[i]=='*')-1;
				
				cmin(f[i][0], f[l][0]+c+(a[i]!='*'));
				cmin(f[i][0], f[l][1]+c+(a[i]!='*')+(b[i]!='*'));
				cmin(f[i][1], f[l][0]+c+(b[i]!='*')+(a[i]!='*'));
				cmin(f[i][1], f[l][1]+c+(b[i]!='*'));
				
				
				f[i][0]+=i-l;
				f[i][1]+=i-l;
				l=i;

				
			}
		}
			
		printf("%d\n",min(f[l][0],f[l][1]));
	}

	return 0;
}