Codeforces 950D(模拟)

Codeforces 950D
题意:最开始$n$个数字中的数字$i$在位置$2 \cdot i-1$,之后从右向左依次用数字将该列填充。最后$q$个$query$问你$pos$为$x_i$该填上什么数字。

可以发现奇数位的数字不会改变,然后只需要考虑偶数位是哪里移过来的。
考虑还原,当偶数位$x$的数被移动时,它的右边一定有$x / 2$个未移动的数,所以是从$x+x/2$移动过来的
如果当前还原操作位置已经是奇数,输出$(x+1)/2$

Codeforces Submission

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
#include<queue>
#include<cmath>
#include<set>
#include<iostream>
using namespace std;
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
#define pr pair<int, int>
#define fir first
#define sec second
#define mp make_pair
LL n, q;
void clean() {
}
int solve() {
clean();
while (q--) {
LL x;
cin >> x;
while (1) {
if (x & 1) {
cout << (x + 1) / 2 << endl;
break;
}
x += n - x / 2;
}
}
return 0;
}
int main() {
cin >> n >> q, solve();
return 0;
}

------ 本文结束 ------