Codeforces Round #760 (Div. 3)A B C D E F

作者实力有限：赛后补题持续更新中

A. Polycarp and Sums of Subsequences(思维)

思路： 最小的两个一定在第$1$第$2$位，那么第$3$个数直接最后一个数减去第$1$第$2$位即可得。

• 参考代码：

#include<bits/stdc++.h>
using namespace std;
#define snow ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define re register int
#define int long long 
#define fer(i,a,b) for(re i = a ; i <= b ; i ++)
#define der(i,a,b) for(re i = a ; i >= b ; i --)
#define lowbit(x) (x&-x)
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int lcm(int a,int b){return a*b/gcd(a,b);}
typedef pair<int,int>PII;
typedef pair<int,string>PIS;
const int N=10;
int s[N];
signed main(){
    int t;
    cin>>t;
    while(t--){
        for(int i=1;i<=7;i++)cin>>s[i];
        int a=s[1];
        int b=s[2];
        int c=s[7]-s[1]-s[2];
        cout<<a<<' '<<b<<' '<<c<<endl;
    }
    return 0;
}

B. Missing Bigram(构造+模拟)

思路： 根据题目给定的$n-1$个字符串进行构造，构造出一个满足条件的字符串，如果长度与失踪的字符串不等，那么我们再在其屁股后面添加一个字符，默认构造一个失踪的单词。

• 参考代码：

#include<bits/stdc++.h>
using namespace std;
#define snow ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define re register int
#define int long long 
#define fer(i,a,b) for(re i = a ; i <= b ; i ++)
#define der(i,a,b) for(re i = a ; i >= b ; i --)
#define lowbit(x) (x&-x)
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int lcm(int a,int b){return a*b/gcd(a,b);}
typedef pair<int,int>PII;
typedef pair<int,string>PIS;
const int N=10;
int a[N];
string s[110];
signed main(){
    int t;
    cin>>t;
    while(t--){
        int n;
        cin>>n;
        for(int i=0;i<n-2;i++)cin>>s[i];
        string ss;
        ss+=s[0];
        for(int i=1;i<n-2;i++){
            if(s[i][0]==s[i-1][1])ss+=s[i][1];
            else ss+=s[i];
        }
        if(ss.size()!=n){
            ss+='a';
        }
        cout<<ss<<endl;
    }
    return 0;
}

C. Paint the Array(思维+GCD)

思路： 因为题目要求相邻两位颜色不相同，所以限定了数组的颜色排列只能为两种。那么我们只需要$GCD$两遍，判断奇数位$GCD$出来的$d$会不会被偶数位整除或者判断偶数位$GCD$出来的$d$会不会被奇数位整除。如果两者任意满足任意一位都不会整除$d$那么输出$GCD$即$d$，否则输出$0$

• 参考代码：

#include<bits/stdc++.h>
using namespace std;
#define snow ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define re register int
#define int long long 
#define fer(i,a,b) for(re i = a ; i <= b ; i ++)
#define der(i,a,b) for(re i = a ; i >= b ; i --)
#define lowbit(x) (x&-x)
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int lcm(int a,int b){return a*b/gcd(a,b);}
typedef pair<int,int>PII;
typedef pair<int,string>PIS;
const int N=110;
int a[N];
signed main(){
    int t;
    cin>>t;
    while(t--){
        int n;
        cin>>n;
        cin>>a[1];
        cin>>a[2];
        int gcd1=a[1];
        int gcd2=a[2];
        for(int i=3;i<=n;i++)//预处理GCD
        {
            cin>>a[i];
            if(i%2)gcd1=gcd(gcd1,a[i]);
            else gcd2=gcd(gcd2,a[i]);
        }
        bool success=true;
        for(int i=1;i<=n;i+=2){
            if(a[i]%gcd2==0)success=false;
        }
        if(success){
            cout<<gcd2<<endl;
            continue;
        }
        success=true;
        for(int i=2;i<=n;i+=2){
            if(a[i]%gcd1==0)success=false;
        }
        if(success){
            cout<<gcd1<<endl;
            continue;
        }
        cout<<0<<endl;
    }
    return 0;
}

D. Array and Operations(贪心)

思路： 题目要求最多进行$k$次操作，也就是最多能操作2k个数。因为题目要求获得的分数尽可能的少。所以我们贪心是往小的方面贪。将原数组$sort$一遍。尽可能使得留下的数最小从而得分最少，所以我们选择后2k个数进行操作。一开始我的想法是直接让后2k个数前后匹配，但马上发现最靠近中间的数存在相等的可能性从而可能会比最优解多提供$1$的贡献值，那么我们只要选择$n-2*k+1$~$n-k$的区间即可，每次让$sum+=a[i]/a[(i+k)]$即可，最后再加上前面剩余的没操作的数即是最优解。贪心的严谨证明太难了，意思意思就行。

• 参考代码：

#include<bits/stdc++.h>
using namespace std;
#define snow ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define re register int
#define int long long 
#define fer(i,a,b) for(re i = a ; i <= b ; i ++)
#define der(i,a,b) for(re i = a ; i >= b ; i --)
#define lowbit(x) (x&-x)
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int lcm(int a,int b){return a*b/gcd(a,b);}
typedef pair<int,int>PII;
typedef pair<int,string>PIS;
const int N=2e5+10;
int a[N];
signed main(){
    int t;
    cin>>t;
    while(t--){
        int n,k;
        cin>>n>>k;
        for(int i=1;i<=n;i++)cin>>a[i];
        sort(a+1,a+n+1);
        int g=k*2;
        int sum=0;
        for(int i=n-g+1;i<=n-g+k;i++){
            int aa=a[i];
            int bb=a[i+k];
            sum+=aa/bb;
        }
        for(int i=1;i<=n-g;i++)sum+=a[i];
        cout<<sum<<endl;
    }
    return 0;
}

