P11190 「KDOI-10」反回文串 题解

· · 题解

P11190 「KDOI-10」反回文串

两个特殊性质已经把做法塞你嘴里了。

考虑 A 性质。

如果 2 \mid n，这时是可以将颜色不同的两两配对上的。考虑将原序列重排，使颜色相同的放在一起，此时把 (i, i + \frac n 2) 分进一个子序列是可行的（经典思路，因为不存在绝对众数，而颜色相同的是连续的，所以他们颜色不同）。答案最优为 \frac n 2。

如果 2 \nmid n，把多出来的 n 加进 (1, 1 + \lfloor \frac n 2 \rfloor) 里面就行了，原因同上。答案最优为 \lfloor \frac n 2 \rfloor。

考虑 B 性质。

这意味着至少有一种颜色数量达到了 \lceil \frac n 2 \rceil，称这种颜色为 X，另一种颜色为 Y。

显然的是分出来的每个子序列都至少有一个 Y，所以所有颜色相同时无解。

当 Y 只有一个时，只能将所有的分在一起。如果此时 2 \nmid n 并且 s _ {\lfloor \frac n 2 \rfloor}（即正中心）为 Y 时，它本身就是一个形如 ...XXXYXXX... 的回文，无解；否则必然不回文，答案为 1。

当 Y 有两个时。设第一个 Y 的位置为 l，最后一个 Y 的位置为 r。把 [l + 1, n] 中的 X 分给 l，[1, l - 1] 中的 X 分给 r。如果分下来有个 Y 没有 X 的话注意从另一个里面分过来一个。这样会得到形如 YXXX... 和 ...XXXY 的东西。答案最优为 2。

当 Y 更多时，延续上面的思路。[l + 1, r - 1] 之间的 Y 没有 X，从 l 或 r 的里面分过来一个就行了。这样会得到形如 YXXX...， ...XXXY 和一大堆 XY，YX。答案最优为 Y 的数量。

考虑正解。

不存在绝对众数时，用 A 性质做法；否则将绝对众数当成 X，其他颜色当成 Y，用 B 性质做法。

就做完了，时间复杂度是线性，根据实现可能会带点别的什么东西。

#include <bits/stdc++.h>
#define F(i, a, b) for(int i = (a); i <= (b); ++i)
#define dF(i, a, b) for(int i = (a); i >= (b); --i)

using namespace std;
typedef long long LL;
typedef unsigned long long ull;
typedef unsigned uint;
typedef pair<int, int> pii;
const int N = 1e5 + 5;

int n, t[140], zyq; char s[N];
int p[N]; vector<int> qu[140];
int cnt; vector<int> ans[N];
void mian() {
  cin >> n, zyq = -1, cnt = 0;
  F(i, 'a', 'z') t[i] = 0, qu[i].clear();
  F(i, 1, n) cin >> s[i], ++t[s[i]];
  F(i, 'a', 'z') if (t[i] >= n + 1 >> 1) zyq = i;
  if (zyq < 0) {
    F(i, 1, n) qu[s[i]].push_back(i);
    cnt = n >> 1; int tot = 0;
    F(i, 'a', 'z') for (auto it : qu[i]) p[++tot] = it;
    F(i, 1, n >> 1) ans[i].push_back(p[i]), ans[i].push_back(p[i + (n >> 1)]);
    if (n & 1) ans[1].push_back(p[n]);
  }
  else {
    if (t[zyq] == n) { return cout << "Shuiniao\n", void(); }
    if (t[zyq] == n - 1) {
      if ((n & 1) && s[n + 1 >> 1] != zyq)
        { return cout << "Shuiniao\n", void(); }
      cout << "Huoyu\n1\n" << n << " ";
      F(i, 1, n) cout << i << " ";
      return cout << "\n", void();
    }
    int l, r; cnt = 2;
    F(i, 1, n) if (s[i] != zyq) { l = i; break; }
    dF(i, n, 1) if (s[i] != zyq) { r = i; break; }
    ans[1].push_back(l), ans[2].push_back(r);
    F(i, l + 1, n) if (s[i] == zyq) ans[1].push_back(i);
    F(i, 1, l - 1) if (s[i] == zyq) ans[2].push_back(i);
    F(i, l + 1, r - 1) if (s[i] != zyq) ans[++cnt].push_back(i);
    F(i, 1, cnt) if (ans[i].size() < 2)
      if (ans[1].size() > 2) ans[i].push_back(ans[1].back()), ans[1].pop_back();
      else ans[i].push_back(ans[2].back()), ans[2].pop_back();
  }
  cout << "Huoyu\n" << cnt << "\n";
  F(i, 1, cnt) {
    cout << ans[i].size() << " ";
    sort(ans[i].begin(), ans[i].end());
    for (auto it : ans[i]) cout << it << " ";
    cout << "\n", ans[i].clear();
  }
}

int main() {
//   freopen("zyq.in", "r", stdin);
//   freopen("zyq.out", "w", stdout);
  ios::sync_with_stdio(0);
  cin.tie(0), cout.tie(0);
  int c, _; cin >> c >> _; while (_--) mian();
  return 0;
}