AT_abc469_d Cantrip 题解

AT_abc469_d Cantrip 题解

洛谷链接

发现

考虑每一个子问题。

令x i x_ixi​表示前i ii个袋子中标有“命中”的袋子数量。

显然，高桥手中目前有x i x_ixi​个袋子。

对于每一个袋子，分为两种情况：

• 若这个袋子标有“命中”，则手中袋子数量不变，吃掉一块糖。
• 若这个袋子标有“未中”，则手中袋子少一个，吃掉一块糖。

显然，高桥最多可以吃掉x i x_ixi​个标有“未中”的袋子中的糖，此时高桥手中没有袋子，无法继续。

分析

考虑倒序枚举。

我们要做的，就是找到第i ii个袋子之后的第x i x_ixi​个标有“未中”的袋子。

即找到第一个袋子k kk，使得x k ≥ i x_k\ge ixk​≥i。

此时进行分类讨论：

• 如果x i = i x_i=ixi​=i或者x i + 1 > i x_{i+1}>ixi+1​>i，那么高桥无法吃掉任何其他糖。
• 否则，找到第一个k kk使得x k = i x_k=ixk​=i。

代码实现

#include<bits/stdc++.h>usingnamespacestd;intn;into[800010];intx[800010];unordered_map<int,int>f;string s;stack<int>ans;intmain(){cin.tie(0)->sync_with_stdio(false);cin>>n>>s;s=' '+s;for(inti=1;i<=n;i++){o[i]=o[i-1]+(s[i]=='o');x[i]=x[i-1]+(s[i]=='x');}for(inti=n;i>=1;i--){if(x[i]==i||x[i+1]>o[i]+x[i]){ans.push(i);continue;}intpos=f[o[i]+x[i]];if(pos==0)pos=n;ans.push(pos);f[x[i]]=i;}while(!ans.empty()){cout<<ans.top()<<'\n';ans.pop();}return0;}

by lonys