AT5337 [ABC153D] Caracal vs Monster

题目描述

打怪,怪会分成两个,打到1的时候就没了

原先这篇题解有点复杂啊……

思路

看看样例,发现了什么不得了的事

答案很简单,就是2的第一个比h大的次幂减1

但为什么呢?

可给出一种直观的解释,你可以把它分裂的过程看做一棵二叉树,二叉树的节点数就是要攻击的次数了

这个D题比C题简单多了,居然直接递归都可过……

代码

1
2
3
4
5
6
7
8
9
#include<bits/stdc++.h>
using namespace std;
unsigned long long p,cnt=1;
int main(){
cin>>p;
while(p>=cnt) cnt<<=1;//求2的第一个比h大的次幂
cout<<cnt-1;
return 0;
}