本文主要是介绍UVA 11645 - Bits(数论+计数问题),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
题目链接:11645 - Bits
题意:给定一个数字n,要求0-n的二进制形式下,连续11的个数。
思路:和 UVA 11038 这题类似,枚举中间,然后处理两边的情况。
不过本题最大的答案会超过longlong,要用高精度,不过借鉴http://www.cnblogs.com/TO-Asia/p/3214706.html这个人的方法,直接用两个数字来保存一个数字,这样能保存到2个longlong的长度,就足够存放这题的答案了。
代码:
#include <stdio.h>
#include <string.h>long long n, a, b;
const long long DIG = 1e13;
void add(long long num) {b += num;a += b / DIG;b %= DIG;
}int main() {int cas = 0;while (~scanf("%lld", &n) && n >= 0) {a = b = 0;long long tmp = n, d = 1;while (n > 1) {add((n>>2) * d);if ((n&3) == 3)add((tmp&(d - 1)) + 1);d <<= 1;n >>= 1;}printf("Case %d: ", ++cas);if (a) {printf("%lld", a);printf("%013lld\n", b);}else printf("%lld\n", b);}return 0;
}
这篇关于UVA 11645 - Bits(数论+计数问题)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!