E. Singers’ Tour(推公式)

前言 这道题没处理好$NO$的判定，$wa$了$5$发真的贼难受，好在最后还是过了。但也是高罚时+慢手速使得$Rank$最后只有$800$+是真的很可惜。

思路: 本题是一道推公式，其实公式的话不是很难推，对于我来说还是有些小坑需要注意。首先：我们从第一个样例出发，第$1$个城市的时间是由a+3b+2c贡献的，第$2$个城市的时间是由2a+b+3c贡献的，第$3$个城市的时间是由3a+2b+c贡献的。那么我们容易得出第$1$条公式：$6a+6b+6c=s[1]+s[2]+s[3]->a+b+c=(s[1]+s[2]+s[3])/6$，第一个$NO$的判断点在这，如果$(s[1]+s[2]+s[3])$mod $6 !=0$那么直接输出$NO$即可。然后我们只要依次推出第$1$个城市~第$n$个城市的初始时长即可。那么则么推呢$?$第一个城市的初始值：$s[n]-s[1]=2=2a-b-c=>a+b+c+2=3a=>7+2=3a=>a=3。$同样的第二个城市的初始值：$s[1]-s[2]=3b=7+(-4)=>b=1$ ...... 那么我们可以由小到大就很容易发现本题的公式始终是固定的。当然第二个NO的坑点在哪呢$?$在于我们求出来的每个城市的初始时间能不能小于等于$0$，如果小于等于$0$说明同样也是不存在的。还需要注意的一个NO点在求每个城市的初始时间同样不能为小数，所以也得判断一下。

• 参考代码：

#include<bits/stdc++.h>
using namespace std;
#define snow ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define re register int
#define int long long 
#define fer(i,a,b) for(re i = a ; i <= b ; i ++)
#define der(i,a,b) for(re i = a ; i >= b ; i --)
#define lowbit(x) (x&-x)
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int lcm(int a,int b){return a*b/gcd(a,b);}
typedef pair<int,int>PII;
typedef pair<int,string>PIS;
const int N=2e5+10;
int a[N];
signed main(){
    int t;
    cin>>t;
    while(t--){
        int n;
        cin>>n;
        int sum=0;
        for(int i=1;i<=n;i++){cin>>a[i];sum+=a[i];}
        int sum2=(1+n)*n/2;
        if(sum%sum2){
            cout<<"NO"<<endl;
            continue;
        }
        sum=sum/sum2;
        int xx=(a[n]-a[1]+sum);
        if(xx<=0||xx%n){//判断小数以及0和负数的情况
            cout<<"NO"<<endl;
            continue;
        }
        for(int i=2;i<=n;i++){
            xx=(a[i-1]-a[i]+sum);
            if(xx<=0||xx%n){
                cout<<"NO"<<endl;
                goto GG;}
        }
        cout<<"YES"<<endl;//如果都满足那么可以输出答案了
        xx=(a[n]-a[1]+sum)/n;
        cout<<xx<<' ';
        for(int i=2;i<=n;i++){
            xx=(a[i-1]-a[i]+sum)/n;
            cout<<xx<<' ';
        }
        cout<<endl;
        GG:;
    }
    return 0;
}

F. Reverse(字符串+DFS记忆化搜索)

思路: 将数字转为为二进制形式，通过几个操作很容易就发现，无论在这个数二进制形式下末尾新加$0$还是$1$，翻转之后全部只能变成首末位皆为$1$的数字。那么如果目标数的二进制形式的末尾不是$1$，那么$X$永远无法转变成$Y$，除非$X=Y$，那么我们通过一个$set$进行存储每次新出现的string(我们用string存储二进制)，如果之前出现过了可以直接剪枝，避免了不断的翻转导致的$MLE$，因为本题的一些限制，所以假定我们限制$string$的最长长度为$70$那么出现的不重复的string不会超过$280$，因为我们改变的是首尾也就是$0$和$1$不一样。最后再判断容器$set$中是否出现过$Y$即可。

• 参考代码：

#include<bits/stdc++.h>
using namespace std;
#define snow ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define re register int
#define int long long 
#define fer(i,a,b) for(re i = a ; i <= b ; i ++)
#define der(i,a,b) for(re i = a ; i >= b ; i --)
#define lowbit(x) (x&-x)
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int lcm(int a,int b){return a*b/gcd(a,b);}
typedef pair<int,int>PII;
typedef pair<int,string>PIS;
string get(int x){//将数转化为二进制形式
    string s;
    while(x){
        if(x&1)s+='1';
        else s+='0';
        x/=2;
    }
    reverse(s.begin(),s.end());
    return s;
}
string go(string x){//翻转去前导0
    while(x.back()=='0')x.pop_back();
    reverse(x.begin(),x.end());
    return x;
}
signed main(){
    set<string>S;
    int a,b;
    cin>>a>>b;
    queue<string>q;
    q.push(get(a));
    S.insert(get(a));
    while(q.size()){
        string k=q.front();
        q.pop();
        if(k.size()>70)continue;
        string s2,s3;
        s2=go(k+'0');
        s3=go(k+'1');
        if(!S.count(s2)){
            S.insert(s2);
            q.push(s2);
        }
        if(!S.count(s3)){
            S.insert(s3);
            q.push(s3);
        }
    }
    if(S.count(get(b)))cout<<"YES"<<endl;
    else cout<<"NO"<<endl;
    return 0;
}

Rank 876 历史新高，记录一下。