首页 > 其他分享 >Educational Codeforces Round 128 (Rated for Div. 2)

Educational Codeforces Round 128 (Rated for Div. 2)

时间：2023-11-02 17:14:30浏览次数：51  
标签：Educational Rated puts int Codeforces mid pair include define

添加链接描述

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

标签：Educational,Rated,puts,int,Codeforces,mid,pair,include,define
From： https://www.cnblogs.com/ganking/p/17805799.html

相关文章

  • Codeforces Round 906 (Div. 2)
    CodeforcesRound906(Div.2)比赛链接A.Doremy'sPaint3题目链接判断给定的数组是不是满足a1+a2=a2+a3=a3+a4=......=an-1+anA思路：这个题一开始没有读仔细问题，导致一时间出错了，后来读清楚问题之后发现其实这个数组中只能出现两个数字，且两个数字之间的差值最多是1A代码：......
  • Codeforces Round 907 (Div. 2) B. Deja Vu（二分+后缀和+位运算）
    CodeforcesRound907(Div.2)B.DejaVu思路：预处理31位的\(2^x\)存在\(tmp_i\)对于输入\(a_i\)，通过查找最后一个二进制1位置，存在\(x0_i\)由题意可知，对于输入的\(x\)，如果有\(a_i\)可整除\(x\)，则会使\(a_i\)加上\(2^{x-1}\)所以之后除非是\(x-1\)，否则无效，因此把输入\(x\)......
  • Codeforces Round 907 (Div. 2)
    CodeforcesRound907(Div.2)A.SortingwithTwos题意：给一个长度为n的数组，可以做任意次以下操作：选择一个整数m，将1-2m的数减1。若能使数组变为一个单调递增的数组则输出YES，否则输出NO分析：只需要保证2m+1-2m+1单调递增即可代码：#include<bits/stdc++.h>usingnamespace......
  • mysql数据库管理-FEDERATED存储引擎远程链接MYSQL
    开启FEDERATED存储引擎1.1、查看存储引擎存在的FEDERATED存储引擎就配置文件开启不存在就安装查看showengines;YES支持并开启DEFAULT支持并开启,并且为默认引擎；NO不支持；DISABLED支持,但未开启。创建federated引擎表创建语句最好和原表语句一样，当然去掉id的auto之类的。CREATE......
  • Codeforces Round 906 Div. 1 (CF1889)
    貌似现在发周六的CF题解已经失去了时效性，不过问题不大。A.QingshanLovesStrings2Description定义一个长度为\(k\)的\(01\)串\(s\)是好的，当且仅当\(\foralli\in[1,k],s_i\neqs_{k-i+1}\)。现给你一个串，每次操作你可以在任意位置插入一对\(01\)。请构造操作方......
  • Codeforces Round 906 (Div. 2)A-E1
    A.Doremy'sPaint3记数组中数的种类数为\(k\)，当\(k=1\)时，答案为\(yes\)；当\(k=2\)时，记两个种类的数的个数差为\(d\)，当\(d≤1\)时，答案为\(yes\)；其他情况答案为\(no\)。时间复杂度：\(O(nlogn)\)1voidsolve()2{3intn;cin>>n;45map<int,int>mp;6......
  • Codeforces Round 895
    提炼感觉这种题还是很金典的我们看到乘积就应该想到其很容易爆而我们省1的话也最多就是2e5数量级的我们为了省事不用算上界可以直接把这个上界设为1e9也不会爆LL只要乘积突破这个上界我们就肯定要是有旁边的大于1的数我们都要吃掉因为增量都超过了1e9那么多我们只要......
  • codeforces 1829G. Hits Different 容斥原理+记忆化搜索
    题目描述：给定一个n，把n给打倒，然后递归的求出包含n在内的上面所有的会倒下的瓶子值的平方和。这里使用二分先求出目前给定的n的行号i和列号j。观察可以发现，对于所有的列号j，j=1或者j=i时，是需要考虑往上单边的总和，其他情况都有两个分支。再观察可以发现，两个分支在再上一行的重合部......
  • CodeForces 1246F Cursor Distance
    洛谷传送门CF传送门发现一个性质：能跳不超过\(j\)步到达\(i\)的所有点形成一段区间。设这这段区间为\([L_{i,j},R_{i,j}]\)。那么答案即为：\[\sum\limits_{i=1}^n\sum\limits_{j=0}n-R_{i,j}+L_{i,j}-1\]并且：\[[L_{i,j},R_{i,j}]=\bigcup\limits_......
  • Codeforces Round 906 (Div. 2) A-E1
    比赛地址A.Doremy'sPaint3题意：给出一个数组\(b\)，问能否通过重新排序使得数组满足\(b_1+b_2=b_2+b_3=...=b_{n-1}+b_{n}\)Solution首先判断元素个数如果是1，则满足条件如果是2，需判断不同元素个数的差是否小于等于1其余的均不满足条件voidsolve(){intn;cin>......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99