题解：Good Game

题目分析

问题核心

给定一个长度为 (N) 的由 'A' 和 'B' 组成的字符串，判断是否能通过一系列操作移除所有字符。每次操作可选择 2 或 3 个连续且相同的字符 移除，移除后剩余字符拼接重新编号。若可全部移除，输出操作序列；否则输出 (-1)。

关键观察

1. 字符分组：连续相同的字符可视为一个“块”。例如字符串 ABAABBBAA 可分为块序列 [A(1), B(1), A(2), B(3), A(2)]（括号内为块的长度）。设块的总数为 (n)，则问题转化为对这 (n) 个块的“合法消除”（块的消除依赖于相邻块的合并，本质是块序列的奇偶性与长度特性）。
2. 块的关键属性：定义 (a[i] = 1) 表示第 (i) 个块的长度 (>1)（可独立作为 2/3 个字符移除），(a[i] = 0) 表示块长度 (=1)（无法独立移除，需与相邻块合并）。
3. 可消除的充要条件：块序列需满足特定的奇偶性和“可合并性”，核心是避免出现无法配对消除的孤立单长度块。

数据范围挑战

• (N \leq 10^6)，需设计 (O(N)) 或 (O(n)) 复杂度算法（(n \leq N) 为块数），避免递归或暴力枚举。

算法设计

核心思路

1. 预处理：字符分组：将原始字符串按连续相同字符分组，得到块序列及属性数组 (a[i])（块长度是否 >1）。
2. 可行性判断（check 函数）：分两种情况判断块序列是否可全部消除：
   • 块数 (n) 为奇数：需存在一个“中心区域”，可通过合并消除所有块。
   • 块数 (n) 为偶数：通过并查集维护可合并的块区间，判断是否存在无法消除的“断点”。
3. 构造操作序列（solve 函数）：若可行，按块序列的结构（奇数/偶数块数），通过“对称合并”或“分段消除”构造操作，将块转化为 2/3 长度的连续字符并记录操作位置。
4. 操作序列转换：将块的消除操作映射回原始字符串的位置（利用块的起始编号），并拆分为 2/3 长度的具体操作。

具体步骤**

1. 预处理：字符分组

void read() {
    string s;
    cin >> n >> s;
    int cnt = 0;
    for (int i = 0; i < n; i++) {
        if (i == 0 || s[i] != s[i-1])
            pid[++cnt] = i + 1; // 块的起始位置（原始字符串编号，1-based）
        b[cnt]++; // 块的长度
    }
    swap(n, cnt); // n 变为块数
    for (int i = 1; i <= n; i++)
        a[i] = (b[i] > 1); // 块属性：长度>1 标记为1
}

• 输出：块数 (n)、块长度数组 (b)、块起始位置数组 (pid)、属性数组 (a)。

2. 可行性判断（check 函数）

情况 1：块数 (n) 为奇数

核心是存在一个“中心块”，其左右两侧的单长度块（(a[i]=0)）可通过合并消除：

• 找到最左和最右的“长块”（(a[i]=1)），记为 (l) 和 (r)。
• 若 (r - l - 1 \geq n/2)（中心区域足够大，可容纳所有单长度块的合并），则可行；否则不可行。

情况 2：块数 (n) 为偶数

需确保块序列无“断点”（即不存在无法合并消除的单长度块区间）：

• 用并查集合并相邻的单长度块（(a[i]=0) 且 (a[i+1]=0)），维护可合并区间的大小。
• 预处理前缀数组 (pre[i])：表示前 (i) 个块组成的前缀是否“可消除”。
• 预处理后缀数组 (suf[i])：表示后 (n-i+1) 个块组成的后缀是否“可消除”。
• 若存在某个位置 (i) 使得前缀 (pre[i]) 和后缀 (suf[i+1]) 均不可消除，则存在断点，不可行；否则可行。

3. 构造操作序列（solve 函数）

情况 1：块数 (n) 为奇数

以块序列的中心为基准，通过“对称合并”将单长度块与相邻长块合并，转化为可消除的 2/3 长度：

• 找到中心区域的左右边界 (l)（最左长块）和 (r)（最右长块）。
• 先处理中心右侧的块，再处理左侧的块，将合并后的块长度记录为操作对象。

情况 2：块数 (n) 为偶数

找到断点 (pmid)，将块序列分为左右两段（([1, pmid]) 和 ([pmid+1, n])），分别对两段调用 solve 函数构造操作。

4. 操作序列转换（out 函数）

将块的合并长度拆分为 2/3 的操作（优先用 2，剩余用 3，或反之），并映射回原始字符串的起始位置：

• 例如，合并后某块的长度为 5，可拆分为“2+3”或“3+2”，对应的操作是原始起始位置 + 长度 2 或 3。

