LibreOJ 2886.「APIO2015」巴厘岛的雕塑

mm 表示分的组数,sis_i 表示第 ii 组的和。
看到位运算,首先考虑按位贪心,从高到低。

可以先假设结果的所有位都是 11,然后再从高位到低位尝试换成 00
于是问题转化为给定 xx,是否有 m[A,B]m \in [A,B] 的方案满足
容易发现只需要满足每一个 sis_i 都满足 即可。
于是就变成了一个睿智 DP。

首先设 fi,jf_{i,j} 表示前 ii 个数分 jj 段的可能性。
再设 sumi=j=1iYjsum_i = \sum\limits_{j=1}^i Y_j。 有转移

然后若 为真,则 xx 合法。

然鹅当 N2000N \le 2000 时,O(n3logYi)O(n^3 \log Y_i) 就过不去了。
然鹅注意到此时 A=1A = 1
换个状态,gig_i 表示前 ii 个要满足上述条件,最少分几组。
其实也很简单……

于是判一下 gNBg_N \le B 即可。
复杂度 O(n2logYi)O(n^2 \log Y_i)

代码:

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
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 2e3;
const int LG = 60;
int n,l,r;
long long s[N + 5],ans = (1LL << LG) - 1;
int f[N + 5][N + 5],g[N + 5];
int check(int op,long long x)
{
if(!op)
{
memset(f,0,sizeof f),f[0][0] = 1;
for(register int i = 1;i <= n;++i)
for(register int j = 1;j <= i;++j)
for(register int k = 0;k < i;++k)
if((s[i] - s[k] | x) == x)
f[i][j] |= f[k][j - 1];
for(register int i = l;i <= r;++i)
if(f[n][i])
return 1;
return 0;
}
else
{
memset(g,0x3f,sizeof g),g[0] = 0;
for(register int i = 1;i <= n;++i)
for(register int j = 0;j < i;++j)
if((s[i] - s[j] | x) == x)
g[i] = min(g[i],g[j] + 1);
return g[n] <= r;
}
}
int main()
{
scanf("%d%d%d",&n,&l,&r);
for(register int i = 1;i <= n;++i)
scanf("%lld",s + i),s[i] += s[i - 1];
for(register int i = LG - 1;~i;--i)
ans &= ~(1LL << i),!check(l == 1,ans) && (ans |= 1LL << i);
printf("%lld\n",ans);
}