题意：
给定两个数的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",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; }
参考博客：传送门
