题目链接

A题.EhAb AnD gCd

题意：
$给一个x，求a和b，使得lcm(a,b)+gcd(a,b)=x$给一个x，求a和b，使得lcm(a,b)+gcd(a,b)=x
题解：
$直接令a=1,b=x-1$直接令a=1,b=x−1

$这样lcm(a,b)=x-1,gcd(a,b)=1，公式成立$这样lcm(a,b)=x−1,gcd(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的数组

$可以把给定的数组再次接到数组后面使数组长度加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条边$n个点形成的连通图，给定n−1条边

让你为每条边给定一个label（0<=x<=n−2）

$Mex(u,v)表示u结点到v结点的简单路中没出现过的label的最小值$Mex(u,v)表示u结点到v结点的简单路中没出现过的label的最小值

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

$其他点可以随意给$其他点可以随意给

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

$这样的话，除了成链不管怎样Mex（u，v）都不会超过2$这样的话，除了成链不管怎样Mex（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代表一个数组的全部异或$给定一个u代表一个数组的全部异或

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

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

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

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

$else数组里只有一个元素u$else数组里只有一个元素u

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

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