Codeforces Round #764 (Div. 3) A B C D E G

A. Plus One on the Subset(思维)

题意： 每一次操作可以选任意数使其$val$++，那么我们直接找到最小的数和最大的数，最多的操作次数就是最大值减去最小值。

• 参考代码：

#include<bits/stdc++.h>
using namespace std;
#define mp make_pair
#define int long long 
#define re register int
#define pb emplace_back
#define lowbit(x) (x&-x)
#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 snow ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
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;
signed main(){
    int t;
    cin>>t;
    while(t--){
        int n;
        cin>>n;
        int MA=INT_MIN;
        int MI=INT_MAX;
        for(int i=1;i<=n;i++){
            int x;
            cin>>x;
            MI=min(MI,x);
            MA=max(MA,x);
        }
        cout<<MA-MI<<endl;
    }
    return 0;
}

B. Make AP(思维)

题意： 能否使三个数中任意一个数乘上一个正整数使得其三形成等差数列。我们只需要初始化一个$bool$值$ok$为$False$如果，三个中任意一个满足乘上一个正整数使得数列变成等差数列，那么更新$ok$为$True$。

• 参考代码：

#include<bits/stdc++.h>
using namespace std;
#define mp make_pair
#define int long long 
#define re register int
#define pb emplace_back
#define lowbit(x) (x&-x)
#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 snow ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
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;
signed main(){
    int t;
    cin>>t;
    while(t--){
        bool ok=false;
        int a,b,c;
        cin>>a>>b>>c;
        int cnt=c-b;//等差值
        int x=b-cnt;//x是a的目标值
        if(x>=a&&x%a==0)ok=true;//要求是正整数所以必须x>=a
        cnt=c-a;
        if(cnt%2==0){//差值如果是奇数那么中间数不用判断，因为中间数不可能为小数
            cnt/=2;
            x=a+cnt;
            if(x>=b&&x%b==0)ok=true;
        }
        cnt=b-a;
        x=b+cnt;//x是c的目标值
        if(x>=c&&x%c==0)ok=true;
        if(ok)cout<<"YES"<<endl;
        else cout<<"NO"<<endl;
    }
    return 0;
}

C. Division by Two and Permutation(贪心)

思路：因为每个数都是可以转化成不断下取整2的任意一个数，容易发现：数越小，他能转化的状态越少，而同样在这个数的本身之中，越靠近其数本身的数越不容易被其他数转换得到，可以从所有数都可以转换成1推出，那么我们排序之后贪心即可，将一个数不断下取整2，一旦遇到第一个没在$1$ ~ $n$的全排列中出现的数，那么标记$ok$并且操作下一个数。最后判断一下是不是所有$1$ ~ $n$的数都$st==True$，用$ok$最后做判断。

• 参考代码：

#include<bits/stdc++.h>
using namespace std;
#define mp make_pair
#define int long long 
#define re register int
#define pb emplace_back
#define lowbit(x) (x&-x)
#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 snow ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
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=60;
int st[N];
int a[N];
signed main(){
    int t;
    cin>>t;
    while(t--){
        int n;
        cin>>n;
        for(int i=1;i<=n;i++){st[i]=0;cin>>a[i];}
        sort(a+1,a+n+1);
        bool ok=true;
        for(int i=1;i<=n;i++){
            while(a[i]){
                if(a[i]<=n&&st[a[i]]==0){//如果没有标记过，且在全排列之中
                    st[a[i]]=1;
                    break;
                }
                a[i]/=2;//不断下取整2
            }
        }
        for(int i=1;i<=n;i++){
            if(st[i]==0)ok=false;
        }
        if(ok)cout<<"YES"<<endl;
        else cout<<"NO"<<endl;
    }
    return 0;
}

D. Palindromes Coloring(贪心+思维)

思路：因为我们要做到使得所有颜色至少有一个数要染，且目标值为每个颜色中染的数量中最少颜色最大。那么我们必须使得每个颜色染数尽可能趋向于相等，使得对答案的贡献最大。容易发现一个规律：任意偶数对永远可以构成回文，而每个偶数对(也有可能没有偶数对)最多只能携带1个奇数构成回文，我们只需要扫描统计一下偶数对和奇数对分别有多少，并且进行分配即可。

• 参考代码：

#include<bits/stdc++.h>
using namespace std;
#define mp make_pair
#define int long long 
#define re register int
#define pb emplace_back
#define lowbit(x) (x&-x)
#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 snow ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
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;
int sum[30];
signed main(){
    int t;
    cin>>t;
    while(t--){
        for(int i=0;i<26;i++){
            sum[i]=0;//将26个字母数量初始化
        }
        int n,m;
        cin>>n>>m;
        string s;
        cin>>s;
        for(int i=0;i<s.size();i++){
            int x=s[i]-'a';
            sum[x]++;//统计字母数量
        }
        int ou,ji;
        ou=ji=0;//偶数和奇数
        for(int i=0;i<26;i++){
            if(sum[i]%2==0&&sum[i]>0)ou+=sum[i]/2;//存奇数偶数对的数量
            else if(sum[i]>0){//这里需要注意，如果有偶数对溢出我们可以将其分配成2个奇数，贪心思想。
                ou+=sum[i]/2;
                ji+=sum[i]%2;
            }
        }
        int cnt=0;
        if(m<=ou){//如果偶数数量大于等于m种颜色，那么我们让每个颜色均匀分配的多，并且最好可以携带一个奇数
            cnt+=(ou/m)*2;
            int shengyu=ou%m;
            ji+=shengyu*2;
            cnt+=min((int)1,ji/m);
        }
        else{//否则如果偶数对小于m,那么奇数贡献为1，偶数贡献也无法均匀分配为2及以上那么答案最终是1
            cnt=1;
        }
        cout<<cnt<<endl;
    }
    return 0;
}

