首页 > > 程序设计 > C/C++ >

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;
}