题解：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$ ，这里需要特判。

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

代码实现

代码：

CPP

//洛谷 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)

。

题解：P14054 [SDCPC 2019] Sekiro

文章操作

题解：P14054 [SDCPC 2019] Sekiro

题目分析

代码实现

相关推荐

评论

题解：P14054 [SDCPC 2019] Sekiro