Codeforces Round #764 (Div. 3)

Codeforces Round #764 (Div. 3)

A   Plus One on the Subset

题意：

给定一个数组，我们可以进行的 *** 作为，选出任意的下标，然后将这些数组下标对应的元素进行+1，求最后使得数组元素都相等的最小 *** 作数是多少。

思路：

我们只需要更新一个最大值，一个最小值，然后答案即为MAX-MIN，输出即可。

#include
using namespace std;
#define ll long long 
#define pb push_back
const int N=2e5+5;
const int mod=1e9+7;
int n;
void solve(){
    cin>>n;
    int Ma=0,Mi=mod;
    for(int i=1;i<=n;i++){
        int a;
        cin>>a;
        if(a>Ma)Ma=a;
        if(a>t;
    while(t--){
        solve();
    }
}

B. Make AP

题意：

给定三个数，a,b,c然后我们可以选择其中一个数乘以m，问是否能够使之成为等差数列。

思路：

我们只需要对每一个数进行考虑即可， 考虑等差数列的公式，可以在已知两个元素的情况下，得到另一个元素的值，然后看当前值是否为计算出的值之间是否满足倍数关系即gcd（x,k）==k，满足即表示YES

注意要判断，通过两个值求出另一个值的时候，这个值要>0

#include
using namespace std;
#define ll long long 
#define pb push_back
const int N=2e5+5;
const int mod=1e9+7;
int n;
void solve(){
    int a,b,c;
    cin>>a>>b>>c; 
    int fg=0;
	if(2*b-c>0&&__gcd(2*b-c,a)==a)fg=1;
   	if(2*b-a>0&&__gcd(2*b-a,c)==c)fg=1;
   	if(__gcd(a+c,2*b)==2*b)fg=1;
    if(fg)cout<<"YESn";
    else cout<<"Non";
    
	return ;
}
int main(){
    int t=1;
    cin>>t;
    while(t--){
        solve();
    }
}

C. Division by Two and Permutation

题意：

给定一个数组，我们可以对任意的数进行 *** 作， *** 作为：将其除以2向下取整，然后代替这个数。

问是否能通过上述的 *** 作，使数组成为1-n的一个排列。

思路：

我们只需要当输入的值大于n就/2,cnt数组保存每一个值是否出现，那么判断的情况就是，当其大于n或者cnt[a]已经存在的情况下一直/2，直至a==0然后break，即可。退出循环的时候cnt[a]++，那么最后判断cnt[0]是否存在即可，若存在，则NO否则YES。

感觉要比B简单

#include
using namespace std;
#define ll long long 
#define pb push_back
const int N=2e5+5;
const int mod=1e9+7;
int n;
int cnt[55];
void solve(){
	scanf("%d",&n);
   	memset(cnt,0,sizeof(cnt));
    for(int i=1;i<=n;i++){
        int a;
        scanf("%d",&a);
        while(a>n||cnt[a]){
            a/=2;
            if(a==0)break;        //特别注意break的情况
        }cnt[a]++;
    }if(cnt[0])printf("Non");
    else printf("YESn"); 
    return ;
}
int main(){
    int t=1;
    scanf("%d",&t);
    while(t--){
        solve();
    }return 0;
}

D. Palindromes Coloring

题意：

有k种颜料，然后给定一个字符串，我们对其字符进行染色，不需要每个字符都染上颜色，但k中颜料必须都要用到，染完色之后，将其不同的颜色分开，形成不同的子字符串，对于每个子字符串，可以进行的 *** 作是，其中的任意两个字符之间都可以交换位置，然后满足的条件是这些子字符串都必须是回文串，那么求出最短的回文串能达到的最长的长度。

思路：

看到最大化最小值，考虑二分答案，然后对于每个二分出来的值进行check，

通过对题意的分析，我们可以统计出每个字母出现的次数，然后进行分类，cnt2统计出现两个的字母，cnt1统计出现一个的字母。

当长度p为偶数的子串的时候，cnt2>=p/2*k

当长度为p的奇数的子串的时候，cnt2>=p/2*k&&cnt1+(cnt2-p/2*k)*2>=k

然后二分check即可

#include
using namespace std;
#define ll long long 
#define pb push_back
const int N=2e5+5;
const int mod=1e9+7;
ll n,k;
string s;
int cnt[26];
ll cnt2,cnt1;
int check(int x){        //注意p*k可能会爆int，
    if(x&1){
        int p=x/2;
        if(cnt2>=p*k&&cnt1+(cnt2-p*k)*2>=k)return 1;
        else return 0;
    }else{
        int p=x/2;
        if(cnt2>=p*k)return 1;
        else return 0;
    }
}
void solve(){
    cin>>n>>k;
    cin>>s;
    cnt1=0,cnt2=0;
    memset(cnt,0,sizeof(cnt));
    for(int i=0;it;
    while(t--){
        solve();
    }
}

E. Masha-forgetful

题意：

有n个电话号码，然后还有一个目标的电话号码，我们需要记住目标的电话号码，我们需要在已知的n个电话号码中找到和目标的电话号码相同的一个子段（该子段长度不小于2）。

回答出将目标分为几个子段，然后依次回答出在n个电话号码中符合这一字段的L，R，和电话号码的标号。

若不行，则输出-1

思路：

考虑到子段的长度不能小于2，那么贪心的考虑发现，只需要考虑长度为2,3的子段即可，

那么我们对于已知的n个字符串来说，我们将其长度为2，3的子串分别加入map中，

然后对于目标字符串，进行简单dp，判断是否为-1的情况。

那么对于dp的定义为：dp[i]表示前i-1个字符均能够符合题意。

那么转移方程为若i前一个位置合法，并且当前连续两个字符在map能找到，那么dp[i+1]=1;

若i前一个位置合法，并且当前连续三个字符在map能找到，那么dp[i+2]=1;

然后判断dp[m]，输出答案的时候，我们进行考虑逆向输出。

当前位置为pos，若dp[pos-2]为1，那么可以将pos-1,pos的map值加入vector中

否则，则表示dp[pos-3]一定为1，那么可以将pos-2,pos-1,pos的map值加入到vector中。

最后输出即可，细节处见代码。

#include
using namespace std;
#define ll long long 
#define pb push_back
const int N=3e3+5;
const int mod=1e9+7;
struct node{
	int l,r,pos;
};
map mp;
string substr(string s,int l,int r){
    string res="";
    for(int i=l;i<=r;i++)res+=s[i];
    return res;
}
int dp[N];
void solve(){
    int n,m;
    cin>>n>>m;
    memset(dp,0,sizeof(dp));
    mp.clear();
    for(int i=1;i<=n;i++){
        string s;
        cin>>s;
        s=" "+s;
        for(int j=1;j<=m;j++){
            if(j+1<=m)mp[substr(s,j,j+1)]={j,j+1,i};
            if(j+2<=m)mp[substr(s,j,j+2)]={j,j+2,i};
        }
    }string s;
    cin>>s;
    s=" "+s;
    dp[0]=1;
    for(int i=1;i<=m;i++){
        if(i+1<=m&&dp[i-1]&&mp.count(substr(s,i,i+1)))dp[i+1]=1;
        if(i+2<=m&&dp[i-1]&&mp.count(substr(s,i,i+2)))dp[i+2]=1;
    }if(!dp[m])cout<<"-1n";
    else{
        vector ans;
        int pos=m;
        while(pos>0){
            if(dp[pos-2]){
                ans.pb(mp[substr(s,pos-1,pos)]);
                pos-=2;
            }else{
                ans.pb(mp[substr(s,pos-2,pos)]);
                pos-=3;
            }
        }cout<=0;i--){
            cout<>t;
    while(t--){
        solve();
    }
}

F. Interacdive Problem

交互。

G. MinOr Tree

题意：

给定一个n个顶点，m条边的连通图，求所有生成树中其树的边权或的值最小的是多少。

思路：

发现边的权值在1e9以内，那么我们可以进行枚举每一位。

首先将所有边加入一个集合中。

对于当前枚举的这一位。

如果当前这一位为0的所有边能够构成一个生成树，那么将这些边加入这一位对应的vector集合里，并且修改当前集合为这一位所对应的集合；

如果不能构成，那么表示该位必须为1，即集合并不能减小，且答案要或上1<

判断是否构成生成树可用并查集。

#include
using namespace std;
#define ll long long 
#define pb push_back
const int N=2e5+5;
const int mod=1e9+7;
struct node{
	int u,v,w;
}; 
vector v[33];
int f[N];
int n,m,pos;
ll res;
int find(int x){
    if(x==f[x])return x;
    else return f[x]=find(f[x]);
}
int merge(int x,int y){
    int fx=find(x);
    int fy=find(y);
    if(fx!=fy){
        f[fx]=fy;
        return 1;
    }else return 0;
}
void judge(int x){
    int cnt=0;
    for(int i=1;i<=n;i++)f[i]=i;
    for(int i=0;i>x)&1)==0){
            if(merge(v[pos][i].u,v[pos][i].v))cnt++;
            v[x].pb(v[pos][i]);
        }
    }if(cnt==n-1)pos=x;
    else res=res|(1<>n>>m;
    for(int i=0;i<33;i++)v[i].clear();
    pos=32;
    res=0;
    for(int i=1;i<=m;i++){
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        v[32].pb(node{a,b,c});
    }
    for(int i=31;i>=0;i--){
        judge(i);
    }cout<>t;
    while(t--){
        solve();
    }
}