例题1 ural 1057.

　　1. 树形结合, 按位统计. 若当前位为1, 则取0, 剩下的位任意取都比其小, ans += f[ L ][ k-tot ], L表示剩下长度. 论文这个地方写的感觉不对- -...

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           using namespace std;int f[32][32];void init(){    memset(f,0,sizeof(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-1] + f[i-1][j];    }}int get(int n,int b){    string s;    while( n ){        s = char((n%b)+'0') + s;        n /= b;    }    for(int i = 0; i < (int)s.size(); i++){        if( s[i]-'0' > 1 ){            for(int j = i; j < (int)s.size(); j++)                s[j] = '1';            break;            }        }    int x = 0;    for(int i = 0; i < (int)s.size(); i++)        x = (x<<1)|(s[i]-'0');    return x;}int calc(int n,int k){    int tot = 0, res = 0;    for(int i = 30; i >= 0; i--){        if( (n&(1<

View Code

　　2. 还是比较喜欢记忆化的写法, 比较通用. Count( bool less, int Length, int cur_num, int target_num, int x )

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           using namespace std; int get(int n,int b){    string s;    while( n ){        s = char((n%b)+'0') + s;        n /= b;    }    for(int i = 0; i < (int)s.size(); i++){        if( s[i]-'0' > 1 ){            for(int j = i; j < (int)s.size(); j++)                s[j] = '1';            break;            }        }    //printf("s = %s\n", s.c_str() );        int x = 0;    for(int i = 0; i < (int)s.size(); i++)        x = (x<<1)|(s[i]-'0');    return x;} int dp[50][50];// dfs( false, 31, 0, k, x )int dfs(bool less, int L, int tot, int k, long long x){ //x本身不被计算    //printf("less = %d, L = %d, tot = %d, k = %d, x = %lld\n", less, L, tot, k, x );    if( L == 0 )        return less && (tot==k);    if( less && (dp[L][k-tot]!=-1) )         return dp[L][k-tot];    int res = 0, d = (x&(1ll<<(L-1))) > 0 ? 1 : 0;        for(int i = 0; i <= 1; i++){        if( (less==false) && (i > d) ) continue;            res += dfs( less||(i

View Code

[1,n] 区间中二进制形式下1的数量

// If No Limit // dp[i]: I位1的数量和// dp[i] = dp[i-1] + dp[i-1] + 2^(i-1)#include
      
       #include
       
        const int N = int(1e5)+10;int f[N];int dfs(bool less,int x,int L){
    //32---1//    printf("L = %d, less = %d\n", L,less); getchar();getchar();    if( L == 1 ) return less;    if( less && (f[L]!=-1) ) return f[L];    int res = 0, d = (x&(1<<(L-1)))?1:0;    for(int j = 0; j < 2; j++){        if( !less && (j>d) ) continue;        res += dfs( less||(j

View Code

例题2 spoj 1182 Sorted bit sequence 求区间 [x,y] 中数位和从小到大，相同则数值大小排序的第K个数

　　f( i, j ) 表示后i位任意，数位和为j的方案数

　　count(i,j) 表示 [1,i)间数位和为j的方案数　　

　　1. 首先利用 count() 求出第k的数位和 sum.

　　2. 然后再逐位确定，同样利用count();

负数可以选择与整数分开，单独做，或者通过转换例如在33位+1之类的与整数一起做。

例题3 spoj 2319 Sequence

　　因为对于一个最大值 S，其分组数有一个最小值x, 若x<=M 则意味着S还可以减小。所以可以二分找出最合适的S。

　　对于每次二分得到的最大值S，求分数数量时，每次让分组尽量满，即可得到最小分组数量X

　　函数 count( n ) 表示 [1,n] 中所有数二进制形式下 1的数量总和

　　假定目前分组左边界是 a, 我们需要求最大的右边界满足 count(b) - count(a-1) <= S.

　　这里需要通过逐位确定的方法的求解b的值

例题4 sgu 390 Tickets

　　sumOf( x ) 表示x的数位和

　　最好理解成按顺序枚举 x 属于 [L,R] ，然后一个一个分组添加。若当前数位和为 remain, 当加入x进来时， remain + sumOf(x) >= K时，此时就会多一个分组，

否则当前未满的分组 remain = remain + sumOf(x).

　　我们可以提取一个不受约束的状态来简化计算。

　　dp[ L ][ sum ][ left ] : 表示后L位取所有值，且L位之前的数位和为sum，且之前最后一个分组未满时已有的数位和left，分组总数与最后一个未满分组剩余量

　　然后进行按位处理以及合并状态。

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           using namespace std;typedef long long LL;const int Length = 19;int K ,low[20], high[20];void get( LL x, int *r ){    int cnt = 0;    for(int i = 0; i < Length; i++)        r[i] = x%10, x /= 10;//    for(int i = 0; i < Length; i++)//        printf("%d ", r[i] ); puts("");}struct Node{    int left; LL tot;    Node(){}    Node(int _l,LL _t):left(_l),tot(_t){}};Node dp[20][200][1001];bool vis[20][200][1001];Node count(bool isGreater,bool isLess,int L,int sum,int start){    if( L == 0 ){        if( isLess && isGreater ){            if( start+sum >= K ) return Node(0,1);            return Node(start+sum,0);        }        return Node(start,0);    }    int left = start; LL tot = 0;    if( isLess && isGreater && vis[L][sum][left] ) return dp[L][sum][left];    for(int x = 0; x < 10; x++){        if( !isGreater && (x
           
            high[L-1]) ) continue; Node t = count( isGreater||(x>low[L-1]),isLess||(x

View Code

例题5 zoj 2599 Graduated Lexicographical Ordering

　　将[1,n]中的所有数排序，第一关键字是数位和从小到大，第二关键字是字典序。

　　求[1,n]中值K在第几位，以及第K位的值是多少。

　　f[ L, sum ] 表示后L位任意，数位和为sum的方案数量。

　　count( n, sum ) 表示 [1,n] 数位和为sum的方案数量.

　　对于第一问，首先求出 {1,sumOf(K)-1} 的数量，然后再统计数位和为sumOf(k) 且字典序小于K的数量，相加即为结果。对于统计数位和为 sum(k) 且字典序小于K的数量，因为长度不同，我们没法直接求。我们可以枚举 x 的长度范围 [1, l ength(n) ] 来计算。

　　\sum { count( k, length, sum(k) ) - f( length-1, sum(K) ) } d

　　对于第二问也是利用上面的方式来逐位确定第K的数的每一位，细节比较多。

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           using namespace std;typedef long long LL;const int Length = 19;LL n, K;LL f[20][200]; //后i位任意，数位和为j 的方案总数LL pow10[20];int getbit(LL x){    for(int i = Length; i >= 1; i--){        if( x/pow10[i-1] ) return i;    }}int SumOf(LL x){    int re = 0; while(x) re+=x%10,x/=10; return re;}int get(int *r,LL x){    for(int i = 0; i < Length; i++) r[i]=x%10,x/=10;}void init(){    pow10[0] = 1;    for(int i = 1; i < Length; i++) pow10[i]=pow10[i-1]*10;    memset(f,0,sizeof(f));    f[0][0] = 1;    for(int i = 1; i <= Length; i++){        for(int j = 0; j < 200; j++){            for(int x = 0; x<10 && x<=j; x++)                f[i][j] += f[i-1][j-x];        }    }}LL count(bool less, int *r, int L, int sum, int goal){ // [1,x) 数位和为goal的数量    if( L == 0 ) return less && (sum==goal);    if( less ) return f[L][goal-sum];    LL res = 0;    for(int x = 0; x < 10; x++){        if( !less && (x>r[L-1]) ) continue;        if( sum+x > goal ) continue;        res += count(less||(x
           
             L ) t/=10,k--; while( k < L ){ if( t<=n/10 && t*10<=n ) t*=10,k++; else{ t=n; flag=true; break; } }// printf("Count:: t = %I64d\n", t); memset(r,0,sizeof(r)); int len = 0; LL remain = t; while(t) r[len]=t%10,t/=10,tmp+=r[len++]; LL temp = count(false,r,L,0,sum)-f[len-1][sum]; if( (L <= getbit(A)) || (remain==n && flag) ) temp += (tmp==sum);// printf("Count:: temp = %I64d\n", temp ); return temp;}LL Deal_1(){ LL tot = 0; int sum = SumOf(K); int r[20]; get(r,n+1); for(int i = 1; i < sum; i++ ) tot += count(false,r,Length,0,i); //printf("Deal_1:: tot = %I64d\n", tot ); for(int i = 1; i <= getbit(n); i++) tot += Count( K, i, sum );// puts("--->"); return tot;// printf("%I64d\n", tot );}LL check(LL A,int x){ if( A <= n/10 ) return min( A*10+x, n ); else return n;}LL Deal_2(){ LL rank = K, A; int sum, r[20]; get(r,n+1); for(sum=1;;sum++){ LL tmp = count(false,r,Length,0,sum);// printf("Deal:: tmp_%d = %I64d, rank = %I64d\n", sum, tmp, rank ); getchar(); getchar(); if( rank - tmp > 0 ) rank -= tmp; else break; }// printf("Deal_2:: rank = %I64d, sum = %d\n", rank, sum); int flag = 0; for(int i = 1; i <= 9; i++){ LL tot = 0; for(int L = 1; L <= getbit(n); L++) tot += Count( i, L, sum );// printf("Deal_2:: i = %d, tot = %I64d\n", i, tot ); if( tot >= rank ){ flag = 1; if(tot==rank && i==sum) A = i, rank = 0; else A = i-1; break; } } if( !flag ) A = 9; if( !rank ) return A;// printf("First:: A = %I64d\n", A); for(int j,i = 2;i <= getbit(n);i++){ // 逐位确定 LL tmp, x; for(j = 0; j < 10; j++){ //当前位的取值j tmp = 0, x = A; // 计算当前位置取j时，长度相等字典序小于x，且数位和为sum的数量 for(int L = 1; L <= getbit(n); L++) // 这里可能溢出 tmp += Count( x*10+j, L, sum);// printf("Deal_2:: tmp = %I64d, j = %d\n", tmp, j ); if( tmp >= rank ) break; } if( j < 10 ){ if( (rank==tmp) && (SumOf(A*10+j)==sum) ) {A = A*10+j; break;} else A = A*10 + (j-1); } else A = A*10+9; } return A;}int main(){// freopen("1.in","r",stdin); init(); // 预处理f(i,j) 后i位任意，且数量和为j的总数 while( cin >> n >> K )// while( scanf("%lld%lld",&n,&K) != EOF) { if( n+K == 0 ) break; LL a = Deal_1(); LL b = Deal_2(); cout << a << " " << b << endl;// printf("%lld %lld", a,b ); } return 0;}

View Code

转载于:https://www.cnblogs.com/yefeng1627/archive/2013/05/17/3083543.html

你可能感兴趣的文章