Pinely Round 4 (Div. 1 + Div. 2) 题解 ABCD

Pinely Round 4 (Div. 1 + Div. 2)

A. Maximize the Last Element

题意

给一个长度为$n$的数组 , (n为奇数) ， 每次你可以删除数组中相邻的两个数，直到数组剩下一个数，问数组最终剩下的那个数最大为多少。

思路

可以发现， 我们最终只有可能留下奇数位的元素$a_1,a_3,...,a_n$ ，对其取max即可。

证明： 整个数组中有$\frac{n+1}{2}$ 个奇数数位， $\frac{n-1}{2}$ 个偶数数位， 即奇数下标一定比偶数多一个， 而对于每次删除操作，一定会删除一个奇数下标的元素和一个偶数下标的元素（因为二者相邻）， 并且不会改变其他下标的奇偶性， 因此进行$\frac{n-1}{2}$ 轮删除后， 奇数下标只剩$1$ 个，而偶数下标剩0个。

代码

#include<bits/stdc++.h> using namespace std; #define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); #define int long long #define rep(i,l,r) for(int i = l;i<=r;i++) #define per(i,r,l) for(int i = r;i>=l;i--) const int INF = 0x3f3f3f3f3f3f3f3f; typedef pair<int,int> PII; void solve(){ 	int n; 	cin>>n; 	int ans = 0; 	for(int i = 1;i<=n;i+=2){ 		int num;cin>>num; ans = max(ans,num); 	} 	cout<<ans<<endl; } signed main(){ 	int T = 1; 	cin>>T; 	while(T--){ 		solve(); 	} 	return 0; } 

B. AND Reconstruction

题意

给你一个长度为$n-1$ 的数组b，请你构造一个长度为n的数组a，满足$a[i]\&a[i+1]=b[i]$ , 其中$\&$表示按位与。

若构造不出合法的数组$a$ ,输出-1

思路

我们既然要构造a数组，那么就考虑$a[i]$ 受到b的哪些元素影响，可以发现$a[i]$ 只和$b[i-1],b[i]$ 有关， 并且$b[i-1],b[i]$ 中为1的数位，在$a[i]$ 中都应该是1， 所以我们让$a[i]=b[i-1]|b[i]$ 就可以得到最终的a[i]数组， 然后我们再按顺序判断一下对于所有的$b[i]$是否都满足$a[i]\&a[i+1]=b[i](1\le i\le n-1)$

代码

#include<bits/stdc++.h> using namespace std; #define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); #define int long long #define rep(i,l,r) for(int i = l;i<=r;i++) #define per(i,r,l) for(int i = r;i>=l;i--) const int INF = 0x3f3f3f3f3f3f3f3f; typedef pair<int,int> PII; void solve(){ 	int n; 	cin>>n; 	vector<int>a(n+5),b(n+5); 	 	for(int i = 1;i<n;i++){ 		cin>>b[i]; 	} 	for(int i = 1;i<=n;i++){ 		a[i] = b[i-1] | b[i]; 	} 	for(int i = 1;i<n;i++){ 		if((a[i] & a[i+1])!= b[i]) {cout<<-1<<endl;return ;} 	} 	for(int i = 1;i<=n;i++){ 		cout<<a[i]<<" "; 	} 	puts(""); } signed main(){ 	int T = 1; 	cin>>T; 	while(T--){ 		solve(); 	} 	return 0; } 

C. Absolute Zero

题意

给你一个长度为n的数组a，$a_1,a_2,...,a_n$ , （$0\le a[i]\le 10^9$） 你要进行至多40次操作（无需令操作数最少）， 每次操作选择一个数x， 并令所有的$a_i,(1\le i\le n)$ 变为$|a_i - x | $ , 其中的$|v|$ 表示$v$ 的绝对值。

在进行完一些操作之后，让整个a数组全部变为0。 如果无法实现， 输出-1。

思路

首先考虑不成立的情况， 如果我们令数组中所有的元素都同时减去一个偶数，那么他们的奇偶性都会保持不变； 相反如果同时减去一个奇数，那么他们的奇偶性都会变化。 而我们最终要求所有的数都是0，即都是偶数。于是我们就可以发现，如果数组a中同时含有奇数以及偶数，那么就无法让a全部变为0。

