题目理解

我们有一个长度为 n 的字符串，由字符 'b'（白色）和 'c'（黑色）组成，其中白色积木数量是黑色积木数量的 k 倍。每次操作需要移除连续的 k+1 个积木，其中恰好包含 k 个白色和 1 个黑色。

关键限制：移除的积木必须是连续的（中间不能有已经被移除的积木留下的空隙）。

解题思路

核心观察

题目保证有解，我们需要找到一个合法的移除顺序。由于移除操作必须是连续的块，这提示我们可以使用栈来模拟移除过程。

算法思想

1. 从左到右扫描积木，维护一个栈来记录当前还未被移除的积木编号
2. 维护前缀和：记录栈中每个位置的白色和黑色积木计数
3. 检查移除条件：当栈的大小 ≥ k+1 时，检查栈顶的 k+1 个积木：
   • 如果这 k+1 个积木中恰好有 1 个黑色和 k 个白色
   • 那么这就是一个合法的操作，可以将这 k+1 个积木移除
4. 逆序输出：由于移除操作可能有依赖关系，需要从后往前输出操作序列

代码详解

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
#include <string>
using namespace std;

const int N = 1e6 + 10;
int st[N], tp;  // 栈和栈顶指针
vector<int> ans[N];  // 存储每个操作移除的积木编号
int cntb[N], cntc[N];  // 栈中前缀和：cntb[i]表示栈中前i个积木的白色数量，cntc[i]表示黑色数量

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    int n, k;
    cin >> n >> k;
    string s;
    cin >> s;
    s = " " + s;  // 让字符串下标从1开始
    int fin = 0;   // 记录操作数量

    for (int i = 1; i <= n; i++) {
        // 将当前积木压入栈中
        st[++tp] = i;
        
        // 更新前缀和
        cntc[tp] = cntc[tp - 1];
        cntb[tp] = cntb[tp - 1];
        
        if (s[i] == 'c')
            cntc[tp]++;  // 黑色积木计数
        else
            cntb[tp]++;  // 白色积木计数

        // 检查是否可以移除栈顶的k+1个积木
        if (tp > k && 
            cntc[tp] - cntc[tp - k - 1] == 1 &&  // 栈顶k+1个积木中恰好有1个黑色
            cntb[tp] - cntb[tp - k - 1] == k) {  // 栈顶k+1个积木中恰好有k个白色
            
            fin++;  // 新增一个操作
            
            // 记录这个操作移除的积木编号
            for (int j = tp - k; j <= tp; j++)
                ans[fin].emplace_back(st[j]);
            
            // 从栈中移除这k+1个积木
            tp -= (k + 1);
        }
    }

    // 逆序输出操作序列
    for (int i = fin; i >= 1; i--) {
        for (auto j : ans[i])
            cout << j << " ";
        cout << "\n";
    }

    return 0;
}

关键点解释

1. 为什么使用栈？

• 栈天然保持了积木的原始顺序
• 移除操作总是发生在栈顶，符合"连续无空隙"的要求
• 栈的LIFO特性与移除操作的嵌套关系相吻合

2. 前缀和的作用

cntc[tp] - cntc[tp - k - 1] == 1  // 检查黑色数量
cntb[tp] - cntb[tp - k - 1] == k  // 检查白色数量

这通过前缀和差值快速判断栈顶 k+1 个积木的颜色分布是否符合要求。

3. 为什么需要逆序输出？

考虑操作之间的依赖关系：

• 后执行的操作可能依赖于先执行的操作创造的"连续"条件
• 栈的移除顺序是从内层到外层，但实际执行需要从外层到内层
• 逆序输出保证了操作序列的合法性

示例分析

以样例为例：

输入: n=12, k=2, s="ccbcbbbbbbcb"

执行过程：

1. 扫描到位置8时，栈顶3个积木满足条件(1黑2白)，记录操作并移除
2. 继续扫描，在适当位置发现其他满足条件的连续块
3. 最终得到4个操作，逆序输出

复杂度分析

• 时间复杂度：O(n)，每个积木入栈出栈各一次
• 空间复杂度：O(n)，用于存储栈和答案

学习要点

1. 栈的巧妙应用：用栈维护连续段，处理嵌套的移除操作
2. 前缀和优化：快速判断区间内的颜色数量
3. 逆序思维：存储顺序与输出顺序相反，解决操作依赖问题
4. 贪心思想：一旦发现合法的连续块就立即移除，保证解的构造

这种解法充分利用了题目保证有解的条件，通过简单的栈操作就能构造出合法的操作序列。