题解：AT_abc469_c [ABC469C] Cantrip

LBXJLXR · 2026-08-04 13:25:41 · 题解

前言

气死我了赛时没有切，后来才恍然大悟，写篇题解玩玩

思路

注意到高桥手里初始会有 k 次机会（题目要求先把前 k 个袋子取玩）。考虑接下来的情况

• 高桥拿到带有 o 的袋子，那么高桥还可以抽，手中仍然有 k 次机会。

• 高桥抽到了带有 x 的袋子，那么高桥就减少了一次机会，目前还剩 k-1 次机会。

注意力时刻

注意到要让他停止抽签，就得让他抽到 k 个 x，因此我们就可以预处理出第一个 x，第二个 x，\dots，第 n 个 x 的位置。

但是！

当 x 的总个数不够消耗时，全部取完。

AC code

#include<bits/stdc++.h>
using namespace std;
const int MAXN=8e5+10;
int pos[MAXN];
string str;
int n;

int main(){
    cin>>n>>str;
    str=' '+str;
    int last=0;
    for(int i=1;i<=n;++i)
        pos[i]=n; //x 不够取的情况，先初始化
    for(int i=1;i<=str.size();++i){
        if(str[i]=='x'){
            pos[++last]=i;
        }
    }
    for(int k=1;k<=n;++k)
        printf("%d\n",pos[k]);
    return 0;
} 

题解不易，祝所有点赞的同学们 AK 每一场比赛！谢谢啦！qwq

The End