Codeforces Round #628 (Div. 2) A、B、C、D-蒲公英云

EhAb AnD gCd

题意：给你一整数x，让你求两个数a,b ,使得 gcd(a,b)+lcm(a,b)=x

题解：令a=1，b=x-1 即可。

code：

#include<iostream>
#include<algorithm>
#include<cstring>
#include<map>
#include<queue>
#include<vector>
#include<set>
#include<sstream>
using namespace std;
typedef long long ll;
const ll maxn=1e6+10;
const ll inf=0x3f3f3f3f3f3f3f3f;
int main()
{ 
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    ll t;
    cin>>t;
    while(t--)
    { 
        ll x;
        cin>>x;
        cout<<1<<" "<<x-1<<endl;
    }
    return 0;
}

CopyCopyCopyCopyCopy

题意：给你一个无序的数组，问你通过copy这些无序数组LIS最大长度多少。

题解：无限copy数组，第一个次数组选最小的，第二个次数组选次小的…

其实就看这个无序数组有多少个不同的数就是答案。
set去重，输出set里数的数量。

code：

#include<iostream>
#include<algorithm>
#include<cstring>
#include<map>
#include<queue>
#include<vector>
#include<set>
#include<sstream>
using namespace std;
typedef long long ll;
const ll maxn=1e6+10;
const ll inf=0x3f3f3f3f3f3f3f3f;
set<ll> s;
int main()
{ 
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    ll t;
    cin>>t;
    while(t--)
    { 
        s.clear();
        ll n;
        cin>>n;
        for(int i=0;i<n;i++)
        { 
            ll a;
            cin>>a;
            s.insert(a);
        }
        cout<<s.size()<<endl;
    }
    return 0;
}

Ehab and Path-etic MEXs

题意：给出一个n个节点的树，让你给每条边(n-1条)填上一个唯一的数( 0~n-2 ), 使得任意mex(u,v)的最大值最小

mex(u,v)：表示从u到v这条路径上边权未出现过的数的最小的一个。

For example：
mex(u,v) 这条路径上的边权为1、3、4 (本题以0为最小值)，mex(u,v)=0，0未出现过且最小

题解：
1.如果他就一条链，n-1条边从头到尾的mex(u,v) 就是n-1
2.如果他有支链(某个点的度>=3),我们就把0、1放到这个点的主链部分，把2放到这个点连接的支链部分，这样可以保证整个数的任意mex(u,v)最大值为2，是optimal.

可以这样想，我们的目的就是让0、1、2不在同一链路上，我们找一条链路上的所有边，每个点连接两条边，我们可以把最小的两个边0、1加到这个点(某个点的度>=3)两侧,并且这条链路上我们不放2这个边权，我们这时已经让这条链路的mex=2，再把2连接到这个点(就是保证0、1、2不在同一链路上)，所以经过这个点的所有路径的最大mex为2，不经过这个点的所有mex=0

说的可能不明白，画图很清晰。

代码：找一个度为不小于3的点，让他的任意3条边等于0、1、2，其他边随机添加。

code：

#include<iostream>
#include<algorithm>
#include<cstring>
#include<map>
#include<queue>
#include<vector>
#include<set>
#include<sstream>
using namespace std;
typedef long long ll;
const ll maxn=1e6+10;
const ll inf=0x3f3f3f3f3f3f3f3f;
ll a[maxn],u[maxn],v[maxn],du[maxn],edge[maxn]; 
int main()
{ 
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    ll n;
    cin>>n;
    for(int i=0;i<n-1;i++)
    { 
        cin>>u[i]>>v[i];
        du[u[i]]++;
        du[v[i]]++;
        edge[i]=-1;
    }
    ll m=0,flag=0;
    for(int i=1;i<n;i++)
    { 
        if(flag) break;
        if(du[i]>=3)
        { 
            for(int j=0;j<n-1;j++)
            { 
                if(u[j]==i||v[j]==i)
                    edge[j]=m++;
                if(m==3)
                { 
                    flag=1;
                    break;
                }
            }
        }
    }
    for(int i=0;i<n-1;i++)
    { 
        if(edge[i]==-1)
            edge[i]=m++;
    }
    for(int i=0;i<n-1;i++)
        cout<<edge[i]<<'\n';
    return 0;
}

Ehab the Xorcist

题意：给你一个u，v ，让你求一个最小长度的数组满足

1.数组里所有数异或=u
2.数组的所有数和=v

我们分析数组异或值为u，保证最小长度，所以数组最长为3个：u，(v-u)/2, (v-u)/2
u⊕x⊕x=u 其中x=(v-u)/2;

a+b=a⊕b+2*(a&b)
所以：a+b>=a⊕b

&运算，全1位1，否则为0，
⊕运算，相同为0，不同为1，

所以我们分情况讨论
1.u>v 输出-1
2.u=v 输出1 u，最短的数组就是他本身。
对于 u，(v-u)/2, (v-u)/2 ，此时为0，u，不用证明就知道最小数组肯定就是u本身。

证明：
a+b=a⊕b+2*(a&b)，即a&b=0 ，说明a和b对应的位数只出现了最多1个1，所以不会牵扯到二进制加法的进制问题，即a+b=a⊕b，a+0=a⊕0

3.u<v

(1) (v-u)是奇数：输出-1，

证明：
我们只看最后一位：
偶⊕偶=偶，偶+偶=偶
偶⊕奇=奇，偶+奇=奇
奇⊕奇=偶，奇+奇=偶
所以我们可以看出，v-u 一定是偶数才可以找到数组。

(2) (v-u)是偶数：

我们考虑最小的是数组2个元素，
想法一：我们把u，(v-u)/2, (v-u)/2，前两项合并为(v-u)/2、(v+u)/2, 我们如果合并后两项在这里不符合条件，因为u⊕(v-u)=u ,v-u一定为0，不满足u<v
想法二： a+b=a⊕b+2*(a&b) a&b=(v-u)/2 a和b求&的值，此值一定满足如果二进制位上如果是1，a和b的此位也一定是1，a和b的其他位二者最多只有1个1。假设如果有1我们就放到a的二进制位上，则b的这一位就是0，此时的b就等于(v-u)/2 ，因为a+b=v，则a=(v+u)/2

最后判断一下(v-u)/2⊕(v+u)/2=u && (v-u)/2+(v+u)/2=v 满足就输出这两个值；

以上都不满足最坏就是数组为3的情况，直接输出。

#include<iostream>
#include<algorithm>
#include<cstring>
#include<map>
#include<queue>
#include<vector>
#include<set>
#include<sstream>
using namespace std;
typedef long long ll;
const ll maxn=1e6+10;
const ll inf=0x3f3f3f3f3f3f3f3f;
int main()
{ 
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    ll u,v;
    cin>>u>>v;
    if(u>v||(v-u)&1)
    { 
        cout<<"-1"<<endl;
    }
    else if(u==v&&v==0)
    { 
        cout<<"0"<<endl;
    }
    else if(u==v&&u!=0&&v!=0)
    { 
        cout<<1<<endl<<u<<endl; 
    }
    else
    { 
        ll a=(v-u)/2;
        ll b=(v+u)/2;
        ll ans=a^b;
        if((ans==u)&&(a+b==v))
        { 
            cout<<2<<endl<<a<<" "<<b<<endl;
        }
        else 
        { 
            cout<<3<<endl<<u<<" "<<a<<" "<<a<<endl;
        }
    }
    return 0;
}