自动搬运

查看原文

来自洛谷，原作者为

	封禁用户 None

搬运于2025-08-24 22:58:57，当前版本为作者最后更新于2024-04-09 18:09:40，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

思路

$$\begin{aligned}\because&\frac{(A_1+A_2)+(A_2+A_3)+\dots+(A_{n-1}+A_n)+(A_n+A_1)}{2}\\ &=A_1+A_2+A_3+\dots+A_{n-1}+A_n\end{aligned}\\ \because n \bmod 2 = 1\\ \begin{aligned}&\therefore A_x=(A_1+A_2+A_3+\dots+A_{n-1}+A_n)-\\ &\begin{cases} [(A_1+A_2)+\dots+(A_{x-2}+A_{x-1})+(A_{x+1}+A_{x+2})+\dots+(A_{n-1}+A_n)]&x \bmod 2 = 1\\ [(A_2+A_3)+\dots+(A_{x-2}+A_{x-1})+(A_{x+1}+A_{x+2})+\dots+(A_{n-2}+A_{n-1})+(A_n+A_1)]&x \bmod 2 = 0\end{cases}\end{aligned}$$

只需要使 $(A_1+A_2)+(A_2+A_3)+\dots+(A_{n-1}+A_n)+(A_n+A_1)\bmod 2 = 0$ 即可，考虑将数字串划分分成 $n$ 个可以有前导 $0$ 的数字，使得末尾数字的和为偶数。

最后一位数字必选为末尾数字，剩下 $n-1$ 个自己选择，因此，只需要看是否有 $n-1$ 个不同的数字和最后一位数字的和为偶数即可。

末尾为偶数：判断是否可以从前面选出 $n-1$ 个数和为偶数即可。

末尾为奇数：先拿另一个奇数凑成偶数，再判断是否可以从其他数中选出 $n-2$ 个数和为偶数即可。

code

写的有点复杂……

#include<bits/stdc++.h>
using namespace std;
void ask(int od,int ev,int cnt){//判断od个奇数、ev个偶数中能否选cnt个数使得和为偶数
	if(od+ev<cnt){//个数都不够
		printf("No\n");
		return;
	}
	if(cnt%2==1){//奇数个，需要先拿一个偶数，避免下面使用奇数时会选出半个一对奇数导致结果为奇数
		if(!ev){//没有偶数
			printf("No\n");
			return;
		}
		cnt--;
		ev--;
	}
	cnt-=od/2*2;//每两个一对奇数
	if(cnt<=0){
		printf("Yes\n");
		return;
	}
	cnt-=ev;
	if(cnt<=0){
		printf("Yes\n");
		return;
	}
	printf("No\n");
}
int main(){
	int tc,n,od,ev;
	string s;
	scanf("%d",&tc);
	while(tc--){
		scanf("%d",&n);
		cin>>s;
		od=0;
		ev=0;
		for(int i=0;i<s.size()-1;i++)//统计奇数和偶数的数量
			if((s[i]-'0')%2==0)
				ev++;
			else
				od++;
		if((s[s.size()-1]-'0')%2==0)
			ask(od,ev,n-1);//末尾为偶数
		else{//末尾为奇数
			if(n==1){//特判：一个数字，但是是奇数
				printf("No\n");
				continue;
			}
			if(od==0){//特判没有奇数
				printf("No\n");
				continue;
			}
			od--;//先用一个奇数
			ask(od,ev,n-2);
		}
	}
	return 0;
}