SGU 293 Game with Q and C：構造算法維護回文序列

問題描述

長度為 2n-1 的 01 序列，元素逐個揭示。每輪 (奇數時刻) 可交換任意兩位置元素一次。要求每個奇數時刻序列必須為回文。輸出每輪的交換操作 (至多兩次)。

構造策略

第 2i+1 輪 (已知 2i+1 個元素)，設 0 和 1 的個數為 s0, s1，必有一奇一偶。假設 s0 為奇數，則中間位置 (i+1) 放 0，其餘按 0101... 或 1010... 填充，不足則用另一字符補齊。證明從上一輪 (2i-1) 轉移只需至多兩次交換：

• 新增兩不同字符：中間點右移翻轉，可能需交換中間堆左側與右側元素。
• 新增兩相同字符：中間點右移不變，類似處理。

實現要點

• 用 bitset 表示當前目標序列與下一目標序列。
• 計算差異位置，配對 0→1 和 1→0 進行交換輸出。
• 每輪輸出兩行：交換次數與具體位置對。

參考程式碼 (C++)

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 4100;
int n; char src; bitset cur, nxt;
int s[2], len;

void add(char c) { s[c==src]++; cur[++len] = (c==src); }

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    cin >> n >> src;
    s[1] = 1; cur[1] = 1; len = 1;
    cout << "Qc\n0 0\n";
    for (int i=2, mid=2; i<=n; ++i, ++mid) {
        add(cin.get()); add(cin.get());
        for (int k=0;k<2;k++) {
            int ts[2] = {s[0], s[1]};
            bitset tmp;
            if (ts[0]&1) tmp[mid]=0, ts[0]--;
            else tmp[mid]=1, ts[1]--;
            for (int j=1, tk=k; j p[2];
        for (int j=1;j<=len;j++) if (nxt[j]!=cur[j]) p[cur[j]].push_back(j);
        for (int j=p[0].size(); j<2; ++j) cout << "0 0\n";
        for (int j=0;j