题解：P3551 [POI 2013] USU-Take-out

· · 题解

题目传送门

欢迎来博客园阅读！

题意

每次消除 k+1 个砖，其中 k 块白色，1 块黑色，并且这 k+1 块砖从开始到结束，中间不能路过已经消除过的砖。

思路

对照样例，不难想到了一点：如果某连续的一段是可消除的，则可以将这一段放到最后再消除。

这是样例输出：

1 8 12
2 6 7
3 4 5
9 10 11

图示：

最后两步消除的部分都是连续段。由此或许可以看出一些性质？

我们考虑递归：

  1. 对于一个可以消除的连续子段，我们将它放在最后消除显然是可行的。
  2. 考虑时光倒流，消除了这个连续子段后将其直接丢掉，这样导致的结果就是会出现新的可以消除的连续子段，我们再将其放在序列中上一次的消除操作的前一次操作，这样就恰好可以满足条件了。

这么看来，我们的操作序列就是一个栈，同时我们可以在输入的过程中也实现一个栈，以便于我们的删除操作。

考虑满足什么条件的连续子段可以消除：k 块白色，1 块黑色。也就是 k+1 块砖之中只有一块黑色或有 k 块白色。于是考虑维护一个前缀和数组，记录前缀白色砖或黑色砖的块数（我的代码实现中是记录的黑色砖个数）。

整理一下，在删除的时候需要满足以下几个条件：

  1. 是连续段。
  2. 恰有 1 块黑色砖（或恰有 k 块白色砖）。

于是这个题做完了。

代码实现

#include <bits/stdc++.h>
#define loop(i,a,b) for(int i=(a);i<=(int)(b);i++)
#define rloop(i,a,b) for(int i=(a);i>=(int)(b);i--)
using namespace std;
typedef long long ll;
const int N=1e6+5;
const int mod=1e9+7;
const int inf=0x3f3f3f3f;
int n,k,sum[N];
char c;
stack<int>st,ans;
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n>>k;
    loop(i,1,n){
        cin>>c;
        st.push(i);
        int s=st.size();
        sum[s]=sum[s-1]+(int)(c=='c');
        if(s>=k+1&&sum[s]-sum[s-k-1]==1){
            rloop(j,s,s-k)ans.push(st.top()),st.pop();
        }
    }
    int T=0;
    while(!ans.empty()){
        cout<<ans.top()<<' ';
        ans.pop();
        T=(T+1)%(k+1);
        if(!T)cout<<'\n';
    }
    return 0;
}

完结撒花花！