P9098 [PA2020] Zabawki 题解

题目梗概

输入两个字符串，如果经过若干次翻转后第一个字符串能变成第二个字符串则输出 \(TAK\)，否则输出 \(NIE\)。

思考

考虑字母的奇偶性问题。

选择一个区间 \(i ∼ i+j-1\)，且题目给出，满足 \(j\) 为奇数。

翻转这个区间，如 \(a\:b\:c\:d\:e(i=1\:j=5)\) 翻转后变为 \(e\:d\:c\:b\:a\)。

对于区间中的在 \(k\) 位置的字符会变为 \(i+j-1-(k-i)\)，化简后为 \(i+i+j-1-k\)。

讨论奇偶性，\(2i\) 为偶数，\(j\) 为奇数，\(1\) 为奇数。

偶数加奇数减奇数等于偶数，所以 \(k=偶数-k\)，则 \(2k\) 为偶数。

所以无论 \(k\) 是偶数还是奇数，交换的位置的奇偶性一定与它相同。

所以现在就有思路了，分别记录两个字符串奇数下标的字母和偶数下标的字母的数量，比较两个字符串数组是否相同即可。

代码

#include <bits/stdc++.h>
using namespace std;
int ans1[26][2], ans2[26][2];//用桶的方式储存
int main() {
	int n;
	string a, b;
	cin >> n >> a >> b;
	for (int i = 0; i < a.size(); i++) {
		ans1[a[i]-'a'][i & 1/*判断偶还是奇*/]++;//加入桶
		ans2[b[i]-'a'][i & 1/*同上*/]++;//同上
	}
	for (int i = 0; i < 26; i++) {
		if ((ans1[i][1] != ans2[i][1]) or (ans1[i][0] != ans2[i][0])) {//如果哪个地方不一样就输出NIE,然后结束循环
			cout << "NIE";
			return 0;
		}
	}
	cout << "TAK";
	return 0;
}