题意分析

题目背景

本题属于组合数学与状态转换问题，描述一个由黑白圆盘组成的环形轨道上的谜题。通过两种操作（翻转和移动）来使同色圆盘聚集在一起。

核心规则

1. 操作定义：
   • 翻转操作：反转任意三个连续圆盘的颜色（0变1，1变0）。
   • 移动操作：将所有圆盘顺时针移动一个位置（循环左移）。
2. 目标状态：所有相同颜色的圆盘必须相邻。
3. 输入限制：圆盘总数$m+n$在10到30之间。

关键观察

• 移动操作的影响：改变圆盘位置的奇偶性（索引从0开始）。
• 翻转操作的影响：对三个连续圆盘的翻转会改变其颜色的奇偶分布。
• 奇偶长度的差异：
  • 奇数长度：总能通过操作达到目标状态。
  • 偶数长度：需满足奇偶位置上1的数量差不超过1。

解题思路

1. 奇数长度序列

• 直接判定：若序列长度$n$为奇数，输出YES。
  数学依据：奇数长度下，通过移动和翻转可以灵活调整奇偶位置的分布。

2. 偶数长度序列

• 统计奇偶位置：
  • 设偶数位置（索引0,2,4,…）的1的数量为$E$。
  • 奇数位置（索引1,3,5,…）的1的数量为$O$。
• 平衡条件：$|E - O| \leq 1$。
  数学解释：
  • 翻转操作对差值的影响为$\pm1$或$\pm3$。
  • 移动操作可交换$E$和$O$的值（符号反转）。
  • 因此，仅当$|E - O| \leq 1$时可达目标状态。

3. 算法流程

1. 输入处理：读取测试用例，存储序列。
2. 奇偶判断：
   • 奇数长度：直接输出YES。
   • 偶数长度：统计$E$和$O$，判断$|E - O|$是否$\leq1$。
3. 输出结果：根据条件输出YES或NO。

算法实现

代码框架

#include <bits/stdc++.h>

using namespace std;
 
int main()
{
	int N;
	cin >> N;
	for (int i = 0;i<N;i++)
	{
		int n;
		cin >> n;
		vector<int> eles(n);
		for (int j = 0;j<n;j++)
		{
			cin >> eles[j];
		}
		if (n%2 == 1)
		{
			cout << "YES"<<endl;
		}else{
			int oneEvenPos = 0;
			int oneOddPos = 0;
			for (int j = 0;j<n;j++)
			{
				if (eles[j] == 1 && j%2 == 0)
				{
					oneEvenPos ++;
				}
				if (eles[j] == 1 && j%2 == 1)
				{
					oneOddPos ++;
				}
			}
			if (abs(oneOddPos - oneEvenPos) >=2)
			{
				cout << "NO" << endl;
			}else{
				cout << "YES" << endl;
			}
		}
	}
	return 0;
}

关键步骤

1. 输入读取：处理多个测试用例，存储圆盘序列。
2. 奇偶统计：
   • 遍历序列，统计偶数位置和奇数位置的1的数量。
3. 条件判断：
   • 偶数长度时，检查$|E - O|$是否满足平衡条件。

复杂度分析

• 时间：$O(T \cdot n)$，其中$T$为测试用例数，$n$为圆盘数量。
• 空间：$O(n)$，存储圆盘序列。