A. Red Versus Blue

题目

分析

红方蓝方打比赛，确定红方比蓝方厉害，连胜的概率最低，排出比赛结果可能的序列。

因为R比B多，所以考虑在B之间插入R，b个B需要将R分为b+1组，需要连胜数最小，就把R均分插入B之间，所以，先求出r是b+1的最小倍数，之后再将剩余的每个插一个到每一组中。

代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll maxn=1e6+10;
const ll N=32768;
const ll INF=0x3f3f3f3f;
const double pi=acos(-1);int main()
{int t;cin>>t;while(t--){int n,r,b;cin>>n>>r>>b;int m=r/(b+1);int mm=r%(b+1);if(b==1){for(int i=1;i<=r/2;i++){cout<<"R";}cout<<"B";for(int i=r/2+1;i<n;i++){cout<<"R";}cout<<endl;continue;}for(int i=1;i<=m;i++){cout<<"R";}if(mm){cout<<"R";mm--;}while(b--){cout<<"B";for(int i=1;i<=m;i++){cout<<"R";}if(mm){cout<<"R";mm--;}}cout<<endl;} return 0;
}

B. Bit Flipping

题目

分析

给一个01串，必须用k步翻转串（选定一个位置，除了本位都反转），使结果01串最大。

因为要使01串最大，所以尽可能让左边数位为1。所以从左边开始遍历。

如果是1，判断操作数是否为偶数，如果不是，对它进行一次操作，确保它被反转了偶数次，使它原数不变，仍为1；

如果是0，判断操作数是否为奇数，如果不是，对它进行一次操作，确保它被反转了奇数次，使它从0变为1；

当遍历到最后一位，因为最大，所以不能改变前面的数字，所以直接判断，之前操作数的奇偶，判断它是否能够被改变。

代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll maxn=2e5+10;
const ll N=32768;
const ll INF=0x3f3f3f3f;
const double pi=acos(-1);
int ans[maxn];int main()
{int t;cin>>t;while(t--){memset(ans,0,sizeof(ans));int n,k;string s;cin>>n>>k>>s;int kk=k;for(int i=0;i<s.size();i++){if(i==n-1){int tt=k-kk;if(s[i]=='1'){if(tt%2){s[i]='0';}ans[i]=kk;}else {if(tt%2){s[i]='1';}ans[i]=kk;}continue;}if(s[i]=='1'){if(k%2==1&&kk){ans[i]=1;kk--;}else if(k%2&&!kk){s[i]='0';}}else {if(k%2==0&&kk){ans[i]=1;kk--;s[i]='1';}else if(k%2){s[i]='1';}}}cout<<s<<endl;for(int i=0;i<n;i++){cout<<ans[i]<<" ";}cout<<endl;} return 0;
}

C. Line Empire

题目

分析

你是国王，你要占领别的国家，默认首都在0处，你要占领所有国家。

你有两种操作，一种是将首都从i迁移到j处，需要花费，另一种是，需要花费，从首都i处占领j。输出最小花费。

因为是数轴，所以考虑，每个国家的值为单调递增。设全部占领后，首都位置为x，所以需要的总花费为两部分，一部分为，从0处一边占领一边迁都的花费，和x之后只需占领的花费。二分查找一下临界值的位置，如果前半部分的增加值比后半部分的减少值更小，则此处最优。（懒得打公式了，就是把每一项列出来，然后消消消，就可以推出来）

代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll maxn=2e5+10;
const ll N=32768;
const ll INF=0x3f3f3f3f;
const double pi=acos(-1);
ll c[maxn];int main()
{int t;cin>>t;while(t--){ll n,a,b;cin>>n>>a>>b;for(int i=1;i<=n;i++){cin>>c[i];}int l=0,r=n;while(r>l){int mid=(l+r)/2;if((n-mid)*b>(a+b)) l=mid+1;else r=mid;}ll ans=(c[l]-c[0])*(a+b);for(int i=l+1;i<=n;i++){ans=ans+b*(c[i]-c[l]);}cout<<ans<<endl;} return 0;
}

D. Reverse Sort Sum

题目

分析

数组a是有01构成的数组，f(i,a)是将数组a的前i项排序，每次排序结果存储在b中，c是所有b的和。给出数组c，求数组a。

首先可以得出数组a中1的总数为c中所有1的和除n（即cnt=sum/n）。因为后面的加进一个1来，排序后有影响，而前面的没有，所以倒序遍历，通过比较当前位置的c[i]是否需要新加一个1，来满足排序后本位1的个数，给a数组赋值。然后对cnt--。

感觉解释不是很清楚，附上别人写的题解

代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll maxn=2e5+10;
const ll mod=32768;
const ll INF=0x3f3f3f3f;
const double pi=acos(-1);
int a[maxn],c[maxn],b[maxn];int main()
{int t;cin>>t;while(t--){int n;cin>>n;ll sum=0;memset(a,0,sizeof(a));memset(b,0,sizeof(b));for(int i=1;i<=n;i++){cin>>c[i];sum+=c[i]; }ll cnt=sum/n;int f=0;for(int i=n;i>=1&&cnt>=0;i--){f--;b[i-cnt]++;f+=b[i];if(c[i]+f>0){cnt--;a[i]=1;}}if(cnt==1){a[1]=1;}for(int i=1;i<=n;i++){cout<<a[i]<<" ";}cout<<endl;	}return 0;
}