zzuli —— 2134 维克兹的进制转换（dp）

秒速五厘米 2021-09-26 16:34 85阅读 0赞

题目链接：[http://acm.zzuli.edu.cn/problem.php?id=2134][http_acm.zzuli.edu.cn_problem.php_id_2134]

题目：

## 2134: 维克兹的进制转换 ##

## 题目描述 ##

我进入了突如其来的强光。闪烁。闪烁，闪烁，闪烁。我调整好眼睛，评估我前方的景观。

有东西在乱窜。我往下看，发现了一只小个的白色生物，用后腿站立着，嗅闻着我的躯体。它吸引了我的注意。

你有什么用途？

我分析这个生物。品红色热能光束一闪而过，它曾颤动的地方扬起尘埃。

哺乳动物...夜行习性...无可挑剔的听觉。难以置信的弱小。但它们的繁殖能力如此强大。

“唔，”我喃喃自语。希望能发现更加复杂的物体；那些东西把我给迷住了。

消化并学习：这是我的目的。和我一起旅行的其它来客都很原始：杀死并吃掉，杀死并吃掉。我需要收集所有可用的信息——收获更多有价值的资源。

维克兹是少数热爱学习的虚空来客之一，他带着非凡的意图探索着符文之地：吸收掉所有知识。凭借着他不断地注视，维克兹可以发射瓦解光线来灭除并分析他途中的一切东西，并为他供给数量庞大的信息。没人知道他为什么需要如此多的材料，尽管有人推测他设法了解符文之地，是为了加速它的毁灭。

有一天，维克兹突发奇想，他觉得古老的二进制魔法串太过单一，于是他规定二进制除了 0 和 1，还有 2。现在维克兹想知道该规则下十进制数 N 转换为二进制数的方案数，维克兹当然可以轻松算出来，但他正好缺一个一起游览符文大地的伙伴，于是他把这个问题交给了你，希望你不要让他失望才好。

## 输入 ##

输入包括 T 组数据，每组数据有一个非负整数 N。（T <= 1e5, N <= 1e7）

## 输出 ##

输出一个正整数代表十进制数 N 转换为二进制数的方案数。

## 样例输入 ##

41234

## 样例输出 ##

1213

## 提示 ##

1 ——> 12 ——> 10 or 23 ——> 114 ——> 100 or 20 or 12

题目描述：

简单的dp题，真的，看明白了特别简单，但我当时比赛的时候是一点不明白。偶然间又看到了这题，就写了。

设dp\[i\]为第i个数的方案数，则

dp\[i\] = dp\[i>>1\]    (i&1==1)

dp\[i\] = dp\[i>>1\]+dp\[(i-1)>>1\]    (i&1==0)

特别的，dp\[0\] = 1。

代码：

#include<stdio.h>
    #include<string.h>
    int dp[10000010];
    int main()
    {
    	int i;
    	int t,n;
    	dp[0] = dp[1] = 1;
    	for(i = 2;i <= 10000000;i++)
    		if(i&1)
    			dp[i] += dp[i>>1];
    		else
    			dp[i] += dp[i>>1]+dp[(i-1)>>1];
    	scanf("%d",&t);
    	while(t--){
    		scanf("%d",&n);
    		printf("%d\n",dp[n]);
    	}
    	return 0;
    }

[http_acm.zzuli.edu.cn_problem.php_id_2134]: http://acm.zzuli.edu.cn/problem.php?id=2134