A题.EhAb AnD gCd

题意：
$给一个 x ，求 a 和 b ，使得 l c m (a, b) + g c d (a, b) = x$
题解：
$直接令 a = 1, b = x - 1$

$这样 l c m (a, b) = x - 1, g c d (a, b) = 1 ，公式成立$

AC代码

#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define endl '\n'
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int mod=1e9+7;
//const int mod=998244353;
const double eps = 1e-10;
const double pi=acos(-1.0);
const int maxn=2e5+10;
const ll inf=0x3f3f3f3f;



int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    int t;cin>>t;
    while(t--){
        int x;cin>>x;
        cout<<1<<' '<<x-1<<endl;
    }


    return 0;
}

B题.CopyCopyCopyCopyCopy

题意：
$给一个长度为 n 的数组$

$可以把给定的数组再次接到数组后面使数组长度加 n$

$这个操作可以执行无数次，问能形成的最长上升序列$
题解：
$由于操作可以执行无数次，所以可以把每一个数都取到$

$但是题目要求是最长上升序列，中间不能相等，所以重复元素不计$

AC代码

#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define endl '\n'
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int mod=1e9+7;
//const int mod=998244353;
const double eps = 1e-10;
const double pi=acos(-1.0);
const int maxn=2e5+10;
const ll inf=0x3f3f3f3f;


int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    int t;cin>>t;
    while(t--){
        int n;cin>>n;
        map<int,int> m;
        int ans=0;
        for(int i=1;i<=n;i++){
            int x;cin>>x;
            if(!m[x])ans++,m[x]++;
        }
        cout<<ans<<endl;
    }


    return 0;
}

C题.Ehab and Path-etic MEXs

题意：
$n 个点形成的连通图，给定 n - 1 条边$

$让你为每条边给定一个 l a b e l （ 0 < = x < = n - 2 ）$

$M e x (u, v) 表示 u 结点到 v 结点的简单路中没出现过的 l a b e l 的最小值$

$让你给定一种方式，令 \forall u \forall v M a x (u, v) 的值最小$
题解：
$将分叉的位置 (即度大于 2 的点) 周围的任意三条边给上 0 ， 1 ， 2 的 l a b e l$

$其他点可以随意给$

$这样给后，任意一条简单路会不通过该点的分叉，或者通过其中一条或两条$

$这样的话，除了成链不管怎样 M e x （ u ， v ）都不会超过 2$

$如果形成了一条链，那么在树的直径里一定所有数会全部包括，所以不管怎么给结果都是一定的$
AC代码

#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define endl '\n'
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int mod=1e9+7;
//const int mod=998244353;
const double eps = 1e-10;
const double pi=acos(-1.0);
const int maxn=2e5+10;
const ll inf=0x3f3f3f3f;

int n;
int de[maxn],ans[maxn];
vector<pii> g[maxn];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    cin>>n;
    memset(ans,-1,sizeof ans);
    for(int i=1;i<n;i++){
        int u,v;cin>>u>>v;
        de[u]++,de[v]++;
        g[u].pb(mp(v,i));
        g[v].pb(mp(u,i));
    }
    int cnt=0;
    for(int i=1;i<=n;i++){
        if(de[i]>2){
            for(auto j:g[i]){
                ans[j.se]=cnt++;
                if(cnt==3)break;
            }
            break;
        }
    }
    for(int i=1;i<n;i++)
        if(ans[i]==-1)ans[i]=cnt++;
    for(int i=1;i<n;i++)
        cout<<ans[i]<<endl;
    return 0;
}

D题.Ehab the Xorcist

题意：
$给定一个 u 代表一个数组的全部异或$

$给定一个 v 代表一个数组的全部和$

$问你这个数组最短的长度及其每个元素$
题解：
对于二进制 $a + b$ 的某一位来说
$a <mtext> </mtext> x o r <mtext> </mtext> b$ 可以表示 $a + b$ 的本位， $a$ & $b$ 可以表示 $a + b$ 的进位
然后将 $a$ & $b$ 左移一位就可以表示 $a + b$
所以可以得到
$a + b = a <mtext> </mtext> x o r <mtext> </mtext> b + 2 * a & b$

所以通过本题可以推出
$v = u + 2 * a & b$

所以可以知道如果 $u > v$ 或者 $(u - v) % 2 = 1$ 这样是恒不成立的
然后特判一下 $u = v$ 的情况
$i f (u = v = 0) 数组是空的$

$e l s e 数组里只有一个元素 u$

其他情况下数组肯定至少有两个元素
然后通过刚才的公式计算出 $a & b$ ，循环判断 $a & b$ 和 $a <mtext> </mtext> x o r <mtext> </mtext> b$ 的每一个二进制位
如果 $a & b$ 在该位是 $1$ ，说明该位每个数都为 $1$ ，所以用 $c n t [i] + = 2$
如果 $a <mtext> </mtext> x o r <mtext> </mtext> b$ 在该位是 $1$ ，说明该位有奇数个 $1$ ，所以需要 $c n t [i] + = 1$
这样 $c n t$ 数组的最大数就代表数组的长度
最后循环每次取出一个作为其中一个数二进制位的第i位
首先令 $x = a & b = (v - u) / 2$
如果长度为 $3$ 的情况就是出现过两个都为 $1$ 的时候 $($ $即 u & x! = 0$ $)$
长度为 $3$ 的时候，其实每个二进制位 $x = 1$ 的时候都在这位加了两次，所以数组中会出现两个 $x$ ,由于每次在某二进制位 $u = 1$ 的时候该位都会加 $1$ ，所以数组中可以分离出一个 $u$
最终可以确定此时数组的元素为 $[u, x, x]$

如果长度为 $2$ 的情况就是没出现过两个都为 $1$ 的时候 $($ $即 u & x = = 0$ $)$
此时可以发现数组依旧可以分离出两个 $x$ ，一个 $u$ ，但是此时的数组长度为2，不能全部直接放到数组里。但是此时 $u & x = = 0$ ，说明如果 $u + x <mtext> </mtext> x$ 为1的二进制位u都为0，所以再用一个 $x$ 二者异或就会重新得到u
所以可以得到最后数组的元素为 $[u + x, x]$

AC代码

#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define endl '\n'
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int mod=1e9+7;
//const int mod=998244353;
const double eps = 1e-10;
const double pi=acos(-1.0);
const int maxn=2e5+10;
const ll inf=0x3f3f3f3f;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    ll u,v;cin>>u>>v;
    if(v-u<0||(v-u)%2){cout<<-1;return 0;}
    ll d=v-u;
    if(!d){
        if(!u)cout<<0;
        else cout<<1<<endl<<u;
    }
    else{
        ll t=d/2;
        if((t&u)==0)cout<<2<<endl<<t<<' '<<u+t<<endl;
        else cout<<3<<endl<<t<<' '<<t<<' '<<u<<endl;
    }
    return 0;
}

Codeforces Round#628(Div.2)解题报告

A题.EhAb AnD gCd

B题.CopyCopyCopyCopyCopy

C题.Ehab and Path-etic MEXs

D题.Ehab the Xorcist