E. Masha-forgetful(string+模拟)

思路： 将所有字符串分割成多个长度为$2$和$3$的块，并用一个结构体存储每个块出现的$l、r、idx$，使用$op$数组的一维记录是长度为$2$还是$3$的块，二维记录其的表示值，因为长度最长为$3$所以大小不会超过$1000$。任意一个长度大于$2$的字符串都可以有多个$2、3$块组建，所以可行。存储完后操作最后一个$string$即可。

• 参考代码(偷师于cup-pyy)：

#include<bits/stdc++.h>
using namespace std;
#define mp make_pair
#define int long long 
#define re register int
#define pb emplace_back
#define lowbit(x) (x&-x)
#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 snow ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
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=1010;
int n,m;
char s[N];
struct Node{
  int l,r,idx;  
};
Node op[2][N];
int f[N];
int pre[N];
signed main(){
    int t;
    cin>>t;
    while(t--){
        memset(op,0,sizeof op);
        cin>>n>>m;
        for(int i=1;i<=n;i++){
            scanf("%s",s+1);
            for(int j=1;j<=m-1;j++){
                int x=(s[j]-'0')*10+s[j+1]-'0';
                op[0][x]={j,j+1,i};
            }
            for(int j=1;j<=m-2;j++){
                int x=(s[j]-'0')*100+(s[j+1]-'0')*10+s[j+2]-'0';
                op[1][x]={j,j+2,i};
            }
        }
        scanf("%s",s+1);
        for(int i=1;i<=m;i++)f[i]=0;
        f[0]=1;
        for(int i=2;i<=m;i++){
            int v1=(s[i-1]-'0')*10+s[i]-'0';
            if(f[i-2]&&op[0][v1].l){
                f[i]=1;pre[i]=2;
            }
            if(i>=3){
                int v2=(s[i-2]-'0')*100+(s[i-1]-'0')*10+s[i]-'0';
                if(f[i-3]&&op[1][v2].l){
                    f[i]=1;pre[i]=3;
                }
            }
        }
        if(f[m]){
            vector<Node>S;
            for(int i=m;i>0;i-=pre[i]){
                if(pre[i]==2){
                    int v=(s[i-1]-'0')*10+s[i]-'0';
                    S.push_back(op[0][v]);
                }
                else if(pre[i]==3){
                    int v=(s[i-2]-'0')*100+(s[i-1]-'0')*10+s[i]-'0';
                    S.push_back(op[1][v]);
                }
            }
            reverse(S.begin(),S.end());
            cout<<S.size()<<endl;
            for(auto x:S){
                cout<<x.l<<' '<<x.r<<' '<<x.idx<<endl;
            }
        }
        else cout<<"-1"<<endl;
    }
    return 0;
}

G. MinOr Tree(dsu+贪心)

思路： 图本身是一个连通加权无向图，我们需要通过删除$m-(n-1)$条边使其的目标值最小(OR )，那么因为所求的是最小边OR值，所以我们需要从高位出发，通过贪心的思想确定$1^9$范围$n-1$条边$OR$的最小值，那么我们只需要将$1^9$范围内的数在二进制形式下从高位出发逐一判断，是否必须此二进制位，如果没有此二进制位，是否能够形成连通图？如果必须此二进制位，那么我们将目标值$OR$上此二进制位。最后的目标值即是$n-1$条边构成的最小$OR$值

• 参考代码:

#include<bits/stdc++.h>
using namespace std;
#define mp make_pair
#define int long long 
#define re register int
#define pb emplace_back
#define lowbit(x) (x&-x)
#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 snow ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
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;
struct Edge{
    int a,b,w;
}edges[N];
int res;
int q[N];
int n,m;
int find(int x){
    if(x!=q[x])q[x]=find(q[x]);
    return q[x];
}
bool check(int x){
    for(int i=1;i<=n;i++)q[i]=i;
    for(int i=1;i<=m;i++){
        if(((res|edges[i].w)>>x)==(res>>x)){
            q[find(edges[i].a)]=find(edges[i].b);
        }
    }
    int cnt=0;
    for(int i=1;i<=n;i++){
        if(q[i]==i)cnt++;
    }
    return cnt>1;
}
signed main(){
    int t;
    cin>>t;
    while(t--){
        cin>>n>>m;
        for(int i=1;i<=m;i++){
            int a,b,w;
            cin>>a>>b>>w;
            edges[i]={a,b,w};
        }
        res=0;
        for(int i=30;i>=0;i--){
            if(check(i))res|=1<<i;
        }
        cout<<res<<endl;
    }
    return 0;
}