Codeforces Round #629 (Div. 3)

题目链接：https://codeforces.com/contest/1328

A. Divisibility Problem

签到题。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
void solve(){
    ll a,b;cin>>a>>b;
    cout<<(b-a%b)%b<<"
";
}
int main()
{
    int t;cin>>t;
    while(t--)
        solve();
    return 0;
}

B. K-th Beautiful String

只移动第一个b发现前后序次之差为等差数列。

#include <bits/stdc++.h>
using namespace std;
void solve(){
    int n,k;cin>>n>>k;
    int l=n-2;
    int sum=1,step=1;
    while(sum+step<=k){
        sum+=step++;
        --l;
    }
    k-=sum;
    string s(n,'a');
    s[l]=s[n-1-k]='b';
    cout<<s<<"
";
}
int main()
{
    int t;cin>>t;
    while(t--)
        solve();
    return 0;
}

C. Ternary XOR

第一次不能平分后较大者不再取数。

#include <bits/stdc++.h>
using namespace std;
void solve(){
    int n;cin>>n;
    string s;cin>>s;
    string s1,s2;
    bool flag=true;
    for(char c:s){
        if(c=='2'){
            if(flag){
                s1+='1';
                s2+='1';
            }else{
                s1+='0';
                s2+='2';
            }
        }else if(c=='1'){
            if(flag){
                s1+='1';
                s2+='0';
                flag=false;
            }else{
                s1+='0';
                s2+='1';
            }
        }else{
            s1+='0';
            s2+='0';
        }
    }
    cout<<s1<<"
"<<s2<<"
";
}
int main()
{
    int t;cin>>t;
    while(t--)
        solve();
    return 0;
}

D. Carousel

分情况讨论。

#include <bits/stdc++.h>
using namespace std;
void solve(){
    int n;cin>>n;
    int a[n];for(int &i:a) cin>>i;
    int res[n]={};
    bool same=true;
    for(int i=1;i<n;i++) if(a[i]!=a[i-1]) same=false;
    if(same)
        fill(res,res+n,1);
    else if(n%2==0)
        for(int i=0;i<n;i++) res[i]=(i&1?1:2);
    else
        for(int i=0;i<n;i++)
            if(a[i]==a[(i+1)%n]){
                for(int j=i-1;j>=0;j--) res[j]=(j&1?1:2);
                for(int j=i+2;j<n;j++) res[j]=(j&1?2:1);
                res[i]=res[(i+1)%n]=(i&1?1:2);
                break;
            }
    if(res[0]==0){
        res[0]=3;
        for(int i=1;i<n;i++) res[i]=(i&1?1:2);
    }
    cout<<max(res[0],res[1])<<"
";
    for(int i=0;i<n;i++) cout<<res[i]<<" 
"[i==n-1];
}
int main()
{
    int t;cin>>t;
    while(t--)
        solve();
    return 0;
}

F. Make k Equal

假如用1，3组成两个相等的数，取1，2，3所消耗的代价是相同的，所以只需枚举数组中的每个元素即可。排序后，因为只能最小值加一或最大值减一，所以若某值需取用其他元素，该值的一侧一定均为x-1或x+1。依次枚举数组中每个元素，因为相同元素不必变换，所以记录下排序后同一值的左右端点，利用前后缀和计算将左端点左侧变为x-1和将右端点右侧变为x+1的代价，取法有三：只取左侧，只取右侧，左右都取，取三者最小值，若某值区间长度大于等于k，最小值为0，break输出。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int M=2e5+10;
const ll INF=1e18;
int main()
{
    int n,k;cin>>n>>k;
    ll a[M];for(int i=1;i<=n;i++) cin>>a[i];
    sort(a+1,a+n+1);
 
    map<int,int> l,r;
    for(int i=1;i<=n;i++) if(l[a[i]]==0) l[a[i]]=i;
    for(int i=n;i>=1;i--) if(r[a[i]]==0) r[a[i]]=i;
    
    ll pre[M]={},suf[M]={};
    for(int i=1;i<=n;i++) pre[i]=pre[i-1]+a[i];
    for(int i=n;i>=1;i--) suf[i]=suf[i+1]+a[i];
    
    ll mi=INF,cost1,cost2;
    for(int i=1;i<=n;i++){
        int sub=k-r[a[i]]+l[a[i]]-1;//该区间外还需再取几个数
        if(sub<=0){mi=0;break;}

        cost1=(l[a[i]]-1)*(a[i]-1)-pre[l[a[i]]-1];
        cost2=suf[r[a[i]]+1]-(n-r[a[i]])*(a[i]+1);

        if(i>=k) mi=min(mi,cost1+sub);
        if(i<=n-k+1) mi=min(mi,cost2+sub);
        mi=min(mi,cost1+cost2+sub);
    }
    cout<<mi<<"
";

    return 0;
}