题解：P12592 重生有惊喜

zyrqwq · 2025-05-24 18:24:35 · 题解

题目分析

本题要求判断给定字符串是否可以通过任意次交换操作变成一个回文串。 关键在于理解回文串的性质：对于一个回文串，每个字符出现的次数必须满足以下条件：

• 如果字符串长度为偶数，每个字符出现的次数必须是偶数。
• 如果字符串长度为奇数，恰好有一个字符出现奇数次，其余字符出现偶数次。

  解题思路

  我们可以通过统计每个字符的出现次数，并检查奇数次出现的字符数量来解决这个问题：

• 统计每个字符的出现次数。
• 计算出现奇数次的字符数量。
• 如果奇数次字符的数量不超过 1，则可以通过交换操作形成回文串，否则不能。

  代码

  #include <bits/stdc++.h>
  #define nailong 114514
  using namespace std;
  int t;int a[26];
  bool f(string s) {
  memset (a, 0, sizeof(a));
  for (char d : s) a[d - 'a']++;
  int c = 0;
  for (int i = 0; i < 26; i++) if (a[i] % 2) c++;
  return c <= 1;
  }
  int main() {
  cin>>t;
  cin.ignore();
  while (t--) {
      string s;
      cin >> s;
      cout << (f(s) ? "Yes" : "No")<<endl;
  }
  return 0;
  }