【学习笔记】CF1456E XOR-ranges

有点难😅

考虑每个数被解除上下界限制时对应的二进制位数

第一次解除限制，一定是二进制中$\text{bit}(L_i,p)\ne \text{bit}(R_i,p)$的最高的数位

第二次解除限制，可以是之后的任意一位，发现无论是$L_i$还是$R_i$，其对应的 在这之前的每一位都是固定的，在这之后的每一位都是自由的，因此考虑以此时对应的低位二进制位数为权值建立小根堆笛卡尔树。

考虑在笛卡尔树上$DP$。发现可以设$d{p}_{l,r,k,0/1,0/1,0/1,0/1,0/1}$表示只考虑$\ge k$的数位，区间$[l,r]$中$a_l,a_r$的值固定，分别等于$L/R$，最低位是否翻转，以及这个区间是否存在自由数位的状态。

转移有两种：
$1.1$ 枚举$[l+1,r-1]$中的位置$i$，表示将$a_i$固定为$L/R$，注意如果存在自由数位那么强制最低位要取反，并且最低位之前的$L_i\ne R_i$。然后将区间划分成$[l,i]$和$[i,r]$两个子区间

$1.2$ $[l,r]$中的每个数的最低位都是自由的，那么让数位增加$1$，并且计算最低数位的贡献

复杂度$O(n^{3}K)$。

实现的有点丑陋。不知道其他人是怎么实现的。

#include
#define ll long long
#define pb push_back
#define fi first
#define se second
#define db double
#define ull unsigned long long
#define inf 0x3f3f3f3f3f3f3f3f
using namespace std;
int n,K;
ll L[55],R[55],c[55],dp[55][55][55][2][2][2][2][2];
void add(ll &x,ll y){
    x=min(x,y);
}
ll get(ll x,int y){
    return (x>>y)<<y;
}
int calc(int i,int k,int x){
    if(x==0)return L[i]>>k&1;
    return R[i]>>k&1;
}
ll solve(int l,int r,int k,int x,int y,int f1,int f2,int f3){
    if(l==r)return 0;
    if(k==K){
        if(l+1==r)return 0;
        return inf;
    }
    ll &res=dp[l][r][k][x][y][f1][f2][f3];
    if(~res)return res;res=inf;
    if(l+1==r){
        int v1=calc(l,k,x)^f1,v2=calc(r,k,y)^f2;ll v3=(v1^v2)*c[k];
        if(l==0||r==n+1)v3=0;
        add(res,solve(l,r,k+1,x,y,0,0,f3)+v3);
    }
    else{
        for(int i=l+1;i<r;i++){
            if(f3){
                if(get(L[i],k+1)!=get(R[i],k+1)){
                    if(!(L[i]>>k&1))add(res,solve(l,i,k,x,0,f1,1,1)+solve(i,r,k,0,y,1,f2,1));
                    if(R[i]>>k&1)add(res,solve(l,i,k,x,1,f1,1,1)+solve(i,r,k,1,y,1,f2,1));
                }
            }
            else{
                if(get(L[i],k+1)!=get(R[i],k+1)){
                    if(!(L[i]>>k&1))add(res,solve(l,i,k,x,0,f1,1,0)+solve(i,r,k,0,y,1,f2,0));
                    if(R[i]>>k&1)add(res,solve(l,i,k,x,1,f1,1,0)+solve(i,r,k,1,y,1,f2,0));
                }
                add(res,solve(l,i,k,x,0,f1,0,0)+solve(i,r,k,0,y,0,f2,0));
                add(res,solve(l,i,k,x,1,f1,0,0)+solve(i,r,k,1,y,0,f2,0));
            }
        }int v1=calc(l,k,x)^f1,v2=calc(r,k,y)^f2;ll v3=0,v4=0;
        if(l!=0)v3+=v1*c[k],v4+=(v1^1)*c[k];if(r!=n+1)v3+=v2*c[k],v4+=(v2^1)*c[k];
        add(res,solve(l,r,k+1,x,y,0,0,1)+min(v3,v4));
    }
    return res;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>n>>K;for(int i=1;i<=n;i++)cin>>L[i]>>R[i];
    for(int i=0;i<K;i++)cin>>c[i];
    memset(dp,-1,sizeof dp);
    cout<<solve(0,n+1,0,0,0,0,0,0);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64