【BZOJ 1192】[HNOI2006]鬼谷子的钱袋

在这里输入题意

【题解】

设k为最大的正整数满足
$2^0+2^1+...+2^k2^0+2^1+...+2^k$
那么只用$2^0,2^1,...2^k$和$m-(2^0+2^1+...+2^k)$这k+2个数就能表示出0..m这m+1个数字了。
(原理自己想
(不过我还不是很明白那个$m-(2^0+2^1+...+2^k)$是否会和前面的2次方数字重复
(不过因为AC了,所以肯定是不会重复了。那么就记住这个结论吧。
如果m=...
那么只用$2^0,2^1,...2^k$这k+1个数字就能表示0..m这m+1个数字了。

【代码】

#include <bits/stdc++.h>

#define LL long long

#define rep1(i,a,b) for (int i = a;i <= b;i++)

#define rep2(i,a,b) for (int i = a;i >= b;i--)

#define all(x) x.begin(),x.end()

#define pb push_back

#define lson l,mid,rt<<1

#define rson mid+1,r,rt<<1|1

using namespace std;

const double pi = acos(-1);

const int dx[4] = {0,0,1,-1};

const int dy[4] = {1,-1,0,0};

int m;

int main(){

	#ifdef LOCAL_DEFINE

	    freopen("rush_in.txt", "r", stdin);

	#endif

    scanf("%d",&m);

    int now = 1;

    int cnt = 0;

    while (now<=m){

        cnt++;

        m-=now;

        now*=2;

    }

    if (m) cnt++;

    printf("%d\n",cnt);

	return 0;

}

巴特西

【BZOJ 1192】[HNOI2006]鬼谷子的钱袋

最新文章

热门文章