欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

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