BZOJ 3416 Take-out

发表于 | 更新于

Link

非常妙的做法啊。。

Solution

需要方案满足每次消除都不跨过已经消除的块，换句话说，就是消除的时候两块要么没有间隔，要么间隔>k+1>k+1，中间的k+1k+1块必须自行消除掉。 注意到保证有解，那就只要贪心地构造解，然后反向地输出，就可以得到答案啦

Tips

考虑构造的过程，如果正着走顾虑太多，就倒着来，使得每次的决策都是不得不做出的决策。 尝试这样的思路，可能有奇效。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include "lucida"
using std::vector;
const int MAXN=1000000+11;
int main() {
	freopen("input","r",stdin);
	static char s[MAXN];
	static int pref[MAXN],stack[MAXN],top;
	vector<int> Ans[MAXN];int ac=0;
	int n,K;is>>n>>K>>(s+1);
	for(int i=1;i<=n;++i) {
		pref[i]=pref[i-1]+(s[i]=='b'?1:-K);
		stack[++top]=i;
		if(top>=K+1 && pref[stack[top-K-1]]==pref[i]) {
			++ac;
			for(int j=1;j<=K+1;++j)
				Ans[ac].push_back(stack[top--]);
		}
	}
	for(int x=ac;x;--x) 
		for(int i=Ans[x].size()-1;~i;--i)
			os<<Ans[x][i]<<(i==0?'\n':' ');
	return 0;
}