A.To Zero

签到题

void solve()
{	int n,k;cin>>n>>k;int k2=k/2*2;int k1=(k2<k)?k:k-1;int cnt=0;if(n%2==1){n-=k1;cnt++;cnt+=(n/k2)+(n%k2!=0);}else {cnt=(n/k2)+(n%k2!=0);}cout<<cnt<<endl;}

B.Array Recoloring

手推一下可以发现，答案其实就是前k+1大的数 。但是需要注意的是需要特判一下 k==1 的情况。

此时最后一个数只能从两侧选。

void solve()
{	int n,k;cin>>n>>k;vector<int> a(n+1);for (int i=1;i<=n;i++){cin>>a[i];}if(k==1){//特判int ans=0;for (int i=1;i<=n;i++){if(i==1||i==n){ans=max(ans,a[1]+a[n]);}else {int tmp = a[i];ans=max(ans,tmp+max(a[1],a[n]));}}cout<<ans<<endl;return ;}sort(all2(a),greater<int>());int sum=0;for(int i=1;i<=k+1;i++){sum+=a[i];}cout<<sum<<endl;
}

C.Two Colors

枚举每一个数，二分找到和大于等于n的第一个数，然后就是求这后面满足条件的数字的条件和。条件就是每一个数减去能覆盖另一种颜色的数量（只需要保证另外一种颜色至少保留一个即可）。

这个过程可以使用前缀和来优化。详情见代码，另外让初始的每一个颜色都小于等于n-1，这样就可以直接求得这个颜色对于其他颜色的覆盖情况了，而不用担心超出n的情况。

void solve()
{	int n,m;cin>>n>>m;vi a(m+1);rep(i,1,m){cin>>a[i];chmin(a[i],n-1);}sort(all2(a));vi s(m+10);rep(i,1,m){s[i]=s[i-1]+a[i];}int sum=0;rep(i,1,m){auto pos = lb(all2(a),n-a[i])-a.begin();chmax(pos,i+1);int len = m-pos+1;sum-=(n-a[i]-1)*len;sum+=(s[m]-s[pos-1]);}cout<<sum*2<<endl;
}

D.Equalization

发现其实就是找到x和y的最大前缀。所以只需要确定x,y分别的右移位数即可，可以暴力枚举，时间复杂度为 O(60^2) 。使用 背包预处理 每种移位情况的的最小代价。

int dp[100][100];
void init()
{memset(dp,0x3f,sizeof dp);dp[0][0]=0;rep(i,0,60){per(j,60,0){per(k,60,0){if(j>=i){dp[j][k]=min(dp[j][k],dp[j-i][k]+(1ll<<i));}if(k>=i){dp[j][k]=min(dp[j][k],dp[j][k-i]+(1ll<<i));}}}}
}
void solve()
{	int x,y;cin>>x>>y;int ans=1e18;rep(i,0,60){rep(j,0,60){if((x>>i)==(y>>j)){ans=min(ans,dp[i][j]);}}}cout<<ans<<endl;
}