Codeforces Round #628 (Div. 2) A、B、C、D

傷城~ 2023-07-15 09:04 16阅读 0赞

[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;
    }

[EhAb AnD gCd]: http://codeforces.com/contest/1325/problem/A
[CopyCopyCopyCopyCopy]: https://codeforces.com/contest/1325/problem/B
[Ehab and Path-etic MEXs]: https://codeforces.com/contest/1325/problem/C
[Ehab the Xorcist]: https://codeforces.com/contest/1325/problem/D