首页 > 代码库 > Ural Amount of Degrees（数位dp）
Ural Amount of Degrees（数位dp）
传送门
Amount of Degrees
Time limit: 1.0 second
Memory limit: 64 MB
Memory limit: 64 MB
Description
Create a code to determine the amount of integers, lying in the set [X;Y] and being a sum of exactly K different integer degrees of B.
Example. Let X=15, Y=20, K=2, B=2. By this example 3 numbers are the sum of exactly two integer degrees of number 2:
17 = 24+20,
18 = 24+21,
20 = 24+22.
18 = 24+21,
20 = 24+22.
Input
The first line of input contains integers X and Y, separated with a space (1 ≤ X ≤ Y ≤ 231−1). The next two lines contain integers K and B (1 ≤ K ≤ 20; 2 ≤ B ≤ 10).
Output
Output should contain a single integer — the amount of integers, lying between X and Y, being a sum of exactly K different integer degrees of B.
Sample
| input | output |
|---|---|
15 2022 | 3
|
解题思路
题意：
思路：
#include<iostream>#include<string>using namespace std;int f[32][32];int change(int x, int b){ string s; do { s = char(‘0‘ + x % b) + s; x /= b; } while (x > 0); for (int i = 0; i < s.size(); ++i) if (s[i] > ‘1‘) { for (int j = i; j < s.size(); ++j) s[j] = ‘1‘; break; } x = 0; for (int i = 0; i < s.size(); ++i) x = x | ((s[s.size() - i - 1] - ‘0‘) << i); //或运算，在此相当于加法 return x;}void init()//预处理f{ f[0][0] = 1; for (int i = 1; i <= 31; ++i) { f[i][0] = f[i - 1][0]; for (int j = 1; j <= i; ++j) f[i][j] = f[i - 1][j] + f[i - 1][j - 1]; }}int calc(int x, int k) //统计[0..x]内二进制表示含k个1的数的个数{ int tot = 0, ans = 0; //tot记录当前路径上已有的1的数量，ans表示答案 for (int i = 31; i > 0; --i) { if (x & (1 << i)) //该位上是否为1 { ++tot; if (tot > k) break; x = x ^ (1 << i); //将这一位置0 } if ((1 << (i - 1)) <= x) { ans += f[i - 1][k - tot]; } } if (tot + x == k) ++ans; return ans;}int main(){ int x, y, k, b; cin >> x >> y >> k >> b; x = change(x, b); y = change(y, b); init(); cout << calc(y, k) - calc(x - 1, k) << endl; return 0;}
Ural Amount of Degrees（数位dp）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。