自动搬运

查看原文

来自洛谷，原作者为

	RainBow_doge 醒了

搬运于2025-08-24 23:01:01，当前版本为作者最后更新于2024-07-13 19:10:09，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

题目大意

有一个 $1\sim n$ 的序列，共有 $k$ 次操作，$1$ 操作指将下标为奇数的数字删除，$2$ 操作指将下标为偶数的数字删除，最后输出删除后的最后一个数字。

分析

看到数据范围为 $1\le n\le10 ^{18}$，知道肯定不能开数组暴力过，那就开始找规律：

首先我们要明白最后得出的数字到底在哪个位置。

我们可以举几个例子

$8$ $3$ $2$ $2$ $2$

1 2 3 4 5 6 7 8
(1)1 3 5 7
(2)1 5
(3)1

$7$ $3$ $2$ $2$ $2$

1 2 3 4 5 6 7
(1)1 3 5 7
(2)1 5
(3)1

$11$ $4$ $2$ $2$ $2$ $2$

1 2 3 4 5 6 7 8 9 10 11
(1)1 3 5 7 9 11
(2)1 5 9 11
(3)1 9
(4)1

这些得数有什么共同点吗?

• 他们都只进行了 $2$ 操作。

• 他们得数都为 $1$。

• 每进行一次 $2$ 操作，相邻两数间的差值就会变大，且每次变大后的差值为变化前相邻两数差值的 $2$ 倍。

即第 $i$ 次操作，两数间的差值为 $2^i$。

那为什么他们的结果都为 $1$ 呢?

我们可以思考一下:

$2$ 操作每次是把偶数位删除，因此每次操作基本所有数字都会转移位置，但有一个数除外，即 $1$ 号位置上的数，他的前面没有数字了，因此他并不会向前补，并且因为他是奇数点，所以他不会被删除，那么他的位置就不会发生变化。

因为一号位置上的数的位置不会改变，而且 $2$ 操作并不会删除奇数点，所以一号位置上的数字在 $2$ 操作下将一定不会被删去，所以一号位置上的数一定为结果。

那我们就能得出：真正的结果不是 $1$，而是 $1$ 号位置上的数。

因此我们在代码中若遇见 $2$ 操作，只用更改两点之间的差值，而不用考虑结果。

if(x==2){//x为操作编号
  cnt*=2;//cnt为两点之间的差值
}

那说了这么久的 $2$ 操作，$1$ 操作要怎么办呢？

我们再举几个例子

我们在原有 $2$ 操作中插入几个 $1$ 操作。

$7$ $3$ $1$ $2$ $2$

1 2 3 4 5 6 7
(1)2 4 6
(2)2 6
(3)2

$8$ $3$ $1$ $1$ $2$

1 2 3 4 5 6 7 8
(1)2 4 6 8
(2)4 8
(3)4

貌似看不出什么共同点，但我们可以联系上面的 $2$ 操作。

我们发现，尽管 $1$ 操作将第一个位置上的数删除了，但第一个位置的数后面的一个数成为了第一个位置上的数，也就是将第二个数作为了答案。

那第二个数要如何求得呢？

这时候我们就用到了操作 $2$ 中求到的差值了，因为求的差值为相邻两数之间的差，那么第二个数就可以理解为第一个数加上差值。

而且 $1$ 操作因为跳着删除了一些数字，所以他也需要与 $2$ 操作一样变更差值，差值也是一样变成 $2^i$。

综上所述，$1$ 操作就比 $2$ 操作多了一步要更改第一个位置上的数的值，那么 $1$ 操作就可以变为 $2$ 操作，只不过要更改一下答案。

代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long//10^18一定要开long long 
int main(){
	int t;
	cin>>t;
	while(t--){
		ll n,k;
		cin>>n>>k;
		ll first=1;//first为第一个位置上的数，也就是本题的答案 
		ll cnt=1;//cnt为相邻两数的差值，一开始为1 
		for(int i=1;i<=k;i++){
			int x;
			cin>>x;
			if(x==1){
				first+=cnt;//执行1操作后第一个数变为第二个数，也就是原firt加上差值 
				cnt*=2;//重新更新两数差值 
			}
			if(x==2)
				cnt*=2;//只需要更新两数的差值 
		}
		cout<<first<<endl;//第一个位置的数一定是最后一个数，也就是答案
	}
	return 0;//完结撒花！ 
}