自动搬运

查看原文

来自洛谷，原作者为

	___w **

搬运于2025-08-24 22:41:35，当前版本为作者最后更新于2023-06-07 21:21:27，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

P8700 [蓝桥杯 2019 国 B] 解谜游戏

题意简述

现有内中外三圈塑料棒，根数分别为 $4,8,12$ 根。有黄红绿三种颜色的塑料棒，根数分别为 $4,8,12$ 根。有三种操作，求是否能达成绿色移动到外圈、所有红色移动中圈、所有黄色移动到内圈的目标。

题目分析

先考虑搜索，每个状态有三种操作，呈指数型增长。况且判断状态是否重复就会牺牲大量的时间，就会超时，不可取。

我们注意到这一题只让我们求可行性，而不在乎具体的方案。要使所有颜色移到对应位置，我们只需要操作三。而操作一二都只是在选择操作三的位置，所以每个操作三都是有必然的联系的。

内圈周期为 $4$，中圈周期为 $8$，外圈周期为 $12$，共同的周期为 $4$。所以对于内圈的一个塑料棒，如下图，与其他 $5$ 个塑料棒是固定不变的，只能与这 $5$ 个交换。

若这 $6$ 个塑料棒的的颜色刚好为 $3$ 个绿色，$2$ 个红色和 $1$ 个黄色时，操作三是一定可以变成目标状态的：否则无论怎么交换，始终是那些颜色，不可能到达目标状态的。

所以具体的做法是枚举内圈的 $4$ 个塑料棒，再开个桶记录下这 $6$ 个塑料棒的颜色，再判断下即可，详细见代码。

代码

#include <bits/stdc++.h>
using namespace std;
int t, cnt[100];
string a, b, c;
int main() {
	cin >> t;
	while (t--) {
		cin >> a >> b >> c;
		bool flag = 1;
		for (int i = 0; i < 4; ++i) {
			memset(cnt, 0, sizeof(cnt));//清空桶 
			++cnt[a[i]], ++cnt[b[i]], ++cnt[c[i]];
			++cnt[a[i+4]], ++cnt[a[i+8]], ++cnt[b[i+4]];//统计6个塑料棒的颜色 
			if (cnt['Y'] != 1 || cnt['R'] != 2 || cnt['G'] != 3) {//判断条件 
				flag = 0;
				break;
			}
		}
		cout << (flag ? "YES" : "NO") << '\n';
	}
	return 0;
}