Codeforces Round #760 (Div. 3) A B C D E F (持续加载中)

Codeforces Round #760 (Div. 3)A B C D E F
作者实力有限：赛后补题持续更新中
A. Polycarp and Sums of Subsequences(思维)
思路：最小的两个一定在第 1 1 1第 2 2 2位，那么第 3 3 3个数直接最后一个数减去第 1 1 1第 2 2 2位即可得。
参考代码：
#include
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 pairPII;
typedef pairPIS;
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< 
B. Missing Bigram(构造+模拟) 
 
 思路： 根据题目给定的
     
      
       
        
         n
        
        
         −
        
        
         1
        
       
       
        n-1
       
      
     n−1个字符串进行构造，构造出一个满足条件的字符串，如果长度与失踪的字符串不等，那么我们再在其屁股后面添加一个字符，默认构造一个失踪的单词。 
 
参考代码： 
#include
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 pairPII;
typedef pairPIS;
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>s[i];
        string ss;
        ss+=s[0];
        for(int i=1;i 
C. Paint the Array(思维+GCD) 
 
 思路： 因为题目要求相邻两位颜色不相同，所以限定了数组的颜色排列只能为两种。那么我们只需要
     
      
       
        
         G
        
        
         C
        
        
         D
        
       
       
        GCD
       
      
     GCD两遍，判断奇数位
     
      
       
        
         G
        
        
         C
        
        
         D
        
       
       
        GCD
       
      
     GCD出来的
     
      
       
        
         d
        
       
       
        d
       
      
     d会不会被偶数位整除或者判断偶数位
     
      
       
        
         G
        
        
         C
        
        
         D
        
       
       
        GCD
       
      
     GCD出来的
     
      
       
        
         d
        
       
       
        d
       
      
     d会不会被奇数位整除。如果两者任意满足任意一位都不会整除
     
      
       
        
         d
        
       
       
        d
       
      
     d那么输出
     
      
       
        
         G
        
        
         C
        
        
         D
        
       
       
        GCD
       
      
     GCD即
     
      
       
        
         d
        
       
       
        d
       
      
     d，否则输出
     
      
       
        
         0
        
       
       
        0
       
      
     0 
 
参考代码： 
#include
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 pairPII;
typedef pairPIS;
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< 
D. Array and Operations(贪心) 
 
 思路： 题目要求最多进行
     
      
       
        
         k
        
       
       
        k
       
      
     k次操作，也就是最多能操作2k个数。因为题目要求获得的分数尽可能的少。所以我们贪心是往小的方面贪。将原数组
     
      
       
        
         s
        
        
         o
        
        
         r
        
        
         t
        
       
       
        sort
       
      
     sort一遍。尽可能使得留下的数最小从而得分最少，所以我们选择后2k个数进行操作。一开始我的想法是直接让后2k个数前后匹配，但马上发现最靠近中间的数存在相等的可能性从而可能会比最优解多提供
     
      
       
        
         1
        
       
       
        1
       
      
     1的贡献值，那么我们只要选择
     
      
       
        
         n
        
        
         −
        
        
         2
        
        
         ∗
        
        
         k
        
        
         +
        
        
         1
        
       
       
        n-2*k+1
       
      
     n−2∗k+1~
     
      
       
        
         n
        
        
         −
        
        
         k
        
       
       
        n-k
       
      
     n−k的区间即可，每次让
     
      
       
        
         s
        
        
         u
        
        
         m
        
        
         +
        
        
         =
        
        
         a
        
        
         [
        
        
         i
        
        
         ]
        
        
         /
        
        
         a
        
        
         [
        
        
         (
        
        
         i
        
        
         +
        
        
         k
        
        
         )
        
        
         ]
        
       
       
        sum+=a[i]/a[(i+k)]
       
      
     sum+=a[i]/a[(i+k)]即可，最后再加上前面剩余的没操作的数即是最优解。贪心的严谨证明太难了，意思意思就行。 
 
参考代码： 
#include
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 pairPII;
typedef pairPIS;
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< 
E. Singers’ Tour(推公式) 
 
 前言 这道题没处理好
     
      
       
        
         N
        
        
         O
        
       
       
        NO
       
      
     NO的判定，
     
      
       
        
         w
        
        
         a
        
       
       
        wa
       
      
     wa了
     
      
       
        
         5
        
       
       
        5
       
      
     5发真的贼难受，好在最后还是过了。但也是高罚时+慢手速使得
     
      
       
        
         R
        
        
         a
        
        
         n
        
        
         k
        
       
       
        Rank
       
      
     Rank最后只有
     
      
       
        
         800
        
       
       
        800
       
      
     800+是真的很可惜。 
 
 
 思路: 本题是一道推公式，其实公式的话不是很难推，对于我来说还是有些小坑需要注意。首先：我们从第一个样例出发，第
     
      
       
        
         1
        
       
       
        1
       
      
     1个城市的时间是由a+3b+2c贡献的，第
     
      
       
        
         2
        
       
       
        2
       
      
     2个城市的时间是由2a+b+3c贡献的，第
     
      
       
        
         3
        
       
       
        3
       
      
     3个城市的时间是由3a+2b+c贡献的。那么我们容易得出第
     
      
       
        
         1
        
       
       
        1
       
      
     1条公式：
     
      
       
        
         6
        
        
         a
        
        
         +
        
        
         6
        
        
         b
        
        
         +
        
        
         6
        
        
         c
        
        
         =
        
        
         s
        
        
         [
        
        
         1
        
        
         ]
        
        
         +
        
        
         s
        
        
         [
        
        
         2
        
        
         ]
        
        
         +
        
        
         s
        
        
         [
        
        
         3
        
        
         ]
        
        
         −
        
        
         >
        
        
         a
        
        
         +
        
        
         b
        
        
         +
        
        
         c
        
        
         =
        
        
         (
        
        
         s
        
        
         [
        
        
         1
        
        
         ]
        
        
         +
        
        
         s
        
        
         [
        
        
         2
        
        
         ]
        
        
         +
        
        
         s
        
        
         [
        
        
         3
        
        
         ]
        
        
         )
        
        
         /
        
        
         6
        
       
       
        6a+6b+6c=s[1]+s[2]+s[3]->a+b+c=(s[1]+s[2]+s[3])/6
       
      
     6a+6b+6c=s[1]+s[2]+s[3]−>a+b+c=(s[1]+s[2]+s[3])/6，第一个
     
      
       
        
         N
        
        
         O
        
       
       
        NO
       
      
     NO的判断点在这，如果
     
      
       
        
         (
        
        
         s
        
        
         [
        
        
         1
        
        
         ]
        
        
         +
        
        
         s
        
        
         [
        
        
         2
        
        
         ]
        
        
         +
        
        
         s
        
        
         [
        
        
         3
        
        
         ]
        
        
         )
        
       
       
        (s[1]+s[2]+s[3])
       
      
     (s[1]+s[2]+s[3])mod 
     
      
       
        
         6
        
        
         !
        
        
         =
        
        
         0
        
       
       
        6 !=0
       
      
     6!=0那么直接输出
     
      
       
        
         N
        
        
         O
        
       
       
        NO
       
      
     NO即可。然后我们只要依次推出第
     
      
       
        
         1
        
       
       
        1
       
      
     1个城市~第
     
      
       
        
         n
        
       
       
        n
       
      
     n个城市的初始时长即可。那么则么推呢
     
      
       
        
         ?
        
       
       
        ?
       
      
     ?第一个城市的初始值：
     
      
       
        
         s
        
        
         [
        
        
         n
        
        
         ]
        
        
         −
        
        
         s
        
        
         [
        
        
         1
        
        
         ]
        
        
         =
        
        
         2
        
        
         =
        
        
         2
        
        
         a
        
        
         −
        
        
         b
        
        
         −
        
        
         c
        
        
         =
        
        
         >
        
        
         a
        
        
         +
        
        
         b
        
        
         +
        
        
         c
        
        
         +
        
        
         2
        
        
         =
        
        
         3
        
        
         a
        
        
         =
        
        
         >
        
        
         7
        
        
         +
        
        
         2
        
        
         =
        
        
         3
        
        
         a
        
        
         =
        
        
         >
        
        
         a
        
        
         =
        
        
         3
        
        
         。
        
       
       
        s[n]-s[1]=2=2a-b-c=>a+b+c+2=3a=>7+2=3a=>a=3。
       
      
     s[n]−s[1]=2=2a−b−c=>a+b+c+2=3a=>7+2=3a=>a=3。同样的第二个城市的初始值：
     
      
       
        
         s
        
        
         [
        
        
         1
        
        
         ]
        
        
         −
        
        
         s
        
        
         [
        
        
         2
        
        
         ]
        
        
         =
        
        
         3
        
        
         b
        
        
         =
        
        
         7
        
        
         +
        
        
         (
        
        
         −
        
        
         4
        
        
         )
        
        
         =
        
        
         >
        
        
         b
        
        
         =
        
        
         1
        
       
       
        s[1]-s[2]=3b=7+(-4)=>b=1
       
      
     s[1]−s[2]=3b=7+(−4)=>b=1 … 那么我们可以由小到大就很容易发现本题的公式始终是固定的。当然第二个NO的坑点在哪呢
     
      
       
        
         ?
        
       
       
        ?
       
      
     ?在于我们求出来的每个城市的初始时间能不能小于等于
     
      
       
        
         0
        
       
       
        0
       
      
     0，如果小于等于
     
      
       
        
         0
        
       
       
        0
       
      
     0说明同样也是不存在的。还需要注意的一个NO点在求每个城市的初始时间同样不能为小数，所以也得判断一下。 
 
参考代码： 
#include
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 pairPII;
typedef pairPIS;
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"< 
F. Reverse(字符串+DFS记忆化搜索) 
 
 思路: 将数字转为为二进制形式，通过几个操作很容易就发现，无论在这个数二进制形式下末尾新加
     
      
       
        
         0
        
       
       
        0
       
      
     0还是
     
      
       
        
         1
        
       
       
        1
       
      
     1，翻转之后全部只能变成首末位皆为
     
      
       
        
         1
        
       
       
        1
       
      
     1的数字。那么如果目标数的二进制形式的末尾不是
     
      
       
        
         1
        
       
       
        1
       
      
     1，那么
     
      
       
        
         X
        
       
       
        X
       
      
     X永远无法转变成
     
      
       
        
         Y
        
       
       
        Y
       
      
     Y，除非
     
      
       
        
         X
        
        
         =
        
        
         Y
        
       
       
        X=Y
       
      
     X=Y，那么我们通过一个
     
      
       
        
         s
        
        
         e
        
        
         t
        
       
       
        set
       
      
     set进行存储每次新出现的string(我们用string存储二进制)，如果之前出现过了可以直接剪枝，避免了不断的翻转导致的
     
      
       
        
         M
        
        
         L
        
        
         E
        
       
       
        MLE
       
      
     MLE，因为本题的一些限制，所以假定我们限制
     
      
       
        
         s
        
        
         t
        
        
         r
        
        
         i
        
        
         n
        
        
         g
        
       
       
        string
       
      
     string的最长长度为
     
      
       
        
         70
        
       
       
        70
       
      
     70那么出现的不重复的string不会超过
     
      
       
        
         280
        
       
       
        280
       
      
     280，因为我们改变的是首尾也就是
     
      
       
        
         0
        
       
       
        0
       
      
     0和
     
      
       
        
         1
        
       
       
        1
       
      
     1不一样。最后再判断容器
     
      
       
        
         s
        
        
         e
        
        
         t
        
       
       
        set
       
      
     set中是否出现过
     
      
       
        
         Y
        
       
       
        Y
       
      
     Y即可。 
 
参考代码： 
#include
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 pairPII;
typedef pairPIS;
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(){
    setS;
    int a,b;
    cin>>a>>b;
    queueq;
    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"< 
Rank 876 历史新高，记录一下。
Codeforces Round #760 (Div. 3) A B C D E F (持续加载中)

C/C++/C#相关栏目本月热门文章
