感觉是个套博弈论的数据结构题。
读完题后很好设计出一个状态，设 $f_{i,j}$ 表示当前力量为 $i$，在 $j$ 位置时是否先手必胜。可以发现第一维不会超过 $n$，则初始化为 $f_{i,n} = 1 (1 \le i \le n)$，最后的答案为 $f_{1,1}$，可以列出以下倒推的转移方程：
直接做需要枚举当前状态、下一力量和下一位置，复杂度是 $O(n^3)$，显然无法接受，所以我们需要进一步挖掘性质。
一个点 $(i,j)$ 如果是必败点，若固定 $i$，则 $(i,j + 1), (i,j + 2), \ldots, (i, j + i)$ 都是必胜点。也就是说，力量为 $i$ 的必败点的个数不超过 $O(\frac{n}{i})$ 个。不难看出总共必败点的个数由调和级数控制，也就是不会超过 $O(n \log n)$ 个。
接下来考虑如何快速找出这些必败点。倒序枚举位置 $j$。对于当前的位置 $j$，维护一个集合 $S_j$。集合中的元素是力量值，定义为：
对于当前状态 $(i,j)$，先手可以把力量变为 $[i,i+a_j]$ 的任意一个值。如果这些 $x$ 全部属于 $S_j$，那么无论先手怎么选择新的力量，后续都只能跳到必胜点，因此当前状态 $(i,j)$ 就是必败点。于是就有：
所以问题转化成动态维护集合 $S_j$，并快速判断其中是否存在长度至少为 $a_j+1$ 的连续段，这里涉及一些单点加入和删除的细节，需要小心。
假设在位置 $j$ 发现了一个新的必败点 $(i,j)$ 后，位置 $p \in [j - i, j - 1]$ 位置的力量 $i$ 均不能再属于对应的 $S_p$ 集合。所以可以用一个数组 $restore_{pos}$ 进行标记，每次的更新就是 restore[j - i - 1].push_back(i)，表示当出现一个新的必败点后，只有到位置 $j - i - 1$ 时，力量 $i$ 才能重新加入集合中。
每个必败点最多被加入和删除一次，配合 set 的实现，总时间复杂度为 $O(n \log^2 n)$。代码如下：
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
65
66
67
68
69
70
| void solve()
{
int n = read(), ans = 1;
vector <int> a(n + 1);
for (int i = 1; i <= n; ++i) a[i] = read();
vector <vector <int>> restore(n + 1);
set <pii> s;
multiset <pii> seg;
auto add_seg = [&] (int l, int r) -> void
{
if (l > r) return ;
s.insert({l, r}); seg.insert({r - l + 1, l});
};
auto del_seg = [&] (int l, int r) -> void
{
if (l > r) return;
s.erase({l, r}); seg.erase(seg.find({r - l + 1, l}));
};
auto add_point = [&] (int x) -> void
{
if (s.empty())
{
add_seg(x, x);
return;
}
auto it = s.upper_bound({x, INF});
int cur_l = x, cur_r = x;
if (it == s.begin())
{
auto [l, r] = *it;
if (x + 1 == l) del_seg(l, r), cur_r = r;
}
else
{
auto [l, r] = *prev(it);
if (x <= r) return;
if (r + 1 == x) del_seg(l, r), cur_l = l;
}
it = s.upper_bound({x, INF});
if (it != s.end())
{
auto [l, r] = *it;
if (x + 1 == l) del_seg(l, r), cur_r = r;
}
add_seg(cur_l, cur_r);
};
auto del_point = [&] (int x) -> void
{
auto it = s.upper_bound({x, INF});
assert (it != s.begin());
--it;
auto [l, r] = *it;
del_seg(l, r); add_seg(l, x - 1); add_seg(x + 1, r);
};
auto get_max = [&] () -> pii {return *prev(seg.end());};
for (int i = n - 1; i >= 1; --i)
{
for (auto v : restore[i]) add_point(v);
add_point(n - i);
while(!s.empty())
{
auto [len, l] = get_max();
if (len <= a[i]) break;
if (i == 1 && l == 1) ans = 2;
del_point(l);
if (i - l - 1 >= 1) restore[i - l - 1].push_back(l);
}
}
printf("%d\n", ans);
}
|
