首页 > 代码库 > UVa 11121 - Base -2
UVa 11121 - Base -2
题目:计算以-2为基数的数的表示。
分析:数论。写出不同位数能表示的数字区间就可以找到规律。
长度为1:[1,1]; 长度为2:[-2,-1]; 长度为3:[2,5];
观察发现,区间长度增长为1,2,4,8,..,2^k,并且奇偶间隔开;
这样可以按顺序找到对应的1的位置,每次减去对应的基底(-2^k)寻找下一个1的位置即可。
说明:又是数论。
#include <iostream> #include <cstdlib> #include <cstring> #include <cstdio> using namespace std; long long l[40],r[40],b[40]; int ans[40]; int main() { l[0] = 1; r[0] = 1; b[0] = 1; l[1] = -2;r[1] = -1;b[1] = -2; long long base = 4; for (int i = 2 ; i < 33 ; ++ i) { if (i%2) { r[i] = l[i-2]-1; l[i] = l[i-2]-base; }else { l[i] = r[i-2]+1; r[i] = r[i-2]+base; } base <<= 1; b[i] = b[i-1]*-2; } int n,m,s,e; while (~scanf("%d",&n)) for (int i = 1 ; i <= n ; ++ i) { scanf("%d",&m); printf("Case #%d: ",i); for (int i = 0 ; i < 33 ; ++ i) ans[i] = 0; s = 32; while (s >= 0) { if (m >= l[s] && m <= r[s]) { ans[s] = 1; m -= b[s]; } s --; } e = 32; while (e > 0 && !ans[e]) e --; while (e >= 0) printf("%d",ans[e --]); printf("\n"); } return 0; }
UVa 11121 - Base -2
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。