hdu 5747 Aaronson (BestCoder Round #84 1001)

本文主要是介绍hdu 5747 Aaronson (BestCoder Round #84 1001)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

至今不懂官方题解是什么意思：答案就是popcount(n)-popcount(\lfloor \frac{n}{2^m} \rfloor) + \lfloor \frac{n}{2^m} \rfloorpopcount(n)−popcount(⌊​2​m​​​​n​​⌋)+⌊​2​m​​​​n​​⌋.

rfloor

popcount是数出一个二进制数中有几个1，如0110就是2

用贪心过得比较多：

#include <iostream>
#include <cstdio>
using namespace std;
typedef long long ll;ll mypow(ll x,ll n){ll res = 1;while(n){if(1 & n) res = res *x;x = x*x;n >>= 1;}return res;
}
ll _2pow[31];
void initial(){for(int i=0;i <=30;i++)_2pow[i] = mypow(2,i);
}
int main()
{initial();//freopen("in.txt","r",stdin);int n,m,t;scanf("%d",&t);while(t--){scanf("%d%d",&n,&m);int ans =  0;m = m >= 31?30:m;for(int i = m;i>=0 && n;i--){if( n >= _2pow[i]){int xi = n / _2pow[i];n = n - (xi *_2pow[i]);ans += xi;}}printf("%d\n",ans);}return 0;
}/*题解的做法..着实想不到，后来敲了一遍
//自己写的，比较挫..
#include <iostream>
#include <cstdio>
using namespace std;
typedef long long ll;ll mypow(ll x,ll n){ll res = 1;while(n){if(1 & n) res = res *x;x = x*x;n >>= 1;}return res;
}
int popcout(ll num){int cnt = 0;while (num){if(num & 1) cnt++;num >>= 1;}return cnt;
}
int main()
{int n,m;int t;scanf("%d",&t);while(t--){scanf("%d%d",&n,&m);if(m>31)m=30;ll A = popcout(n);ll B = popcout(n/mypow(2,m));ll C = (ll)n/mypow(2,m);printf("%I64d\n", A - B + C);}return 0;
}*/

popcount(n)-popcount(\lfloor \frac{n}{2^m} \rfloor) + \lfloo

这篇关于hdu 5747 Aaronson (BestCoder Round #84 1001)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---