POJ 3252 Round Numbers（数位dp）

题意：给定区间[l,r]，l < r ，求区间中满足条件的正整数的个数：二进制表示下0的个数不少于1的个数。

分析：f(x)表示<=x时满足条件的数的个数，所求问题即为f(r)-f(l-1)。x二进制表示下从高到低位为1，bi,bi-1, bi-2, b0, 长度为len，那么f(x)可以这样求解：

dp[i][j]表示从i~0位可以任意为0或1时，0的个数比1多j个情况，由于j可能为负数，所以这里方便处理，将j = 40表示0的个数和1的个数一样多。

转移：dp[i][j] = sum{dp[i-1][j-1]+dp[i-1][j+1]}.

1首先考虑长度<len的数，设长度l < len,由于首位一定为1，那么只需考虑剩下的l-1位任意选取时的情况；

2考虑长度为len的数，首位一定为1，从次高位到低位一次考虑，如果bi为1，那么此位为0，之前的位数和1，bi+2， bi+1一样时，剩下的i-1,i-2, 0位便可任意选取。

最后应该考虑x本身是否满足条件。

代码：

 #include <cstdio>

 #include <iostream>

 #include <map>

 #include <cstring>

 #include <cstdlib>

 #include <cmath>

 #define pb push_back

 #define mp make_pair

 #define esp 1e-8

 #define lson   l, m, rt<<1

 #define rson   m+1, r, rt<<1|1

 #define sz(x) ((int)((x).size()))

 #define pb push_back

 #define in freopen("solve_in.txt", "r", stdin);

 #define bug(x) printf("Line : %u >>>>>>\n", (x));

 #define inf 0x7f7f7f7f

 using namespace std;

 typedef long long LL;

 typedef map<int, int> MPS;

 typedef pair<int, int> PII;

 const int maxn = ;

 int dp[maxn][], dig[maxn];

 int solve(int x) {

     if(!x) return ;

     int len = , ans = ;

     while(x) {

         dig[len++] = x&;

         x >>= ;

     }

     int tot = ;

     for(int i = len-; i >= ; i--) {

         if(i < len-) {

             if(i- >= )

                 for(int j = ; j < ; j++)

                     ans += dp[i-][j];

             if(dig[i]) {

                 if(i) {

                     for(int j = max(, -tot-); j < ; j++)

                         ans += dp[i-][j];

                 } else {

                     ans += (tot+ >= );

                 }

             }

         }

         tot += dig[i] ? - : ;

     }

     ans += (tot >= );

     return ans;

 }

 void pre() {

     dp[][] = ;

     dp[][] = ;

     for(int i = ; i < maxn; i++)

         for(int j = ; j < ; j++) {

             dp[i][j] += dp[i-][j+]+dp[i-][j-];

         }

 }

 int main() {

     int l, r;

     pre();

     scanf("%d%d", &l, &r);

     cout << solve(r)-solve(l-) << endl;

     return ;

 }

巴特西

POJ 3252 Round Numbers（数位dp）

最新文章

热门文章