【洛谷 P8700】[蓝桥杯 2019 国 B] 解谜游戏题解（字符串+映射+周期性）

本文主要是介绍【洛谷 P8700】[蓝桥杯 2019 国 B] 解谜游戏题解（字符串+映射+周期性），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

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

题目背景

题目描述

小明正在玩一款解谜游戏。谜题由 $24$ 根塑料棒组成，其中黄色塑料棒 $4$ 根，红色 $8$ 根，绿色 $12$ 根 (后面用 Y 表示黄色、R 表示红色、G 表示绿色)。初始时这些塑料棒排成三圈，如上图所示，外圈 $12$ 根，中圈 $8$ 根，内圈 $4$ 根。

小明可以进行三种操作：

将三圈塑料棒都顺时针旋转一个单位。例如当前外圈从 $0$ 点位置开始顺时针依次是 YRYGRYGRGGGG，中圈是 RGRGGRRY，内圈是 GGGR。那么顺时针旋转一次之后，外圈、中圈、内圈依次变为：GYRYGRYGRGGG、YRGRGGRR 和 RGGG。
将三圈塑料棒都逆时针旋转一个单位。例如当前外圈从 $0$ 点位置开始顺时针依次是 YRYGRYGRGGGG，中圈是 RGRGGRRY，内圈是 GGGR。那么逆时针旋转一次之后，外圈、中圈、内圈依次变为：RYGRYGRGGGGY、GRGGRRYR 和 GGRG。
将三圈 $0$ 点位置的塑料棒做一个轮换。具体来说：外圈 $0$ 点塑料棒移动到内圈 $0$ 点，内圈 $0$ 点移动到中圈 $0$ 点，中圈 $0$ 点移动到外圈 $0$ 点。例如当前外圈从 $0$ 点位置开始顺时针依次是 YRYGRYGRGGGG，中圈是 RGRGGRRY，内圈是 GGGR。那么轮换一次之后，外圈、中圈、内圈依次变为：RRYGRYGRGGGG、GGRGGRRY 和 YGGR。

小明的目标是把所有绿色移动到外圈、所有红色移动中圈、所有黄色移动到内圈。给定初始状态，请你判断小明是否可以达成目标？

输入格式

第一行包含一个整数 $T$ ，代表询问的组数。 $\le T \le 100)$ 。

每组询问包含 $3$ 行：

第一行包含 $12$ 个大写字母，代表外圈从 $0$ 点位置开始顺时针每个塑料棒的颜色。

第二行包含 $8$ 个大写字母，代表中圈从 $0$ 点位置开始顺时针每个塑料棒的颜色。

第三行包含 $4$ 个大写字母，代表内圈从 $0$ 点位置开始顺时针每个塑料棒的颜色。

输出格式

对于每组询问，输出一行 YES 或者 NO，代表小明是否可以达成目标。

样例 #1

样例输入 #1

2
GYGGGGGGGGGG
RGRRRRRR
YRYY
YGGGRRRRGGGY
YGGGRRRR
YGGG

样例输出 #1

YES
NO

提示

蓝桥杯 2019 年国赛 B 组 H 题。

思路

每个圈中每4个元素为1个周期。其中，外圈有3个周期，中圈有2个周期，内圈有1个周期。每个周期内的元素可以分为四组，每个周期中相同位置的塑料棒被认为是一组。无论旋转多少次，塑料棒的位置总是在组内循环。

图中数字代表组号，数字相同的元素可以调换位置。

首先，定义一个长度为4的map数组，存储每组中每个颜色的塑料棒的数量。

然后，读入外圈、中圈和内圈的塑料棒的颜色，并根据塑料棒的位置和颜色进行分组统计，每个周期中相同位置（i % 4）的塑料棒被认为是一组。

接着，检查每组中的塑料棒颜色数量是否满足目标状态：每组应有3个绿色，2个红色，1个黄色。如果所有组都满足，那么输出"YES"，否则输出"NO"。

AC代码

#include <algorithm>
#include <cmath>
#include <iostream>
#include <map>
#define AUTHOR "HEX9CF"
using namespace std;
using ll = long long;const int N = 1e6 + 7;
const int INF = 0x3f3f3f3f;
const ll MOD = 1e9 + 7;int n;void solve() {map<char, int> cnt[4];for (int i = 0; i < 4; i++) {// 初始化cnt[i]['G'] = 0;cnt[i]['Y'] = 0;cnt[i]['R'] = 0;}string str[3];for (int i = 2; i >= 0; i--) {cin >> str[i];}for (int j = 0; j < 3; j++) {for (int i = 0; i < (j + 1) * 4; i++) {// cout << i << " " << i % 8 << " " << i % 4 << endl;// 统计每组中某颜色的数量cnt[i % 4][str[j][i]]++;}}bool ans = 1;for (int i = 0; i < 4; i++) {// 每组应有3绿2红1黄ans &= (cnt[i]['G'] == 3);ans &= (cnt[i]['R'] == 2);ans &= (cnt[i]['Y'] == 1);}cout << (ans ? "YES" : "NO") << "\n";
}int main() {ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin >> n;while (n--) {solve();}return 0;
}