「PA 2020」Zabawki 题解

算法思路

本题使用奇偶性分析和字符频率统计来判断是否可以通过翻转操作将一个字符串转换为另一个字符串。核心观察是翻转操作对字符位置的奇偶性影响。

关键观察

1. 翻转操作的性质

• 每次翻转奇数个连续字符
• 翻转操作会改变字符位置的奇偶性
• 字符在奇数位置和偶数位置的分布是关键

2. 必要条件

对于两个字符串 $s$ 和 $t$，要能通过翻转操作相互转换，必须满足：

• 每个字符在奇数位置的出现次数相同
• 每个字符在偶数位置的出现次数相同

代码解析

字符频率统计

map<char, int> mp[2];  // mp[0]统计偶数位置，mp[1]统计奇数位置
string s;
cin >> s;

// 统计原字符串的字符分布
for (int i = 0; i < n; i++)
    mp[i & 1][s[i] - 'a']++;  // i&1为0表示偶数位置，1表示奇数位置

比较目标字符串

cin >> s;

// 从目标字符串中减去相应计数
for (int i = 0; i < n; i++)
    mp[i & 1][s[i] - 'a']--;

检查条件

int ans = 1;
for (int i = 0; i < 2; i++)           // 检查奇数和偶数位置
    for (auto [x, y] : mp[i])         // 遍历每个字符的计数
        if (y)                        // 如果计数不为0
            ans = 0;                  // 不满足条件

cout << (ans ? "TAK" : "NIE") << "\n";

算法正确性证明

必要性证明

如果两个字符串的奇偶位置字符分布不同，则无法通过翻转操作转换：

• 翻转奇数长度区间会改变区间内所有字符的奇偶性
• 但无法改变字符在奇偶位置的整体分布

充分性证明

当奇偶位置字符分布相同时，总可以通过一系列翻转操作完成转换（构造性证明）。

复杂度分析

• 时间复杂度：$O(n + 26)$
  • 遍历两个字符串：$O(n)$
  • 检查26个字母的分布：$O(26)$
• 空间复杂度：$O(26)$