P10765 题解

· · 题解

题目大意

有一个 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

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

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

那为什么他们的结果都为 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;//完结撒花！ 
}