【Lightoj 1032 Fast Bit Calculations 】
发布日期:2021-11-04 12:59:43
浏览次数:4
分类:技术文章
本文共 2612 字,大约阅读时间需要 8 分钟。
Fast Bit Calculations
Description
A bit is a binary digit, taking a logical value of either 1 or 0 (also referred to as “true” or “false” respectively). And every decimal number has a binary representation which is actually a series of bits. If a bit of a number is 1 and its next bit is also 1 then we can say that the number has a 1 adjacent bit. And you have to find out how many times this scenario occurs for all numbers up to N.Examples:
Number Binary Adjacent Bits 12 1100 1 15 1111 3 27 11011 2
Input
Input starts with an integer T (≤ 10000), denoting the number of test cases.Each case contains an integer N (0 ≤ N < 231).
Output
For each test case, print the case number and the summation of all adjacent bits from 0 to N.Sample Input
7 0 6 15 20 21 22 2147483647 Sample Output Case 1: 0 Case 2: 2 Case 3: 12 Case 4: 13 Case 5: 13 Case 6: 14 Case 7: 16106127360一很好的朋友想到的,听他讲过之豁然开朗,想着打就出来了~~
#include#include using namespace std;long long dp[36];int pa[36];long long QAQ(int x,int y) //快速幂{ int base = x ; long long ans = 1; while(y) { if(y&1) ans *= x; x *= x; y >>= 1; } return ans;}int main(){ long long ans; int i,k,j,pl; memset(dp,0,sizeof(dp)); dp[0] = dp[1] = 0 ,dp[2] = 1; for(i = 3 ; i <= 35 ; i++) // 先打个表 { ans = dp[i - 1]; // 先加上上一位的总和 for(j = 0 ; j <= i - 2 ; j++) ans += j * QAQ(2,i - j - 2) + dp[i - j - 2]; // 前 i 个 1 的贡献 + 当前位置的贡献 dp[i] = ans + i - 1; } int T,nl = 0 ,N,kl,x,y,ml; scanf("%d",&T); while(T--) { scanf("%d",&N); memset(pa,0,sizeof(pa)); ans = 0; kl = 0; while(N) { if(N&1) pa[++kl] = 1; else pa[++kl] = 0; N >>= 1; } for(i = kl ; i >= 1 ; i--) { if(pa[i]) { ans += dp[i - 1]; //先加上前一位 pl = 0; ml = i; while(pa[i]) { i--; pl++; } for(j = 0 ; j <= pl - 2 ; j++) ans += j * QAQ(2,ml - j - 2) + dp[ml - j -2]; x = 1 ; y = 1; for(k = 1 ; k <= i ; k++) { y += (x * pa[k]); x <<= 1 ; } ans += (pl - 1) * y; } } printf("Case %d: %lld\n",++nl,ans); } return 0;}
转载地址:https://blog.csdn.net/WYK1823376647/article/details/52634713 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
网站不错 人气很旺了 加油
[***.192.178.218]2024年04月21日 18时31分26秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
芯片为什么持续缺货?
2019-04-29
美国无人机在火星首飞成功,创造历史,3米飞行高度悬停30秒
2019-04-29
缺货涨价很久的MCU的国产和国外厂家汇总!(80家)
2019-04-29
华为重磅反击,鸿蒙来了!
2019-04-29
常用电子接口大全,遇到不认识的,就翻出来对照辨认!
2019-04-29
芯片IC附近为啥要放0.1uF的电容?
2019-04-29
电赛 | 19年全国一等奖,北航学子回忆录。
2019-04-29
电赛 | 19年全国一等奖,北航学子回忆录(上)
2019-04-29
电赛 | 19年全国一等奖,北航学子回忆录(下)
2019-04-29
突破!台积电1nm芯片,有了新进展。
2019-04-29
一文读懂全系列树莓派!
2019-04-29
自制一个害羞的口罩,见人就闭嘴,戴着可以喝奶茶
2019-04-29
聊聊我是如何编程入门的
2019-04-29
J-Link该如何升级固件?
2019-04-29
485通信自动收发电路,历史上最详细的解释
2019-04-29
一位头发发白的神人教你怎么写程序,运维,买电脑,写文章,平面设计!
2019-04-29
「第三篇」全国电子设计竞赛,这些你必须知道的比赛细节,文末附上近十年电赛题目下载...
2019-04-29
5G小科普(漫画版,So easy!)
2019-04-29
「第四篇」电赛控制题可以准备一些什么?
2019-04-29
树莓派翻车了
2019-04-29