[POI2013]USU-Take-out 题解

传送门

POI的题都好神仙啊。

题意：

​ 有n块砖，其中白色是黑色的k倍，求一个消除序列，满足以下条件：每次消除k+1个砖，其中k块白色，1块黑色，并且这k+1块砖从开始到结束，中间不能路过已经消除过的砖。要求你输出方案，数据保证有解。

输入输出格式：

输入：

​ 输入两行，第一行两个整数，$1<n<10^6$ 和 $0<k<n$，第二行有一个长度为 $n$ 的字符串，其中只有’c’和’b’两种字符，’c’代表黑砖，’b’代表白砖。保证$k+1|n$

输出：

​ 输出 $\frac{n}{k+1}$ 行，每行 $k+1$ 个整数，第$i$行的整数表示第$i$次取砖块的位置。

思路：

​ 一开始的想法是分治，就是从中间随便掏出符合要求的一段，之后再去做两边的，倒序输出。但很快发现这个方法不行，首先是时间受不了，其次是在中间先取相当于把两边断开，破坏了很多可行的方法。

​ 对于断开序列的问题可以这样解决：把每次找到的砖删掉，再重新跑一遍，直到删光。那就是一个 $N^2$ 的枚举了，跟分治差不多快但至少正确。

​ 手动模拟一下这个过程，发现我们做了很多无用功，比如循环要删除砖块前面那些砖块被循环了多次。而开一个栈可以很好的解决这个问题，当栈顶有$k+1$个元素并只有一个’c’是，将他们全部弹出储存到输出中即可。

代码：

#include<cstdio>
#include<iostream>
using namespace std;
char a[1000001];
int n,top,sum[1000001],stack[1000001];
int k,cnt,ans[1000001];
int main(){
    scanf("%d%d%s",&n,&k,a+1);
    for (int i=1; i<=n; i++){
        stack[++top]=i;
        sum[top]=sum[top-1]+(a[i]=='c');
        if (top>=k+1&&sum[top]-sum[top-k-1]==1){
            for (int j=top; j>=top-k; j--){
                ans[++cnt]=stack[j];
            }
            top=top-k-1;
        }
    }
    for (int i=n; i>=1; i--){
        printf("%d ",ans[i]);
        if (i%(k+1)==1) puts("");
    }
    return 0;
}