题解：CF949B A Leapfrog in the Array

Drind · 2024-12-06 14:57:59 · 题解

duel 做到了，发现好难，不会做！

首先我们发现整个过程都没有什么规律非常的烦人，但是我们可以模拟一下这个过程，发现每次填第 i 个空格的时候，这后面正好是一连串的连续数字，而且数字个数就是 n-i。

而且我们还知道一个当下有数字的位置，今后再也不会被别的数字占领。

所以考虑倒着做，因为我们知道这个空格是从哪个位置的数字跳过来的（因为我们知道后面有多少连续数字，肯定是连续数字最后一个跳过来了），所以可以往后跳，直接模拟这个过程即可。因为每次距离结尾的距离减半，所以单次查询复杂度是对数 O(\log n) 的。

注意如果跳到某个奇数位置（即初始时有值的位置）时，直接结束，输出答案。

#include<bits/stdc++.h>
#define int long long
using namespace std;
bool Mbe;
const int N=2e5+10;
inline int _abs(int x){if(x>0) return x;return -x;}

void fake_main(){
    int n,q; cin>>n>>q;
    for(int i=1;i<=q;i++){
        int tmp; cin>>tmp;
        while(1){
            if(tmp%2==1){//奇数位置！直接输出答案
                cout<<(tmp+1)/2<<"\n";
                break;
            }

            int back=n-tmp/2;//算一下后面有多少数字
            tmp+=back;//往后跳
        }
    }
}

bool Med;
signed main(){
    ios::sync_with_stdio(false);
    cerr<<fabs(&Med-&Mbe)/1048576.0<<"MB\n";
    int t; t=1;
    while(t--) fake_main();
    cerr<<"\n"<<clock()*1.0/CLOCKS_PER_SEC*1000<<"ms\n";
}