Codeforces 1730 D

题意

定义一次“操作”为

把字符串 $ a $ 的前 $ k $ 个字母与字符串 $ b $ 的后 $ k $ 个字母交换。

问能不能经过有限次操作后，让 $ a = b $ 。
注：$ |a| = |b| = n $ 。

思路

先放结论：

将 $ a_1 $ 与 $ b_n $ 配对，$ a_2 $ 与 $ b_{n – 1} $ 配对 …… $ a_n $ 与 $ b_1 $ 配对成 无序组 。
如果这些对子能组成回文（例如：$ (a, c), (a, b), (c, c), (a, b), (c, a) $ 就是回文），那么可以。
在 $ n \bmod 2 = 1 $ 的时候，我们还需要保证对于中间那一对 $ a_i = b_i $ 。

设 $ a = \texttt{abxxxx}, b = \texttt{xxxxcb} $ 。
魔性的操作来了！
把 $ \ b \ $ 反 转 ！

分组变成了 $ (a_1, b_1), (a_2, b_2), \cdots, (a_n, b_n) $ 。
（接下来讲的 $ b $ 都是反转后的 $ b $）
我们需要证明：

1. 每组两个元素相对位置相等（即，对应 $ a_i $ 的永远是 $ b_i $）。
   

   可我证不出来（别打死我）

2. 每组两个元素可以随便交换
   

   $ k = i, 1, i $
   举个例子，交换 $ a_2, b_2 $ 。

   $ k = 2 $ ，$ a = \texttt{cbxxxx}, b = \texttt{baxxxx} $ 。
   $ k = 1 $ ，$ a = \texttt{bbxxxx}, b = \texttt{caxxxx} $ 。
   $ k = 2 $ ，$ a = \texttt{acxxxx}, b = \texttt{bbxxxx} $ 。

3. 组可以换到别处去（把 $ (a_i, b_i) $ 换到 $ (a_j, b_j) \(）（\) i < j $）
   

   $ k = i, j \( 举个例子，\) (a_3, b_3) \to (a_2, b_2) $。

   $ k = 2 $ ，$ a = \texttt{cbxxxx}, b = \texttt{baxxxx} $ 。
   $ k = 3 $ ，$ a = \texttt{xabxxx}, b = \texttt{xabxxx} $ 。

有了这三点，就好证明了。

代码

#include <bits/stdc++.h>
using namespace std;

struct pp {
	char a, b;
} s[100005];

int cnt[150][150];

int main() {
	int t;
	cin >> t;
	while (t--) {
		memset(cnt, 0, sizeof cnt);
		int n;
		cin >> n;
		string s1, s2;
		cin >> s1 >> s2;
//		cerr << s1 << " " << s2 << endl;
		for (int i = 0; i < n; i++) {
			s[i].a = min(s1[i], s2[n - i - 1]);
			s[i].b = max(s1[i], s2[n - i - 1]);
//			cerr << s[i].a << " " << s[i].b << endl;
		}
		for (int i = 0; i < n; i++) {
			cnt[s[i].a][s[i].b]++;
		}
		bool flag = 1;
		bool odded = !(n & 1);
		for (char ch = 'a'; ch <= 'z'; ch++) {
			if (cnt[ch][ch] & 1) {
				if (odded) {
					flag = 0;
				} else {
					odded = 1;
				}
			}
		}
		for (char i = 'a'; i <= 'z'; i++) {
			for (char j = i + 1; j <= 'z'; j++) {
				if (i != j) {
					flag &= (cnt[i][j] % 2 == 0);
				}
			}
		}
		if (flag) {
			puts("YES");
		} else {
			puts("NO");
		}
	}
	return 0;
}

原文地址：http://www.cnblogs.com/AProblemSolver/p/16849308.html