题面

https://www.luogu.com.cn/problem/P7078

题解

考场上开T4的时候只有40~50分钟了 努力思索了10分钟想到一个结论(中途想假了一次)

然后发现部分分还挺多:70分

70分

简单说说70分做法:先假设游戏一直进行,那么就可以用set把每轮游戏是谁吃谁处理出来

显然游戏共有轮,从最后一轮开始向前扫,假设当前到第轮,是吃掉,记为第轮中第一次有蛇叫停是在第几轮(初始时$t=n$),同时记录表示若游戏一直进行则第条蛇在第轮被吃掉,那么如果就表示如果这一轮吃了,那它在后面一定会被吃掉,所以必须叫停,更新,否则不更新

最终答案即为,复杂度

100分

如何把上面set求的东西求出来?

这题的做法和NOIP2016蚯蚓比较像,通过维护多个普通队列来存取最小/最大值

具体地说,维护两个普通队列,一个初始时装着排好序的所有元素,一个初始为空

每次操作时,分别找出两个队列的队头元素,取其中较小者即是当前的最小元素,最大元素同理取队尾

然后把最大减最小的那个元素放到第二个队列的队头

只要两个队列都具有单调性,这个做法就是对的

显然只出不进的队列1时刻具有单调性 考虑队列2

整个轮分为两个阶段 假设第轮场上最大的蛇是,最小是

1.

那么显然有

假设得到的那条蛇,那么有

时,队列2就是有单调性的了

时,一定有,那么要不两次其实都是标号相同的那条蛇(即作为被弹出队列2了),要不的标号大于也就是说的标号大于,两种情况都满足队列2的单调性

至此证明了阶段1中队列2是有单调性的

2.

第一次满足这个条件时,看作是进入了阶段2

假设第一次进入阶段2时,共有条蛇,从小到大为

那么第一次吃完后的蛇长度为

第二次一定是

第三次是减掉第二次得到的那个值,也是

假设第次减出来的值是,由于队列1中已没有长度小于的蛇,不难看出第次的最短蛇的长度一定是(但是编号不一定相同)

继续推下去,易证对于所有的奇数次,有,而偶数次有

对于奇数次,第轮中最小值必然是,那么就相当于进入队列2后又马上被弹出了,依然不影响队列2单调性

换个说法 也就是说在吃完后,下一轮马上作为被吃掉

对于偶数次,若第轮中最小蛇是则同上

如果并且此时有和它长度相同但编号更小的蛇呢?

假设第一次出现这种情况是在第轮,吃完后长度变成,由于有比更小的作为,那么就一定不和是同一条蛇了

那么只有两轮的最大蛇都选择要吃时,$A_k$`才有可能在后续被吃掉

而由于是奇数,所以如果在第轮选择吃的话,吃掉的一定是此时长度小于

这样一来,轮肯定就会选择叫停,所以 “两轮的最大蛇都选择要吃” 是不可能的

所以在后续一定不会被吃掉,它就一定会选择吃

注意到此时也是奇数,那么就是同一条蛇,所以在第轮一定叫停

写了这么多,就是为了证明出现这种情况时,游戏在第轮就一定会终止,那么就从第轮往回扫就行了

这样我们就算出了上面set算的东西,然后再套用上面的70分做法即可

代码

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
#include <bits/stdc++.h>
#define N 1000005
#define mp make_pair
#define fi first
#define se second
using namespace std;
typedef pair<int, int> pii;

template <typename T>
inline void read(T &num) {
T x = 0; char ch = getchar();
for (; ch > '9' || ch < '0'; ch = getchar());
for (; ch <= '9' && ch >= '0'; ch = getchar()) x = (x << 3) + (x << 1) + (ch ^ '0');
num = x;
}

const int inf = 0x3f3f3f3f;
int ttt, n, k;
int a[N], b[N], c[N], eaten[N], h1, t1, h2, t2;
pii q1[N], q2[N];

inline pii getmn() {
if ((h2 > t2) || (h1 <= t1 && q1[t1] < q2[t2])) return q1[t1--];
else return q2[t2--];
}
inline pii getmx() {
if ((h2 > t2) || (h1 <= t1 && q1[h1] > q2[h2])) return q1[h1++];
else return q2[h2++];
}

void calc(int st) {
memset(eaten, 0, sizeof(eaten));
int ans = st + 1;
for (int i = st; i; i--) {
eaten[c[i]] = i;
if (eaten[b[i]] && eaten[b[i]] < ans) {
ans = i;
}
}
printf("%d\n", n - ans + 1);
}

void solve() {
h1 = h2 = 1; t1 = t2 = 0;
bool flag = 0;
for (int i = n; i; i--) q1[++t1] = mp(a[i], i);
for (int i = 1; i < n; i++) {
pii mx = getmx(), mn = getmn();
pii nowmn = min(h1<=t1?q1[t1]:mp(inf, inf), h2<=t2?q2[t2]:mp(inf, inf));
pii now = mp(mx.fi-mn.fi, mx.se);
b[i] = mx.se; c[i] = mn.se;
if (now < nowmn) flag = 1;
if (flag && now >= nowmn) {
calc(i-2); return;
}
q2[++t2] = now;
}
calc(n-1);
}

int main() {
read(ttt); ttt--;
read(n);
for (int i = 1; i <= n; i++) read(a[i]);
solve();
for (int i = 1; i <= ttt; i++) {
read(k);
for (int j = 1, x, y; j <= k; j++) {
read(x); read(y);
a[x] = y;
}
solve();
}
return 0;
}

评论