AGC015 D A or...or B Problem(智商题)
程序员文章站
2022-11-30 20:39:23
题意 题目链接 给出$[A, B]$,求出$[A, B]$内任意数Or起来能得到多少不同的值 Sol 又是神仙题,考试的时候最怕这种题了qwq 设A,B二进制分解后第一个不同的位为i,那么显然i之前所有的数都是没用的(因为or出来的数都包含这些位) 考虑剩下的数形成的新的A和B能生成那些数 首先$B ......
题意
给出$[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; }
上一篇: 四种气虚体质的表现 分享给关爱的ta
下一篇: 感恩节一大早