又卡空间又卡时间的
巴厘岛的雕塑
思路
套路的把二进制下每位分开考虑，从高到低贪心判断该位能否为 $0$
考虑 $n^2$ 个三元组 $(l, r, sum)$ ，表示“从 $l$ 到 $r$ 和为 $sum$ ”，记当前可选集合为 $S$ ，初始时 $S$ 包含所有三元组
对于当前位，把 $sum$ 为 $1$ 的从 $S$ 中去除，然后 $O(n^3)$ 暴力 dp 判断可否用剩下的三元组凑出 $1 \sim n$ ，不行就再把删的数加回去，一看时间， $O(40 * n^3)$ ，虽然跑不满可过 $70 \sim 85 pts$ 但明显再卡常也过不了
发现最后一个满数据的 Sub 有性质，即 $A = 1$ ，那 dp 不就只用求个最小值，变成 $O(n^2)$ ，可过
但，我伞兵的要把 $n^2$ 个二元组真的用 long long 记下来，导致空间爆炸，在空间只给 $64 MiB$ 的 loj 上直接 MLE ，用 short 卡了半天，最后发现只要记录 $l, r$ ，用前缀和现场算 $sum$ 即可
唉，一波三折啊
代码
由于为了卡空间 STL 用的多，不开 $O2$ 会很慢
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
| #include <bits/stdc++.h>
#define fi first
#define se second
#define STC static
const short N = 2000 + 5, INF = 0x3f3f;
short n, l, r;
int top;
long long ans, sum[N];
std::bitset<N> d[N];
std::pair<short, short> stk[N * N];
bool cmn(short &x, short y){ return x > y ? x = y, true : false; }
void _work(short bit)
{
STC short f[N];
top = 0;
for (short i = 1; i <= n; ++i)
for (short j = i; j <= n; ++j) if (d[i][j] && ((sum[j] - sum[i - 1]) >> bit) & 1) stk[++top] = {i, j}, d[i][j] = 0;
if (!top) return ;
memset(f, 0x3f, sizeof f);
f[0] = 0;
for (short i = 1; i <= n; ++i)
for (short j = 0; j < i; ++j) if (d[j + 1][i] && f[j] < r) cmn(f[i], f[j] + 1);
if (f[n] <= r) return ;
for (; top; --top) d[stk[top].fi][stk[top].se] = 1;
ans |= (1ll << bit);
}
void work(short bit)
{
STC std::bitset<N> f[N];
top = 0;
for (short i = 1; i <= n; ++i)
for (short j = i; j <= n; ++j) if (d[i][j] && ((sum[j] - sum[i - 1]) >> bit) & 1) stk[++top] = {i, j}, d[i][j] = 0;
if (!top) return ;
for (short i = 0; i <= r; ++i) f[i].reset();
f[0][0] = 1;
for (short i = 1; i <= r; ++i)
{
for (short j = 1; j <= n; ++j)
for (short k = 0; k < j && !f[i][j]; ++k) if (d[k + 1][j]) f[i][j] = f[i][j] | f[i - 1][k];
if (i >= l && f[i][n]) return ;
}
for (; top; --top) d[stk[top].fi][stk[top].se] = 1;
ans |= (1ll << bit);
}
int main()
{
scanf("%hd %hd %hd", &n, &l, &r);
for (short i = 1; i <= n; ++i) scanf("%lld", &sum[i]), sum[i] += sum[i - 1];
for (short i = 1; i <= n; ++i) d[i].set();
short t = (sum[n]) ? (log2(sum[n]) + 1) : (0);
if (l != 1) for (short i = t; ~i; --i) work(i);
else for (short i = t; ~i; --i) _work(i);
printf("%lld", ans);
return 0;
}
|