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_iixii或者x i 1 i x_{i1}ixi1i那么高桥无法吃掉任何其他糖。否则找到第一个k kk使得x k i x_kixki。代码实现#includebits/stdc.husingnamespacestd;intn;into[800010];intx[800010];unordered_mapint,intf;string s;stackintans;intmain(){cin.tie(0)-sync_with_stdio(false);cinns;s s;for(inti1;in;i){o[i]o[i-1](s[i]o);x[i]x[i-1](s[i]x);}for(intin;i1;i--){if(x[i]i||x[i1]o[i]x[i]){ans.push(i);continue;}intposf[o[i]x[i]];if(pos0)posn;ans.push(pos);f[x[i]]i;}while(!ans.empty()){coutans.top()\n;ans.pop();}return0;}by lonys
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_iixii或者x i 1 i x_{i1}ixi1i那么高桥无法吃掉任何其他糖。否则找到第一个k kk使得x k i x_kixki。代码实现#includebits/stdc.husingnamespacestd;intn;into[800010];intx[800010];unordered_mapint,intf;string s;stackintans;intmain(){cin.tie(0)-sync_with_stdio(false);cinns;s s;for(inti1;in;i){o[i]o[i-1](s[i]o);x[i]x[i-1](s[i]x);}for(intin;i1;i--){if(x[i]i||x[i1]o[i]x[i]){ans.push(i);continue;}intposf[o[i]x[i]];if(pos0)posn;ans.push(pos);f[x[i]]i;}while(!ans.empty()){coutans.top()\n;ans.pop();}return0;}by lonys
