C/C++教程

Codeforces Round #782 (Div. 2)

本文主要是介绍Codeforces Round #782 (Div. 2)，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

前言

两个 E，两个印度人。

\(\texttt{Rating Change:}\color{grey}{683}\color{black}\to \color{green}{1205}\)
\(\Delta={\color{green}{\texttt{522}}}\qquad \texttt{rank:285}\)

A

由于题目保证了红色一定大于蓝色，所以直接算在 \(b+1\) 个空隙中把红色均匀插入就可以了。然后模拟一遍输出。

My Code 
void solve(){
	int n,r,b;cin>>n>>r>>b;
	int num=r/(b+1);
	int rem=r%(b+1);
	if(0<rem){
		rep(j,1,num+1) cout<<"R";
	}else{
		rep(j,1,num) cout<<"R";
	}
	rep(i,1,b){
		cout<<"B";
		if(i<rem){
			rep(j,1,num+1) cout<<"R";
		}else{
			rep(j,1,num) cout<<"R";
		}
	}cout<<'\n';
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	int T;for(cin>>T;T--;) solve();
	return 0;
}

B

首先讨论 \(k\) 的奇偶性。如果是奇数，我们可以考虑把序列 01 翻转来把 \(k\) 变成偶数，这是合法的。接下来，每次对一个数操作相当于在最后的时候是翻转了它的二进制位的，所以从高到低翻转 \(0\) 就可以了。最后的时候如果 \(k\) 还有多，那就疯狂翻最低位一定是最优的。

My Code 
const int MAXN=2e5+10;
int cnt[MAXN];
void solve(){
	int n,k;cin>>n>>k;
	rep(i,1,n) cnt[i]=0;
	string b;cin>>b;
	if(k&1) rep(i,0,n-1) b[i]=(b[i]=='1'?'0':'1');
	rep(i,0,n-2) if(b[i]=='0'&&k) k--,b[i]='1',cnt[i+1]++;
	cnt[n]=k;if(k&1) b[n-1]=(b[n-1]=='1'?'0':'1');
	cout<<b<<'\n';
	rep(i,1,n) cout<<cnt[i]<<' ';cout<<'\n';
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	int T;for(cin>>T;T--;) solve();
	return 0;
}

C

给你一个数轴上若干个点，你的起点初始为 \(0\)，每个点初始是白色的，然后你需要把每个点染黑，代价是 \(b\times |s-t|\)。或者你可以改变你的起点到任意一个黑色的点，代价是 \(a\times |s-t|\)。求最终每个点都染黑的最小代价。

最直观的感受一定是你先染第一个点，然后把这个点定为你的起点。考虑什么情况会比这样子做更优。就是我们一定是到某一个位置就不改起点了，那么后面的点就全部要通过重新跑一遍来染色。预处理一下就可以啦。

My Code 
const int MAXN=2e5+10;
int x[MAXN],sum[MAXN],cur[MAXN];
void solve(){
	int n,a,b;cin>>n>>a>>b;
	rep(i,1,n) cin>>x[i],sum[i]=cur[i]=x[i]-x[i-1],sum[i]=sum[i]*(a+b);
	rep(i,2,n) sum[i]+=sum[i-1];int now=0,ans=INF;
	per(i,n,1) now+=cur[i]*(n-i+1)*b,ans=min(ans,now+sum[i-1]);
	cout<<ans<<'\n';
}
signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	int T;for(cin>>T;T--;) solve();
	return 0;
}

D

首先容易想到，\(a\) 的和除以 \(n\) 就是 \(b\) 中 \(1\) 的个数对吧。如果我们确定当前位，那么我们就能知道前缀中 \(1\) 的数量是怎么变的。接下来，我们在后缀的 \(k\) 个中减去 \(1\)，表示最后一次排序给序列带来的结果。然后我们每次考察一个位置是否等于 \(0\) 就能知道当前位是 \(0\) 还是 \(1\) 了。一个后缀中减去可以转化成前缀加然后判断是否和 \(a\) 相等，树状数组即可。

My Code 
const int MAXN=2e5+10;
struct BIT{
	int tr[MAXN],n;
	void init(int len){rep(i,0,len) tr[i]=0;n=len;}
	int lbt(int x){return x&(-x);}
	void upd(int x,int v){for(;x<=n;x+=lbt(x))tr[x]+=v;}
	int ask(int x){int ret=0;for(;x;x-=lbt(x))ret+=tr[x];return ret;}
}Tr;
int a[MAXN],ans[MAXN];
void solve(){
	int n,sum=0;cin>>n;
	rep(i,1,n) cin>>a[i],sum+=a[i];
	Tr.init(n);sum/=n;Tr.upd(n-sum+1,1);
	per(i,n,2){
		int cur=Tr.ask(i);
		if(cur^a[i]) ans[i]=1,sum--;
		else ans[i]=0;
		if(i^sum) Tr.upd(i-sum,1);
	}ans[1]=sum;
	rep(i,1,n) cout<<ans[i]<<' ';cout<<'\n';
}
signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	int T;for(cin>>T;T--;) solve();
	return 0;
}

E

神奇的简单题/qd。容易发现答案只能是 \(0\) 或者 \(1\) 或者 \(2\)。然后考虑 \(0\) 的情况，你对每个二进制位维护一个并查集然后查连通性就可以了。考虑 \(1\)，既然不是 \(0\)，那我们就只要判断中间会不会出现 \(1\)。也很好做，你考虑路径一定是这样的：先是一段与和为奇数的非 \(1\)，然后是一段与和为偶数的，由于 \(mex\) 不是 \(0\)，所以这样一定会出现 \(0\) 而不出现 \(1\)。所以我们需要维护联通块是边权为奇数的并且 \(i\) 位都是 \(1\) 的，并查集即可。

My Code 
const int MAXN=1e5+10;
int ok[MAXN];
struct dsu{
	int f[MAXN];
	int find(int x){while(x^f[x])x=f[x]=f[f[x]];return x;}
	void merge(int x,int y){if(find(x)^find(y))f[find(x)]=find(y);}
}D[35],C[35];
int sok[35][MAXN];
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	int n,m;cin>>n>>m;
	rep(i,1,n) rep(b,0,30) D[b].f[i]=i,C[b].f[i]=i;
	rep(i,1,m){
		int u,v,w;cin>>u>>v>>w;
		rep(b,0,30) if(w&(1<<b)) D[b].merge(u,v);
		if(w%2==0) ok[u]=ok[v]=1;
		else rep(b,1,30) if(w&(1<<b)) C[b].merge(u,v);
	}
	rep(i,1,n) if(ok[i]) rep(b,1,30)
		sok[b][C[b].find(i)]=1;
	int Q,u,v;cin>>Q;
	while(Q--){
		cin>>u>>v;
		int ans=2;
		rep(b,0,30)
			if(D[b].find(u)==D[b].find(v))
			{ans=0;break;}
		if(ans==2){
			rep(b,1,30)
				if(sok[b][C[b].find(u)])
				{ans=1;break;}
		}
		cout<<ans<<'\n';
	}
	return 0;
}

F

牛逼博弈，不会。

这篇关于Codeforces Round #782 (Div. 2)的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！
您可能喜欢
栏目导航