CF1456E XOR-ranges

神仙题。不愧是 3500 。

我们考虑对于每个数,它必然有一个脱离限制的位。也就是说,每个位置实际上放的值,必然是和 $L$ 或者 $R$ 存在一段 $\text{LCP}$ ,然后下一位脱离限制,然后后面的随意填。

于是我们考虑一个贪心,如果我们知道了 $1 \sim n$ 的所有数中脱离限制位最低的是谁,那么这个脱离限制位之下的所有位对于所有数都是可以随便放的,所以我们一定全放 $0$ 或者全放 $1$ 最优。

我们可以把这个问题推广到任何一个区间上。对于一段区间 $l,r$ ,我们可以枚举脱离限制最低位是谁,再枚举它脱离限制的位,那么我们可以在这下面的位随意发挥。那么如果 $l-1,r+1$ 在下面某一位不同,就必须得在这位有 $1$ 的贡献,否则可以没有贡献。

但是注意到 $l-1,r+1$ 这两个数并不好存下来,因为值域太大。但是我们可以钦定这两个数在当前考虑的位已经被限制上了,于是可以用两个 $0/1$ 表示这个数前面的位贴紧 $l$ 还是 $r$ 以及最下面的位是否被翻转。

于是可以设置出状态 $dp[c][l][r][0/1][0/1][0/1][0/1]$ 表示当前只考虑 $\ge c$ 的位,下面的位不管,区间为 $l,r$ 而 $l-1,r+1$ 的状态分别由两个 $0/1$ 表示。转移分为两种,一种是区间内不存在正好 $c$ 位脱离限制的,那么直接由 $dp[c+1][l][r][0/1][0/1][0/1][0/1]$ 转移过来,再加上这一位的贡献,由左右在这一位是否不同决定。还有一种是枚举一下在 $k$ 脱离限制,就由 $dp[c][l][k-1][…]$ 和 $dp[c][k+1][r][…]$ 转移过来。而如果 $l > r$ 则意味着所有里面的位置都被钦定过了,显然只能走第一种转移。如果 $c = k$ 那么只有在 $l > r$ 的时候才有值,因为到最后一定必须确定所有数。

于是就做完了,写记搜会好写得多。

复杂度 $O(n^3k)$ 带一个大常数,跑着还是很快的。

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
#include "iostream"
#include "algorithm"
#include "cstring"
#include "cstdio"
#include "cmath"
#include "vector"
#include "map"
#include "set"
#include "queue"
using namespace std;
#define MAXN 56
//#define int long long
#define rep(i, a, b) for (int i = (a), i##end = (b); i <= i##end; ++i)
#define per(i, a, b) for (int i = (a), i##end = (b); i >= i##end; --i)
#define pii pair<int,int>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define vi vector<int>
#define all(x) (x).begin() , (x).end()
#define mem( a ) memset( a , 0 , sizeof a )
typedef long long ll;
int n , k;
ll L[MAXN] , R[MAXN] , C[MAXN];
ll dp[MAXN][MAXN][MAXN][2][2][2][2];

inline void ckm( ll& a , ll b ) {
a = min( a , b );
}
ll wkr( int c , int l , int r , int l1 , int l2 , int r1 , int r2 ) {
if( c == k ) return l > r ? 0 : 1e18;
ll& s = dp[c][l][r][l1][l2][r1][r2];
if( ~s ) return s;
ll lt = ( ( l1 ? R[l - 1] : L[l - 1] ) >> c ) ^ l2;
ll rt = ( ( r1 ? R[r + 1] : L[r + 1] ) >> c ) ^ r2;
s = 1e18;
ckm( s , wkr( c + 1 , l , r , l1 , 0 , r1 , 0 ) + ( l != 1 && r != n ? ( ( lt & 1 ) ^ ( rt & 1 ) ) * C[c] : 0 ) );
rep( k , l , r ) rep( t , 0 , 1 ) {
if( !c ) ckm( s , wkr( c , l , k - 1 , l1 , l2 , t , 0 ) + wkr( c , k + 1 , r , t , 0 , r1 , r2 ) );
ll w = ( t ? R[k] : L[k] );
if( L[k] <= ( ( w ^ ( 1ll << c ) ) & ( ~( ( 1ll << c ) - 1 ) ) ) && ( ( w ^ ( 1ll << c ) ) | ( ( 1ll << c ) - 1 ) ) <= R[k] )
ckm( s , wkr( c , l , k - 1 , l1 , l2 , t , 1 ) + wkr( c , k + 1 , r , t , 1 , r1 , r2 ) );
}
return s;
}

void solve() {
cin >> n >> k;
rep( i , 1 , n ) scanf("%lld%lld",L + i,R + i);
rep( i , 0 , k - 1 ) scanf("%lld",C + i);
memset( dp , -1 , sizeof dp );
cout << wkr( 0 , 1 , n , 0 , 0 , 0 , 0 ) << endl;
}

signed main() {
// int T;cin >> T;while( T-- ) solve();
solve();
}
文章作者: yijan
文章链接: https://yijan.co/2021/04/19/cf1456e-xor-ranges/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Yijan's Blog