周末偷偷看了看CSP T4,发现非常刺激,铁牌退役狗想了一中午(不过感觉比树上的树简单不少)
注意到本题中的蛇只需要最大化自己吃几个,不需要最大化排名。我们称拥有其它蛇梦寐以求的选择权利的蛇为后浪蛇(当前值最大),没有选择权利的蛇为打工蛇(当前值最小)。
考虑后浪蛇的策略:如果吃掉打工蛇,在游戏之后一定不会死,那就吃,否则就不吃。于是只需要求会不会死。
可以发现吃掉打工蛇之后,如果自己没有变成打工蛇,那么它的值一定大于之后产生的所有新蛇,于是不会死可以吃。如果吃掉后只剩下自己,也可以吃。
如果后浪蛇吃掉打工蛇后自己变成打工蛇,那么它很可能被下一个吃掉。于是只需判断下一个后浪蛇是否可以吃掉它。如果吃掉当前打工蛇,下一个后浪蛇可以吃掉自己,那么就必须停止游戏。否则就可以吃。于是可以假装吃掉了打工蛇,把问题丢给下一个后浪,递归求解。递归边界是某条后浪吃掉打工蛇后自己没有变成打工蛇。
当然其实不需要递推,开个set模拟就行。注意到模拟上述过程时间不太够,考虑用某年noip蚯蚓那个题的经典方法优化。具体来说,开两个deque,由上面的分析可知产生的新蛇一定更小,于是把初始蛇丢尽第一个队列,新产生的蛇丢进第二个队列,假装它是个set就行了。
#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;
}
orz
orz
@邓鸽鸽高考加油啊
大专挺好的