Educational Codeforces Round 96

2020-10-12

这里是关于Educational Codeforces Round 96的一些题解

A. Number of Apartments

题目大意

一共$t$组测试数据，对于每一组测试数据，给定$n$，求满足$3 \times x + 5 \times y + 7 \times z = n$的一组解，

数据范围

$1 \leq t \leq 10^3$，$1 \leq n \leq 10^3$

思路

数据范围小，直接暴力即可，当时直接没动脑子三个for循环枚举xyz，直接被hack；稍微多加几个判断条件可以

代码

void solve(){
    int n=read();
    for(int i=0;i*3<=n;i++)
        for(int j=0;i*3+j*5<=n;j++)
            for(int k=0;i*3+j*5+k*7<=n;k++)
                if(i*3+j*5+k*7==n){
                    cout<<i<<' '<<j<<' '<<k<<endl;
                    return ;
                }
    cout<<-1<<endl;
    return ;
}

B. Barrels

题目大意

一共$t$组测试数据，对于每一组测试数据，给定$n,k$，表示一共有$n$个数，以及最多操作$k$次，对于每一次操作，我们可以选取任意一个数，将其与另一个数相加，然后将其归零，所得之和替换另一个数；求完成$k$次操作之后$n$个数里面最大值和最小值之差最大为多少。

数据范围

$1 \leq t \leq 10^3$，$1 \leq k \le n \leq 2 \times 10^5$

思路

看完题目直接贪心就行，排个序直接从大往小加起来就行；对于$k$进行$+1$处理可以稍微简化一点

代码


vector<ll> v ;

void solve(){
    
    v.clear();
    ll n=read(),k=read()+1,sum=0;
    for(ll i=0;i<n;i++){
        v.push_back(read());
    }

    sort(v.rbegin(),v.rend());
    for(int i=0;i<n&&k;i++,k--){
        sum+=v[i];
    }
    cout<<sum<<endl;
    
    return ;
}

C. Numbers on Whiteboard

题目大意

一共$t$组测试数据，对于每一组测试数据，给定$n$，表示有$1,2,…,n-1,n$一共有$n$个数，，每次拿取两个数，进行相加除以二向上取整再放回，如此操作$n-1$次，最后剩下一个数，求该数最小值，并且给出操作步骤

数据范围

$1 \leq t \leq 10^3$，$2 \leq n \leq 2 \times 10^5$

思路

稍微纸笔思考一下可知是结论题，最小值一定是$2$，步骤一定是先将$n$与$n-2$相加，得到$n-1$，再将得到的$n-1$和原有的$n-1$合并为$n-1$，之后就发现可以一直重复最大数和最大数-2合并的操作，直到只剩下一个2；
特例$n==2$需要特殊考虑

代码

void solve(){
    ll n=read();
        cout<<2<<endl;
    if(n==2){
        cout<<1<<' '<<2<<endl;
        return ;
    }
    else {
        cout<<n<<' '<<n-2<<endl;
        cout<<n-1<<' '<<n-1<<endl;
        for(int i=n-1;i>=3;i--){
            cout<<i<<' '<<i-2<<endl;
        }
    }
    return ;
}

D. String Deletion

题目大意

给你一个仅由”0”以及”1”组合而成的字符串，你对其进行如下操作，该操作包括先后两个步骤：

1.在该字符串中随意删除一个字符
2.随后将该字符串中由相同字符组成的前缀删除

求字符串被清空时最大操作次数，注意每次操作是包含上面两个步骤的

思路

首先可以想到，对于任意的由相同字符组成的前缀，都可以用于拆分成两个部分——第一个字符和后面的字符——用于完成一次操作的两个步骤，那么问题就被简化；对于每一个操作一，我们应该从连续相同字符组成的串长度大于1的串删除，而删除的顺序则是当前能进行如此操作的最左边的串

代码

void solve(){
    ll len=read(),an=0,it = 0 ;
    vector<int>v;
    string s;
    cin>>s;
    s+="2";
    for(int i=0,j=i;i<len+1;i++)
        if(s[i]==s[j])continue;
        else {
            v.push_back(i-j);
            j=i;
        }
    for(int i=0;i<v.size();i++){
        if(it<i)it=i;
        while(it<v.size()&&v[it]==1)it++;
        an++;
        if(it==v.size()){
            an+=(v.size()-i-1)/2;
            break;
        }
        else v[it]--;
    }
    cout<<an<<endl;
    return ;
}

从现在开始，这里叫做隶辰寿广场

E. String Reversal

题目大意

对于给定的字符串$s$，仅能将相邻位置的字符进行位置交换，得到其反转字符串$t$，求所要的操作次数最小值。

思路

首先无论怎么交换，最优方案一定是原字符串$s$中第一个$a$，对应到翻转串$t$中还是第一个$a$，原字符串$s$中第二个$a$，对应到翻转串$t$中还是第二个$a$……这样才能保证操作次数最少，因为相同字母交换之后没有意义，除了使得操作数增加。

其次我们再来看对应的字符串规律，假设我们有字符串$s=”abcab”$，则翻转串$t=”bacba”$，使用我们上面提到的交换最优方案，做出一个表$pos=[2,1,3,5,4]$表示原来第一个字符要去第二个位置，第二个字符去第一个位置……这样就发现是一个类似于求逆序对的题目了