周末偷偷看了看CSP T4，发现非常刺激，铁牌退役狗想了一中午（不过感觉比树上的树简单不少） 注意到本题中的蛇只需要最大化自己吃几个，不需要最大化排名。我们称拥有其它蛇梦寐以求的选择权利的蛇为后浪蛇（当前值最大），没有选择权利的蛇为打工蛇（当前值最小）。 考虑后浪蛇的策略：如果吃掉打工蛇，在游戏之后一定不会死，那就吃，否则就不吃。于是只需要求会不会死。 可以发现吃掉打工蛇之后，如果自己没有变成打工蛇，那么它的值一定大于之后产生的所有新蛇，于是不会死可以吃。如果吃掉后只剩下自己，也可以吃。 如果后浪蛇吃掉打工蛇后自己变成打工蛇，那么它很可能被下一个吃掉。于是只需判断下一个后浪蛇是否可以吃掉它。如果吃掉当前打工蛇，下一个后浪蛇可以吃掉自己，那么就必须停止游戏。否则就可以吃。于是可以假装吃掉了打工蛇，把问题丢给下一个后浪，递归求解。递归边界是某条后浪吃掉打工蛇后自己没有变成打工蛇。 当然其实不需要递推，开个set模拟就行。注意到模拟上述过程时间不太够，考虑用某年noip蚯蚓那个题的经典方法优化。具体来说，开两个deque，由上面的分析可知产生的新蛇一定更小，于是把初始蛇丢尽第一个队列，新产生的蛇丢进第二个队列，假装它是个set就行了。
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
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
| #include <bits/stdc++.h>
using std::cerr;
using std::endl;
inline int rd() {
int b = 0; char c = getchar();
while (!isdigit(c)) c = getchar();
while (isdigit(c)) b = b * 10 + c - '0', c = getchar();
return b;
}
const int N = 1e6 + 233;
struct Node {
int val, id;
bool operator<(Node n) const {
return val < n.val (val == n.val && id < n.id);
}
bool operator==(Node n) const {
return val == n.val && id == n.id;
}
};
int ans, n, A[N];
inline void solve(int kase) {
ans = rd();
if (kase == 1) {
n = ans;
for (int i = 1; i <= n; ++i)
A[i] = rd();
} else {
for (int i = 1; i <= ans; ++i) {
int x = rd(), y = rd();
A[x] = y;
}
}
ans = n;
std::deque<Node> que1, que2;
for (int i = 1; i <= ans; ++i)
que1.push_front({A[i], i});
while (true) {
if (que1.size() + que2.size() <= 2) {
if (que1.size() + que2.size() == 2)
--ans;
break;
}
Node min, max;
min = que1.back();
que1.pop_back();
if (que2.empty()) {
max = que1.front();
que1.pop_front();
} else {
if (que1.size() == 1 que1.front() < que2.front()) {
max = que2.front();
que2.pop_front();
} else {
max = que1.front();
que1.pop_front();
}
}
max.val -= min.val;
if (!que1.empty() && que1.back() < max) {
que2.push_back(max);
--ans;
continue;
}
int del = 0;
while (true) {
if (que1.size() + que2.size() == 1)
break;
min = max;
if (que2.empty()) {
max = que1.front();
que1.pop_front();
} else {
if (que1.size() == 1 que1.front() < que2.front()) {
max = que2.front();
que2.pop_front();
} else {
max = que1.front();
que1.pop_front();
}
}
max.val -= min.val;
if (!que1.empty() && que1.back() < max)
break;
if (!que2.empty() && que2.back() < max)
break;
del ^= 1;
}
ans -= del;
break;
}
printf("%d\n", ans);
}
int main() {
int T = rd();
for (int i = 1; i <= T; ++i)
solve(i);
return 0;
}
|