本站在允许 JavaScript 运行的环境下浏览效果更佳


题解分享:HRBUST 1132 水数

68

题目描述

题目描述 点我展开

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