M - Sekiro

基本信息

题目出处	2019 山东省大学生程序设计竞赛
队伍通过率	291/307 (94.8%)

题解

题目求的是 $n$ 连续进行 $k$ 次除以 $2$ 上取整的结果。

如果 $n=0$，显然答案就是 $0$。否则 $n$ 将在 $\mathcal{O}(\log n)$ 次操作之后变成 $1$，因此最多只要模拟 $\mathcal{O}(\log n)$ 次操作即可。

复杂度 $\mathcal{O}(\log n)$。

参考代码

#include <bits/stdc++.h>
using namespace std;

void solve() {
    int n, K; scanf("%d%d", &n, &K);
    if (n == 0) printf("0\n");
    else {
        while (K > 0 && n > 1) K--, n = (n + 1) / 2;
        printf("%d\n", n);
    }
}

int main() {
    int tcase; scanf("%d", &tcase);
    while (tcase--) solve();
    return 0;
}