题解分享:HRBUST 1132 水数
题目描述
题目描述 点我展开
Description
元帅得到的反馈信心很少,原来元帅了解到,大家都不愿意做水题,可是元帅自己就是一个水题王啊,前前后后水题水了300多道,水题王现在看看大家是个什么水的级别,决定在模拟一个水题吧。
如果一个正整数m表示成二进制,它的位数为n(不包含前导0),称它为一个n二进制数。所有的n二进制数中,1的总个数被称为n对应的水数。
例如,3二进制数总共有4个,分别是4(100)、5(101)、6(110)、7(111),他们中1的个数一共是1+2+2+3=8,所以3对应的水数就是8。
Input
给你一个整数T,表示输入数据的组数,接下来有T行,每行包含一个正整数n(1<=n<=25)。
Output
对于每个n ,在一行内输出n对应的水数。
Sample Input
3
1
2
3
Sample Output
1
3
8
思路
n | 枚举二进制数 | 从最高位,各个位上出现 1 的次数 |
---|---|---|
1 | 1 0 | 1 |
2 | 10 11 | 2+1 |
3 | 100 101 110 111 | 4+2+2 |
4 | 1000 1001 1010 1011 1100 1101 1110 1111 | 8+4+4+4 |
可以看出 n = x 时,n 对应的水数是
(x-1)**2 + ((x-2)**2)*(x-1) # Python code
实现
#include <iostream>
#include <math.h>
#include <iomanip>
using namespace std;
int main()
{
int lines;
cin >> lines;
while (lines--)
{
int n;
cin >> n;
cout << fixed << setprecision(0) << (pow(2, (n - 1)) + pow(2, (n - 2)) * (n - 1)) << endl;
}
return 0;
}
注意点
如果不加 << fixed << setprecision(0)
,当 n=26,输出值会变成 2.18104e+08