自动搬运

查看原文

来自洛谷，原作者为

	Clare613 csacademy.com||宣:https://www.luogu.com.cn/team/103922||250粉后橙名就别找我了||目标一：黄+绿+蓝+紫+黑->431/888||目标二：2025J：320+，2025S:250+||个人题库已满

搬运于2025-08-24 23:17:35，当前版本为作者最后更新于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;
}

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