题目大意:给出n,输出第n给Pinary Number,Pinary Number为二进制数,并且没有连续两个1相连。
解题思路:dp[i]表示到第i位有dp[i]种,于是给定n,一层循环判断dp[i]≤n的话,就输出1,并且n减掉dp[i],注意输出0的时候,不能输出前导0.
#include <cstdio>
#include <cstring>
typedef long long ll;
const int N = 50;
ll dp[N];
void init () {
memset(dp, 0, sizeof(dp));
dp[0] = dp[1] = 1;
for (int i = 2; i <= 40; i++)
dp[i] = dp[i-1] + dp[i-2];
}
void solve (ll n) {
bool flag = false;
for (int i = 40; i; i--) {
if (n >= dp[i]) {
printf("1");
n -= dp[i];
flag = true;
} else if (flag)
printf("0");
}
printf("\n");
}
int main () {
init ();
int cas;
ll n;
scanf("%d", &cas);
for (int i = 0; i < cas; i++) {
scanf("%lld", &n);
solve(n);
}
return 0;
}
分享到:
相关推荐
Uva 100 ,问题是The 3n+1 probelm ,可以ac的代码
UVA 100题答案
判断输入字符串是否为镜像或回文串。 来源于UVaOJ - 401. 水题。
开源项目-codingsince1985-UVa#uva-online-judge-solutions-in-golang.zip,两年来每天都在解决一个uva在线裁判问题,算起来…
uva705 Slash Maze 的代码,在UVaOJ上通过
PDF试题
UVa写入 使用C ++编写UVa OJ: : 等级 基于 ★★ ★★ ★★★ ★★★★ ★★★★★ 未排名
uva532 Dungeon Master的源代码,并且AC了
Algorithm-UVA-Solutions-in-Python.zip,python 3中各种uva(acm)问题的解决方案。,算法是为计算机程序高效、彻底地完成任务而创建的一组详细的准则。