A. EhAb AnD gCd
题意：
给定两个数的gcd和lcm的和x，要求输出任意一组这对数。
思路：
考虑1的特殊性，1与任意数的gcd都是1，与任意数的lcm都是该数。
所以答案就是1和x-1了
最开始想偏了，还证明了几分钟别的……
代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll gcd(ll a,ll b){
return b==0?a:gcd(b,a%b);
}
ll lcm(ll a,ll b){
return a/gcd(a,b)*b;
}
int main(){
int t;cin>>t;
while(t--){
ll n;cin>>n;
printf("1 %lld
",n-1);
}
return 0;
}
B. CopyCopyCopyCopyCopy
题意：
给你一个长度为n的数组，问将该数组复制n次后得到的最长上升子序列的长度是多少。
思路：
我们记数组中不同元素的个数为sum,因为可以将该数组复制n次，我们可以在第一个数组中取出第一小的元素，在第二个数组中取出第二小的元素，以此类推，长度最大是sum
代码：
map写法 也可以直接用set计算，写map写习惯了
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e6+7;
ll a[maxn];
map<ll,ll>mp;
int main(){
ll t;cin>>t;
while(t--){
ll n;mp.clear();
cin>>n;
ll res=0;
for(int i=1;i<=n;i++){
cin>>a[i];
if(mp[a[i]]==0) mp[a[i]]=1,res++;
//else res++;
}
cout<<res<<endl;
}
return 0;
}
C. Ehab and Path-etic MEXs
题意：
给你一棵树，边的权值为0~n-2,问如何分配权值才能使得题意中的MEX最大值尽可能的小
思路：
先来考虑特殊情况，如果所有点的度都小于等于2，说明这棵树就是一条链，这时候怎么赋值都无所谓。
当有个点的度数大于2时，我们把0，1，2分别赋给他的三个边，其余的赋值不重的边就可以了。这时候，所有的路径都不会同时经过权值为0，1，2的边，得到的MEX最大值一定是最小的，此时MEX为2。
代码：
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+7;
int u[maxn],v[maxn];
int s[maxn];
int main(){
int n;cin>>n;
for(int i=1;i<n;i++){
cin>>u[i]>>v[i];
s[u[i]]++;s[v[i]]++;
}
int root=-1;
for(int i=1;i<=n;i++){
if(s[i]>=3){//找度数大于2的点
root=i;
break;
}
}
if(root==-1)//一条链
for(int i=1;i<n;i++) cout<<i-1<<endl;
else{
int x=3,cnt=0;
for(int i=1;i<n;i++){
if((v[i]==root||u[i]==root)&&cnt<3) cout<<cnt++<<endl;
else cout<<x++<<endl;
}
}
return 0;
}
D - Ehab the Xorcist
题意：
给你u,v，要求构造一个最短的数组，使得其所有元素异或为u，和为v
思路：
我们可以把异或看成是不进位的加法，这样就可以推出以下几种特殊情况（当时是真没往这想）
（1）当u>v时,一定无解。因为不存在一些数使得不进位的加法的和比进位的加法的和大
（2）当u == v == 0时，答案是0
（3）当u==v!=0时，答案是u，长度为1
再来看普通情况
根据异或的性质x^x=0，所以我们可以知道【u,x,x】满足要求，这时x=(v-u)>>1;这也就要求v-u一定要是偶数，所以当v-u是奇数时也就不能构造了。
然后就是神仙思路了
如果u和x的二进制上，没有一位两个都是1的，那么这时候u^x=u+x
所以可以把u和x合并为u+x,这样就变成了最短长度~
其余几个注意点都在代码里了~
代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;//注意数据范围~
const int maxn=1e6+7;
int main(){
ll u,v;
cin>>u>>v;
if(u>v||(v-u)%2) puts("-1");
else if(u==v){
if(u==0) puts("0");
else cout<<"1"<<endl<<u<<endl;
}
else{
ll x=(v-u)>>1;
//注意优先级
if((x^u)==x+u) cout<<"2"<<endl<<x+u<<" "<<x<<endl;
else cout<<"3"<<endl<<u<<" "<<x<<" "<<x<<endl;
}
return 0;
}
参考博客：传送门