1 solutions
-
0
作为一个既搞数竞,又搞物竞,又搞信竞的人我很清楚这题肯定可以不用数位DP来做这其实就是一个简单的数学题,把这个整数转换成B进制,你就会发现一个很神奇的事情:
B的幂变成(100...0)
不同的B的幂之和变成了0和1的排列 那么,只需要把[X,Y]中的所有数都写成B进制,然后这些数里面恰好有K个1,其余都是0就行
搞定!!!
#include <bits/stdc++.h> using namespace std; string change_M(int x,int m) { string ans = ""; while(x > 0) { char ch = '0' + x % m; ans = ch + ans; x /= m; } return ans; } int S(string s) { int len = s.size(),sum = 0; for(int i = 0;i < len;i++) { if(s[i] > '1') return -1; sum += (s[i] - '0'); } return sum; } int main() { int s,m,x,y; scanf("%d%d%d%d",&x,&y,&s,&m); int cnt = 0; for(int i = x;i <= y;i++) { if(S(change_M(i,m)) == s) cnt++; } printf("%d",cnt); return 0; }
然后...
TE了。。。
这题还真的不简单,因为Y最大可是2^31 - 1
经过一晚上的抢救之后,也是终于做出来了复杂度低一点的办法,代码如下:(把string吃了)
#include <bits/stdc++.h> using namespace std; const int N = 50; int h[N]; int f[N][N]; int k, x, y, b; int solve(int x) { int top = -1; while (x) { int p = x % b; x /= b; h[++top] = p; } int tot = 0, ans = 0; for (int i = top; i >= 0; --i) { if (h[i] == 1) { ++tot; if (tot > k + 1) break; if (i > 0) ans += f[i - 1][k - tot + 1]; } else if (h[i] > 1) { ans += f[i][k - tot]; return ans; } } if (tot == k) ++ans; return ans; } int main() { scanf("%d%d%d%d", &x, &y, &k, &b); f[0][0] = 1; f[0][1] = 1; for (int i = 1; i <= 31; i++) { f[i][0] = 1; for (int j = 1; j <= i + 1; j++) f[i][j] = f[i - 1][j - 1] + f[i - 1][j]; } --x; int ans = solve(y) - solve(x); printf("%d\n", ans); return 0; }
- 1
Information
- ID
- 165
- Time
- 1000ms
- Memory
- 512MiB
- Difficulty
- 10
- Tags
- # Submissions
- 8
- Accepted
- 3
- Uploaded By