题解：CF949B A Leapfrog in the Array

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

首先我们发现整个过程都没有什么规律非常的烦人，但是我们可以模拟一下这个过程，发现每次填第

i

个空格的时候，这后面正好是一连串的连续数字，而且数字个数就是

n-i

。

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

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

O(\log n)

的。

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

CPP

#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";
}

题解：CF949B A Leapfrog in the Array

文章操作

相关推荐

评论

题解：CF949B A Leapfrog in the Array