Codeforces Round ＃652 (Div. 2)

Codeforces Round #652 (Div. 2) /cf1369

Summary after the game ：

The code must be clean , On the court A 了 2 Avenue , however B I have read the question , Although I think there may be bug, Not optimized enough , No matter the , The result was a heavy sentence after the game , also T 了 , Then put the code cout<<endl Switch to printf("\n"), It's over .

It can be seen that there should be no rough way of doing things as soon as they are done .

Of course B topic , My code idea is not simple enough , The analysis in the official tutorial is very wonderful and detailed .

B topic

The question ： There is a string of 01 character , If x[i]=‘1’,x[i+1]=‘0’, Then it can be eliminated x[i] or x[i+1], Ask what is the simplest result of elimination , The most concise means that the string is the shortest and the dictionary order is the smallest .

Official explanation

#include <iostream>
#include <string>
 
using namespace std;
 /*
 [a]0000+0+
 */
int main(){
    
    int t;
    cin >> t;
    while(t--){
        int n;
        cin >> n;
        string s;
        cin >> s;
        int sw = 1;
        for(int i = 1; i < s.size(); i++){
            if(s[i] < s[i-1])sw = 0;
        }
        if(sw){   // Then the string is 000000111111 Or pure 1, Or pure 0
            cout << s << '\n';
            continue;
        }
        string ans;
        for(int i = 0; i < s.size(); i++){
            if(s[i] == '1')break;
          
            ans.push_back('0');// Prefix 0
        }
        ans.push_back('0');// The middle section is not pure , As the above has been found 1, Then the middle must be treated as 1 individual 0.
        for(int i = s.size()-1; i >= 0; i--){
            if(s[i] == '0')break;
            ans.push_back('1'); // suffix 1
        }
        cout << ans << '\n';
    }
}

My code

I am a pure simulation , Do it in reverse order , If you find it later 0, that 0 Ahead 1 Can be eliminated .

#include "bits/stdc++.h"
using namespace  std;
const int maxn=2e5+10;
char ss[maxn],ans[maxn];
int main()
{
    int cas,n;
    scanf("%d",&cas);
    while (cas--)
    {
        scanf("%d",&n);
        scanf("%s",ss+1);

        int pp=0;
        ans[pp]='1';
        for(int i=n;i>=1;--i)
        {
            if(ss[i]=='0')
            {
                int k=i;
                while (k>0&&ss[k-1]=='0')--k;
                int u=k;
                while (u>0&&ss[u-1]=='1')--u;
                if(u!=k){i=u;
                    if(ans[pp]=='1')ans[++pp]='0';
                }
                else ans[++pp]='0';
            }
            else if(ss[i]=='1'&&ans[pp]=='0')
            {
                while (i>0&&ss[i-1]=='1')--i;
            }
            else ans[++pp]='1';
        ans[pp+1]='\0';
        }
        for(int i=pp;i>=1;--i)printf("%c",ans[i]);
        printf("\n");
    }
    return 0;
}

C topic

The question ：

Yes n A digital ,k personal ,$a_i$ Indicates the size of the number ,$k_i$ It means the first one i The number of figures to be received by individuals , Ask in the case of optimal allocation , What is the sum of the maximum and minimum values each person receives ？

Ideas ：

If this person only asks for a gift , Must give him the biggest number . Now , The maximum number in the following is the sub maximum number excluding this .

Because the maximum number and the minimum number must appear in sum in , Then give it to $k_i$ The biggest one , And then put the smallest number remaining , All into this man , And so on and so on , Just ok 了 .

#include "bits/stdc++.h"
using namespace  std;
const int maxn=2e5+10;
typedef  long long ll ;
ll want[maxn],gift[maxn];
bool cmp1(ll &a,ll &b)
{
    return a>b;
}
int main()
{
  // freopen("E:\\project folds\\Clion\\hello\\cmake-build-debug\\in.text","r",stdin);

    int cas,n;
    scanf("%d",&cas);
    while (cas--)
    {
        int n,m;
        ll ans=0;
        scanf("%d %d",&n,&m);
        for(int i=1;i<=n;++i)scanf("%lld",&gift[i]);
        for(int i=1;i<=m;++i)scanf("%lld",&want[i]);
        sort(gift+1,gift+n+1,cmp1);
        sort(want+1,want+m+1);

        int i=1;
        while (i<=m&&want[i]==1){ans+=gift[i]*2;++i;}
        if(i==(m+1))
        {printf("%lld\n",ans);
            continue;}

        int last=n;// Record the smallest gift
        sort(want+i,want+m+1,cmp1);// Arrange your friends according to the number of gifts you want 

        for(;i<=m;++i)
        {
            ans+=gift[i];
            ans+=gift[last];
            want[i]-=1;
            while (want[i]>0){--last;--want[i];}
        }
        printf("%lld\n",ans);
    }
    return 0;
}