[cf]Codeforces Round #782

目录

• • • 前言
    • 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−(n−1)的位置

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

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

显然我们只需要从高位到地位将所有 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.(完全不会,蹲大佬的题解)