跳至正文

NOIp 2006 提高组 4 2^k进制数

  这题我以前写过的,现在就当是再温习一遍吧,思路就是递推(也就是动态规划)根据一个公式推导出来的DP方程,首先我用f[i][j]表示第i位数以j开头的数字共有多少个,那么最容易得到的一个转移方程是:
  f[i][j] = f[i – 1][j + 1] + f[i – 1][j + 2] + ……. + f[i – 1][n – 1] + f[i – 1][n].
  但是这个方程给我们的感觉就是一个字——太慢了,为什么这么慢呢?因为它就是这么慢,要把所有的一个个相加一次,但是注意到上面我画红的部分!就是用这个公式,这部分能够表示成啥?很简单啊:
  f[i][j + 1] = f[i – 1][j + 2] + ……. + f[i – 1][n – 1] + f[i – 1][n].
  那么智商高一点的人就看到玄机了,能够把f[i][j]简化成如下的形式:
  f[i][j] = f[i][j + 1] + f[i – 1][j + 1]
  如此一来程序就清晰多了,代码也很好写,要注意的是搜索时j是从后向前搜索,我还是使用面向对象的思想,先封装了一套int类型的,然后再修改成高精度类型的,int类型的(40分)如下:

#include <stdio.h>
typedef int num;
num f[61][513];
num ans;

void give(num a, int b)
{
        
a = b;
}

void add(num a, num b)
{
        a += b;
}

void output(num a)
{
        printf("%d",
a);
}

int main(void)
{
        int i, j;
        int n, s, k, t, l;
        scanf("%d%d", &s, &n);
        k = 1 << s;
        for(i = 0; i < k; i++){
                give(&f[0][i], 1);
        }
        t = n / s;
        for(i = 1; i <= t; i++){
                for(j = k – i – 1; j >= 1; j–){
                        add(&f[i][j], &f[i][j + 1]);
                        add(&f[i][j], &f[i – 1][j + 1]);
                }
        }
        for(i = 1; i < t; i++){
                for(j = k – i – 1; j >= 1; j–){
                        add(&ans, &f[i][j]);
                }
        }
        l = n – t s;
        if(l == 0){
                l = k;
        }else{
                l = 1 << l;
        }
        for(i = 1; i < l; i++){
                add(&ans, &f[t][i]);
        }
        output(&ans);
        printf("\n");
        return 0;
}
  详细修改了一番之后,发现主函数中错了,后来详细修改了一番,弄得我以为高精度写错了,仔细检查之后发现两个地方错了,第一个是数组开小了,本来是num f[61][513],后来发现要使用f[513][513],再一个就是不能够直接使用用(n – 1)/s,因为如果用30000/1(k = 1, w = 30000)的话那数组又会显得小了,需要f[30000][513],但是实际上又跟本用不到(因为k很小时最多只有
!((1 << k) – 1)种情况,那样的情况很少)。
  所以最终修改了一大番,确定了AC代码:

#include <math.h>
#include <stdio.h>
#define max(a, b) ((a)>(b)?(a):(b))
#define used 100000000
#define bits ((int)log10(used))
#define MAX 26
typedef struct{
        int num[MAX];
        int len;
}num;
num f[513][513];
//数组开小了 
num ans;

void give(num a, int b)
{
        int i;
        for(i = 0; b != 0; i++){
                a->num[i] = b % used;
                b /= used;
        }
        a->len = i;
}

void add(num a, num b)
{
        int i;
        int len = max(a->len, b->len);
        int re = 0;
        for(i = 0; i < len; i++){
                a->num[i] += b->num[i] + re;
                re = a->num[i] / used;
                a->num[i] %= used;
        }
        if(re > 0){
                a->num[i] = re;
                len++;
        }
        a->len = len;
}

void output(num a)
{
        int i;
        int len = a->len,
num = a->num;
        printf("%d", num[len – 1]);
        len–;
        for(i = len – 1; i >= 0; i–){
                printf("%.*d", bits, num[i]);
        }
}

int main(void)
{
        int i, j;
        int n, s, k, t, l;
        scanf("%d%d", &s, &n);
        k = 1 << s;
        t = (n – 1) / s + 1;
        if(t > k){                     //一直没写这个~!! 所以可能会出现各种想象不到的情况, 如:t = 3000
                t = k;
        }
        for(i = 0; i < k; i++){
                give(&f[0][i], 1);
        }
        for(i = 1; i < t; i++){
                for(j = k – i – 1; j >= 1; j–){
                        add(&f[i][j], &f[i][j + 1]);
                        add(&f[i][j], &f[i – 1][j + 1]);
                }
        }
        for(i = 1; i < t; i++){
                for(j = k – i – 1; j >= 1; j–){
                        add(&ans, &f[i][j]);
                }
        }
        l = n % s;
        if(l == 0){
                l = k;
        }else{
                l = 1 << l;
        }
        for(i = 1; i < l; i++){
                add(&ans, &f[t – 1][i]);
        }
        output(&ans);
        printf("\n");
        return 0;
}

发表评论

您的电子邮箱地址不会被公开。