代码关键模块解析

1. 并查集（FaC 类）

用于合并相邻的单长度块，维护可合并区间的大小，辅助可行性判断：

struct FaC {
    int fa[N], sz[N];
    void init() { for (int i=1; i<=n; i++) fa[i]=i, sz[i]=1; }
    int find(int x) { return fa[x]==x ? x : fa[x]=find(fa[x]); }
    void merge(int x, int y) { // 合并两个块
        x=find(x), y=find(y);
        if (x!=y) fa[y]=x, sz[x]+=sz[y];
    }
    int getsiz(int x) { return sz[find(x)]; } // 获取合并后的区间大小
};

2. 可行性判断（check 函数）

bool check() {
    if (n & 1) { // 块数为奇数
        int l=0, r=n+1;
        for (int i=1; i<=n/2+1; i++) if (a[i]) l=i; // 最左长块
        for (int i=n; i>=n/2+1; i--) if (a[i]) r=i; // 最右长块
        return (r-l-1 >= n/2); // 中心区域足够大
    } else { // 块数为偶数
        F.init();
        for (int i=1; i<=n; i++) {
            if (i>1 && a[i]==0 && a[i-1]==0) F.merge(i-1, i);
            if (i&1) pre[i] = (F.getsiz((1+i)/2) < i/2 || a[(1+i)/2]==1);
        }
        F.init();
        for (int i=n; i>=1; i--) {
            if (i<n && a[i]==0 && a[i+1]==0) F.merge(i+1, i);
            if ((n-i+1)&1) suf[i] = (F.getsiz((n+i)/2) < (n-i+1)/2 || a[(n+i)/2]==1);
        }
        for (int i=1; i<n; i++) if (i&1) {
            if (pre[i] && suf[i+1]) { pmid=i; return 0; } // 存在断点，不可行
        }
        return 1;
    }
}

• 奇数块数：通过左右长块的位置判断中心区域是否足够。
• 偶数块数：通过前缀/后缀数组判断是否存在断点，若存在则记录断点位置 (pmid)。

3. 操作构造（solve 函数）

以奇数块数为例，对称合并块并记录操作：

void solve(int ql, int qr) {
    int len=qr-ql+1, l=ql-1, r=qr+1, mid=(ql+qr)>>1;
    for (int i=ql; i<=mid; i++) if (a[i]) l=i; // 左长块
    for (int i=qr; i>=mid; i++) if (a[i]) r=i; // 右长块
    // 处理右侧块
    for (int c=0; c<mid-l; c++) {
        if (c==0) ans.pb(mp(b[r], pid[r]));
        else ans.pb(mp(b[r-c]+b[r+c], pid[r-c]));
    }
    // 合并块，更新长度
    int fl=r-(mid-l), fr=r+(mid-l), j=l;
    if (l!=mid) b[fr] += b[fl];
    // 处理左侧块
    for (int c=0; c<l-ql+1; c++) {
        if (c==0) ans.pb(mp(b[l], pid[l]));
        else ans.pb(mp(b[l-c]+b[j], pid[l-c]));
        j++;
        if (l!=mid && j==fl) j=fr;
    }
}

• 核心：将单长度块与相邻长块合并，转化为可消除的长度（≥2），并记录合并后的块长度和原始起始位置。

4. 操作转换（out 函数）

将合并后的块长度拆分为 2/3 的操作：

void out() {
    for (pii p : ans) {
        int id=p.sec, w=p.fir;
        while (w) {
            if (w&1) pans.pb(mp(3, id)), w-=3; // 奇数剩余用3
            else pans.pb(mp(2, id)), w-=2; // 偶数用2
        }
    }
    cout << pans.size() << '\n';
    for (pii p : pans) cout << p.sec << ' ' << p.fir << '\n';
}

• 例如，长度 5 拆分为 2+3，长度 4 拆分为 2+2，长度 3 直接输出。

时间复杂度与空间复杂度

• 时间复杂度：(O(N))。字符分组为 (O(N))，可行性判断和操作构造均为 (O(n))（(n \leq N)），操作转换为 (O(K))（(K) 为操作次数，(K \leq N)）。
• 空间复杂度：(O(N))。存储块信息、并查集、操作序列等数组，均为线性空间。

关键结论

1. 块序列转化：将原始字符串转化为块序列，将问题简化为块的合并与消除，大幅降低复杂度。
2. 奇偶性判断：块数的奇偶性决定了判断逻辑，奇数块数依赖中心区域，偶数块数依赖断点检测。
3. 操作构造技巧：通过对称合并和分段处理，确保所有块都能转化为 2/3 长度的可消除单元，同时映射回原始位置保证操作的正确性。