贪吃蛇[CSP2020]

AK-dream

发布于：2020年11月12日

次浏览

题面

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

题解

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

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

70分

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

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

最终答案即为$n-t+1$，复杂度$O(Tn\log n)$

100分

如何$O(n)$把上面set求的东西求出来？

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

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

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

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

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

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

整个$n-1$轮分为两个阶段 假设第$i$轮场上最大的蛇是$A_i$，最小是$B_i$

1.$A_i\ge 2*B_i$

那么显然有$A_{i+1}\le A_i,B{i+1}\ge B_i$

假设$C_i$是$A_i$吃$B_i$得到的那条蛇，那么有$C_i\ge C_{i+1}$

当$C_i>C_{i+1}$时，队列2就是有单调性的了

当$C_i=C_{i+1}$时，一定有$A_i=A_{i+1}$，那么要不$A_i$和$A_{i+1}$两次其实都是标号相同的那条蛇(即$C_i$作为$A_{i+1}$被弹出队列2了)，要不$A_i$的标号大于$A_{i+1}$也就是说$C_i$的标号大于$C_{i+1}$，两种情况都满足队列2的单调性

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

2.$A_i<2*B_i$

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

假设第一次进入阶段2时，共有$m$条蛇，从小到大为$a_1,a_2,\cdots a_m$

那么第一次吃完后的蛇长度为$a_m-a_1<a_1$

第二次一定是$a_{m-1}-(a_m-a_1)\le a_1$

第三次是$a_{m-2}$减掉第二次得到的那个值，也是$<a_1$

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

继续推下去，易证对于所有的奇数次，有$v_i<a_1$，而偶数次有$v_i\le a_1$

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

换个说法 也就是说$A_i$在吃完$B_i$后，下一轮马上作为$B_{i+1}$被吃掉

对于偶数次$i$，若第$i+1$轮中最小蛇是$v_i$则同上

如果$v_i=a_1$并且此时有和它长度相同但编号更小的蛇呢？

假设第一次出现这种情况是在第$k$轮，$A_k$吃完$B_k$后长度变成$v_k$，由于有比$v_k$更小的作为$B_{k+1}$，那么$B_{k+1}$就一定不和$A_k$是同一条蛇了

那么只有$k+1$和$k+2$两轮的最大蛇都选择要吃时，$A_k$`才有可能在后续被吃掉

而由于$k+1$是奇数，所以如果$A_{k+2}$在第$k+2$轮选择吃的话，吃掉的一定是此时长度小于$a_1$的$A_{k+1}$

这样一来，$A_{k+1}$在$k+1$轮肯定就会选择叫停，所以 “$k+1$和$k+2$两轮的最大蛇都选择要吃” 是不可能的

所以$A_k$在后续一定不会被吃掉，它就一定会选择吃$B_k$

注意到此时$k-1$也是奇数，那么$A_{k-1}$和$B_k$就是同一条蛇，所以$A_{k-1}$在第$k-1$轮一定叫停

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

这样我们就$O(n)$算出了上面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;
}

更新于：2020年11月12日