[cf]Codeforces Round #782

[cf]Codeforces Round #782 ,第1张

目录
      • 前言
      • A.Red Versus Blue
      • code
      • B. Bit Flipping
      • code
      • C Line Empire
      • code
      • D.(完全不会,蹲大佬的题解)

前言

传送门 :
(那天人们又想起了被蓝名支配的恐惧)

A.Red Versus Blue

题意 :
给定你 n , r , b n,r,b n,r,b 表示 字符长度, R R R的数量, B B B的数量

问使得 连续 R R R最少的方案

思路 :
显然,我们一开始都是想到的分组,也就是将 R R R分成 B + 1 B+1 B+1

但是很多情况我们都无法完全分组,因此我们还需要将剩下的余数塞回我们已经处理的分组之中

然后输出即可

code
const int N = 110;

int n,R,B;

int a[N];
void solve(){
	cin>>n>>R>>B;
	
	int tail = R/(B+1);
	int remain = R%(B+1);
	
	for(int i=1;i<=B+1;i ++ ) a[i] = tail;
	for(int i=1;i<=remain;i++) a[i]++;
	
//	cout<
	
	for(int i=1;i<=B+1;i++){
		for(int j=1;j<=a[i];j ++ )cout<<"R";
		if(i!=B+1)cout<<"B";
	}
	cout<<endl;
}
B. Bit Flipping

题意 :(屎题 真难写)

给定 n , k n,k n,k表示字符串长度和 *** 作次数

*** 作描述如下 :

对于给定的 01 01 01字符串,你可以选择一个 i i i使得当前位置的数不变,其余翻转

询问 *** 作完成之后的 最大字符串和各个位置的次数

思路 :

这种取反的题,一般都和 2 2 2有关,因为来回两次回到原位

当然对于这种题,我们一般考虑 将多余的 *** 作放到最后一位来回 *** 作

显然

  • 如果是奇数的话,我们最后将多余的 1 1 1对最后一位 *** 作,前面的 *** 作都不影响最后一位,当然如果不多于的话,那么最后一位必然取反,因为前面已经有 0 0 0把 *** 作数吃掉了
  • 如果是偶数的话,不管怎么 *** 作,最后一位仍然不会变

因此我们只考虑 0 − ( n − 1 ) 0-(n-1) 0(n1)的位置

如果是奇数,我们先对所有数取反(相当于在最后一位 *** 作)

然后转换为偶数的形式,我们再考虑偶数怎么 *** 作

显然我们只需要从高位到地位将所有 0 0 0变为 1 1 1 即可

因为对于每次 *** 作我们都可以把 0 0 0固定住,然后让前面的 1 1 1全部变为 0 0 0,然后为了保证 *** 作的完全利用,我们在让下次碰到 0 0 0的时候变成 1 1 1即可

总之总结一个字 : 贪心即可

code
void solve(){
	int n,k;cin>>n>>k;
	string s;cin>>s;
	
	vector<int> ans(n);
	 
	if(k&1){
		for(auto &c : s){
			if(c == '0') c = '1';
			else c = '0';
		}
	}
	
	for(int i=0;i<n-1;i++){
		if(k>0 && s[i] =='0'){
			ans[i]++;
			s[i] ='1';
			k--;
		}
	}
	
	ans[n-1]+=k;
	if(k%2){
		if(s.back() == '0') s.back() = '1';
		 else s.back() = '0';
	}
	
	cout<<s<<endl;
	for(auto x  : ans)cout<<x<<" ";
	cout<<endl;
	
	
}
int main(){
    int t;cin>>t;while(t--)
    solve();
    return 0 ;
}
C Line Empire

W i z C o d e WizCode WizCode大佬的图,写的很详细了我就不乱添足了

code
const int N = 2e5+10;

ll sum[N];
ll x[N];

void solve(){
	int n;cin>>n;
	ll a,b;cin>>a>>b;
	
	for(int i=1;i<=n;i++) cin>>x[i];
	
	sum[n+1] = 0 ;
	for(int i=n;i>=1;i --) sum[i]  = x[i]+sum[i+1];
	
	ll res = 1e18;
	ll pre = 0;
	ll t ;
	
	for(int i =0 ;i<=n;i++){
		if(i){
			pre += a*(x[i] - x[i-1]) + b*(x[i] -x[i-1]);
		}
		t = b*(sum[i+1] - x[i]*(n-i));
		res = min(res,pre+t);
	}
	cout<<res<<endl;
	
}
D.(完全不会,蹲大佬的题解)

欢迎分享,转载请注明来源:内存溢出

原文地址: http://outofmemory.cn/langs/707124.html

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2022-04-24
下一篇 2022-04-24

发表评论

登录后才能评论

评论列表(0条)

保存