解题思路:
观察给的例子,当k = 3, w = 7的时候,因为将7位2进制数三位三位的分割最多分割成三块,所以最多只有三位数的情况,而这个数最小是两位,所以只有两位数和三位数两种情况,由此可以知道,对于每一个k和w,出现的位数情况为w / k(因为从两位数开始考虑所以不用减1),由观察可知,这个数是两位数的时候,它的最低位的最大值7就是其二进制数被分割的时候,最先被分割出的那一块的数,本例中即为111(二进制数),也就是1 + 2 + 4 = 7,而该数为两位数时的所有情况其实就是1到7共7个数字的排列组合,也就是C72 = 21,同理,该数为三位数时的所有情况就是C62 = 30,所以就找到了规律,对于每个2k进制数,从其为两位数的情况开始,每种情况的数量依次为Cs2 = s * (s - 1) / 2,s逐渐递减,且s = 2k - 1,再把每种情况的数量加起来就得到了答案
参考代码:
#include<iostream>
using namespace std;
int k, w;
long long res;
int main()
{
cin >> k >> w;
long long s = 1;
for (int i = 1; i <= k; i ++) s *= 2;
s --; //该数为两位数时其最低位的最大值
int m = w / k; //该数最多可能为m + 1位数,因为从2位数开始看所以不用加一
while (m --)
{
res += s * (s - 1) / 2;
s --;
}
cout << res << endl;
return 0;
}
0.0分
4 人评分
矩阵乘方 (C语言代码)浏览:1031 |
1035 题解浏览:785 |
回文数(一) (C语言代码)浏览:1119 |
简单的a+b (C语言代码)浏览:510 |
P1002 (C语言代码)浏览:961 |
求圆的面积 (C++代码)浮点数有误差!!!浏览:675 |
C语言程序设计教程(第三版)课后习题7.3 (C语言代码)浏览:577 |
母牛的故事 (C语言代码)浏览:479 |
C语言程序设计教程(第三版)课后习题6.7 (C语言代码)浏览:513 |
简单的a+b (C语言代码)浏览:609 |