题解：P12707 [KOI 2021 Round 1] 橡皮擦

Clare613 · 2025-06-06 22:32:46 · 题解

纯模拟就可以过这道题，用两个队列，一个队列用来存储剩余的数字，另一个用于存储该轮消了后还剩哪些数，于是便有了第一种解法：

#include<bits/stdc++.h>
#define int long long
using namespace std;

signed main(){
    cin.tie(0)->sync_with_stdio(0);
    queue<int> q;
    int x;
    cin>>x;
    for(int i=1;i<=x;i++){
        q.push(i);
    }
    while(!q.empty()){
        if(q.size()==1){
            break;
        }
        queue<int> w;
        while(!q.empty()){
            q.pop();
            if(!q.empty()){
                w.push(q.front());
                q.pop();
            }
        }
        swap(q,w);
    }
    cout<<q.front();
    return 0;
}

接下来给出第二种解法，我们可以发现，每一次减就相当于删掉奇数后剩余数除以 2，那么答案就是在 n 以内的 2 的最大幂，这样可以缩短代码：

#include<iostream>
#include<algorithm>
using namespace std;
int poow[8];
int main(){
    cin.tie(0)->sync_with_stdio(0);
    int x;
    cin>>x;
    poow[0]=1;
    for(int i=1;i<=7;i++){
        poow[i]=poow[i-1]*2;
    }
    cout<<poow[upper_bound(poow,poow+7+1,x)-poow-1];
    return 0;
}

不知道还有没有题解也写了两种解法。