接下来我们考虑如何解决这道题。最多40次使我们很容易想到按位处理。

起初所有的$a[i]$ 都满足$a[i]\le 10^9<2^{30}$ , 所以我们第一次操作选择$2^{29}$ ，便可以让所有的数都满足$0\le a[i]\le 2^{29}$ ,

再接着我们第二次操作选择$2^{28}$ ， 于是所有的数都满足了$0\le a[i]\le 2^{28}$

不断重复如上选择，直到最后选择了$2^0$ 。

我们不断如上选择会不断缩小a数组元素的取值范围。使得最终都变为0 。

需要特殊注意的是，此时如果a数组原本为奇数数组，那么所有的数都变为了0 。 但如果a数组是偶数数组，那么最终还要在选择一次0.

代码

#include<bits/stdc++.h> using namespace std; #define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); #define int long long #define rep(i,l,r) for(int i = l;i<=r;i++) #define per(i,r,l) for(int i = r;i>=l;i--) const int INF = 0x3f3f3f3f3f3f3f3f; typedef pair<int,int> PII; void solve(){ 	int n; 	cin>>n; 	vector<int> a(n+5); 	rep(i,1,n){ 		cin>>a[i]; 	} 	int odd=0,even=0;     //特判是否能够成立 	rep(i,1,n){ 		if(a[i]%2) odd=1; 		else even=1; 	} 	if(odd&&even){ // 如果同时有奇数和偶数，就不能 		cout<<-1<<endl; 		return ; 	} 	vector<int> ans;//存储答案 	for(int i=29;i>=0;i--) ans.push_back(1<<i);     if(even) ans.push_back(1); 	cout<<ans.size()<<endl; 	for(auto p : ans){ 		cout<<p<<' '; 	}puts(""); }  signed main(){ 	int T = 1; 	cin>>T; 	while(T--){ 		solve(); 	} 	return 0; } 

D. Prime XOR Coloring

题意

给你一个无向图，图中有$n$个节点，编号从$1$到$n$。 如果$u\oplus v$ 是一个质数 （$u\oplus v$表示u和v进行按位异或） ，那么$u$和$v$之间有一条边相连。 请你给这$n$个节点染色，使得不存在两个相邻的节点有相同的颜色。

思路

先给出结论，所有的节点最多只需要4种颜色。

因为节点$1,3,4,6$ 所以他们四个的颜色必须不同，我们为他们四个分配四种颜色。

于是当$n<6$ 时，我们直接打表输出。 当$n>6$ 时，我们令$a[i]=i\%4+1$ , 这样就保证了任意两个相同颜色的节点的差一定是4的倍数，那么他们的异或就一定不是质数。也就满足了题意。。

代码

#include<bits/stdc++.h> using namespace std; #define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); #define int long long #define rep(i,l,r) for(int i = l;i<=r;i++) #define per(i,r,l) for(int i = r;i>=l;i--) const int INF = 0x3f3f3f3f3f3f3f3f; typedef pair<int,int> PII; void solve(){ 	int n;cin>>n; 	if(n == 1){ 		cout<<"1\n1\n";return ; 	} 	if(n == 2){ 		cout<<"2\n1 2\n";return ; 	} 	if(n == 3){ 		cout<<"2\n1 2 2\n";return ; 	} 	if(n == 4){ 		cout<<"3\n1 2 2 3\n";return ; 	} 	if(n==5){ 		cout<<"3\n1 2 2 3 3\n";return ; 	} 	vector<int> color(n+5); 	for(int i = 1;i<=4;i++){ 		color[i] = i; 	} 	for(int i = 5;i<=n;i++){ 		int t = i ^ 2; 		if(i%2){ 			color[i] = 1; 			if(t <= i) color[i] = 4 - color[t]; 		}else { 			color[i] = 2; 			if(t <= i) color[i] = 6 - color[t]; 		} 	}w 	cout<<"4\n"; 	for(int i = 1;i<=n;i++){ 		cout<<color[i]<<' '; 	} 	puts(""); }  signed main(){ 	int T = 1; 	cin>>T; 	while(T--){ 		solve(); 	} 	return 0; }