题解：P14054 [SDCPC 2019] Sekiro

AW_BCH · 2025-09-17 20:28:31 · 题解

题解：P14054 [SDCPC 2019] Sekiro

题目传送门

更好的阅读体验

题目分析

通过简单的计算，可以发现最后的答案是 \left\lceil \frac{n}{2^k} \right\rceil。

考虑暴力，但是暴力的时间复杂度是 O(T\times K)，毫无疑问会超时，怎么办呢？

这时候，聪明的你发现当 k 很大时（比如 k>\log_2(n) 时），值会稳定在 1。也就是说，当 k 足够大时，结果就是 1。

因为 n 的取值范围 1\le n\le 10^9\le 10^{15}\approx 2^{50}，所以我们可以将每次输入分成几种情况讨论：

• 当 k\le 50 时，暴力求出答案。

• 当 k>50 时，直接输出 1。

• 注意，当 n=0 时，无论 k 是多少，结果都是 0，这里需要特判。

接下来的代码就很简单了。

代码实现

代码：

//洛谷 P14054 [SDCPC 2019] Sekiro 
#include<bits/stdc++.h>
using namespace std;
//#define LOCAL//
#define emdl '\n'
typedef long long ll;
typedef unsigned long long ull;
const int MAXN=1+5;

int n,k;

int main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    #ifdef LOCAL
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
    #endif

    int t;
    cin>>t;
    while(t--){
        cin>>n>>k;

        //特判 n=0 
        if(n==0){
            cout<<"0"<<emdl;
            continue;
        }

        //贪心 
        if(k>50){
            cout<<"1"<<emdl;
            continue;
        }
        //暴力求出答案 
        int x=n;
        for(int i=1;i<=k;i++){
            x=(x+1)/2;
        } 
        cout<<x<<emdl;
    }

    return 0;
}

时间复杂度 O(T\times K)，因为 k 最大为 50，所以时间复杂度为 O(T)。