AGC015 D A or...or B Problem(智商题)
2018-09-19 02:44:16来源:博客园 阅读 ()
题意
题目链接
给出$[A, B]$,求出$[A, B]$内任意数Or起来能得到多少不同的值
Sol
又是神仙题,考试的时候最怕这种题了qwq
设A,B二进制分解后第一个不同的位为i,那么显然i之前所有的数都是没用的(因为or出来的数都包含这些位)
考虑剩下的数形成的新的A和B能生成那些数
首先$B-A+1$这些数一定是能生成的
再考虑这些数or起来能得到哪些数
为了方便讨论,把AB分成两个集合
第一个是$S1 = [A, 2^r)$,另一个是$S2 = [2^r, B]$
S1内能生成的数有$[A, 2^r - 1]$
S2内能生成的数有$[2^r, 2^r + 2^{p+1} - 1]$
其中$p$表示B二进制分解后r位置往后下一个1的位置
两个集合Or起来能生成的数有$[A + 2^r, 2^{r+1} - 1]$
最后一个边界我自己没有想出来,其实归纳证明一下是显然的
首先是最高位r,包含该位的元素一定可以通过2^r or S1得到
r - 1往后的都可以由S2得到
然后对AB二进制拆分后判断一下上面说的边界条件即可
#include<cstdio> #include<iostream> #include<cstring> #define LL long long #define int long long using namespace std; const int MAXN = 2001; inline LL read() { char c = getchar(); LL x = 0, f = 1; while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();} while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar(); return x * f; } LL A, B; int a[MAXN], b[MAXN], N, M; int Get(int x, int *a) { int mx = 0; for(int i = 0; i <= 60; i++) { if(x & (1ll << i)) mx = i; a[i] = (bool)(x & (1ll << i)); } return mx; } main() { A = read(); B = read(); if(A == B) {puts("1"); return 0;} N = Get(A, a); M = Get(B, b); //for(int i = 0; i <= M; i++) // printf("%d", b[i]); int r = 0, p = 0; for(int i = M; i >= 0; i--) if(a[i] != b[i]) {r = i; break;} for(int i = r -1; i >= 0; i--) if(b[i]) {p = i; break;} //printf("%d %d\n", r, p); A = 0; B = 0; for(int i = 0; i <= r; i++) { if(a[i]) A += (1ll << i); if(b[i]) B += (1ll << i); } int al = A, ar = (1ll << r) + (1ll << (p + 1)) - 1; int ll = A + (1ll << r), rr = (1ll << (r + 1)) - 1; if(ar < ll) cout << ar - al + 1 + rr - ll + 1; else cout << rr - al + 1; return 0; }
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- 哈尔滨网络热身赛 2019-11-25
- 两个数的差 2019-10-16
- 带毒的水 2019-08-16
- CCPC2019江西省赛-Problem G.Traffic 2019-08-16
- [Algorithm] 1. A+B Problem 2018-11-03
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash