JZTXT

Codeforces Round 628 (Div. 2) A-D

发布时间 2023-04-14 22:39:13作者: EdGrass

Codeforces Round 628 (Div. 2)

A. EhAb AnD gCd

void solve(){
    int n=read();
    for(int i=1;i*i<=n;i++){
        int g=__gcd(i,n-i);
        if(g*g+i*(n-i)==n*g){
            cout<<i<<" "<<n-i<<endl;
            break;
        }
    }
    //puts(ans>0?"YES":"NO");
    //puts(ans>0?"Yes":"No");
}

 

B. CopyCopyCopyCopyCopy

void solve(){
    int n=read();
    vector<int>a;
    for(int i=0;i<n;i++){
        int x=read();
        a.push_back(x);
    }
    sort(a.begin(),a.end());
    a.erase(unique(a.begin(),a.end()),a.end());
    cout<<a.size()<<endl;
    //puts(ans>0?"YES":"NO");
    //puts(ans>0?"Yes":"No");
}

 

C. Ehab and Path-etic MEXs

先考虑特殊情况 若为一条链 则明显的 直接输出0—n-1

考虑普通情况： 先肯定0被选中的时候 MEX为1 其次01同时选中时MEX为2 且这两种情况必然发生

若0，1，2同时被选中 则MEX为3

若0，1，2不同时被选中 整棵树的最大MEX为2

所以0，1，2不被同时选中 选择一个有三条边的点放置0，1，2 

int ans[N];
vector<int>a[N];
void solve(){
    int n=read();
    for(int i=1;i<n;i++){
        int x=read(),y=read();
        a[x].push_back(i);
        a[y].push_back(i); 
    }
    int cnt=1;
    for(int i=1;i<=n;i++){
        if(a[i].size()>=3){
            for(int x:a[i]){
                ans[x]=cnt;
                cnt++;
            }
            break;
        }
    }
    for(int i=1;i<n;i++){
        if(ans[i])cout<<ans[i]-1<<'\n';
        else cout<<cnt-1<<'\n',cnt++;
    }
    //puts(ans>0?"YES":"NO");
    //puts(ans>0?"Yes":"No");
}

 

D. Ehab the Xorcist

首先考虑一些特殊情况：1.v==0，u==0 答案为0 2.v<u 答案为-1 3.v==u 答案为u

接下来是就是思考构造思路 对于异或 a^a=0 所以如果将v分成{u,d,d}其中d=(v-u)/2 是符合的 反之 若(v-u)%2==1则不符合 因为几个数的异或与这几个数的和同奇偶性

所以可以知道数组长度最大为3

最后想一下长度为2的情况：u为1的位置a,b也一定为1 位数为0的位置 a,b不可能同时为1 因此让a可能不为1的地方全为0,即a = (v - u)/2 check一下a^b是否为u

#define int long long
void solve(){
    int u=read(),v=read();
    if(u==0&&v==0){
        cout<<"0\n";
        return ;
    }
    if(v<u){
        cout<<"-1\n";
        return ;
    }
    if(u==v){
        cout<<"1\n";
        cout<<u<<'\n';
        return ;
    }
    if(v==0){
        cout<<"-1\n";
        return ;
    }
    if((v-u)&1)cout<<"-1\n";
    else{
        int d=(v-u)/2;
        int p=(v+u)/2;
        if((d&u)==0){
            cout<<2<<endl;
            cout<<d<<" "<<v-d<<'\n';
            return ;
        }
        cout<<"3\n";
        cout<<u<<" "<<d<<" "<<d<<'\n';
    }
    //puts(ans>0?"YES":"NO");
    //puts(ans>0?"Yes":"No");
}