OI - 贪吃蛇(洛谷) | Lucky_Glass's Blog

以心为名，名为爱惜

0%

OI - 贪吃蛇(洛谷)

发表于 更新于 分类于 Valine：

果然还是压轴题……

# 题面

> Linked 洛谷 P7078

点击展开/折叠 题面

有 $n$ 条蛇，每条蛇有一个体力值 $h_i$。蛇之间会发生竞争，每次竞争由 $(h_i,i)$ 最大的蛇决定，$(h_i,i)$ 最大的蛇可以选择：

  1. 停止竞争；
  2. 吃掉 $(h_j,j)$ 最小的蛇，体力变为 $h_i-h_j$；

每条蛇都希望在自己不被吃掉的前提下尽可能多地吃掉其他蛇，求每条蛇都采取最优策略时，最后会剩下多少蛇。

$n\le10^6$，保证输入的 $h_i$ 不减。

# 解析

一道博弈思想非常复杂的题……

- 小暴力

首先较简单的暴力想法就是先假设每次最大蛇都选择吃掉最小蛇，一直竞争到只剩一条。然后再从只剩一条蛇的状态倒推回来，即现在我们知道——如果第 $i$ 次竞争中，最大蛇吃掉最小蛇（转移到下一个状态），那么最终剩下的蛇有哪些。如果发现第 $i$ 次竞争后最大蛇还活着，就可以吃，否则就停止。

只需要 set 维护一下最大蛇最小蛇，做到单次 $O(n\log n)$ 的复杂度，可以得到 70pts 的好成绩~

- 正解

但是正解思路跟这个完全不一样。

先分析一个性质：

（剩下至少三条蛇）设现在 $h_i$ 的最大值、次小值和最小值分别是 $x,y,z$


若 $x-z>y$ 或 $x-z=y$ 且 x 的编号大于 y，即最大蛇吃掉最小蛇后没有变成剩下的蛇中最小的，则最大蛇一定可以吃。

简单证明如下：分析下一次竞争，记此时的最大值为 $w$，显然有 $w\le x$，此时最小值是 $y$，又有 $y\ge z$；则 $w-y\le x-z$，则下一次竞争得到的“新蛇”（带上编号考虑）一定更小；如果 $x-z$ 被吃，$w-y$ 一定会先被吃掉，于是 $w$ 此时就会选择不吃 $y$ 然后竞争结束，而 $x$ 就可以非常安全地吃掉 $z$。

下面借用博主 Resuscitate 的思路

如果最大蛇 $x$ 吃掉最小蛇 $z$ 后变成最小蛇了（情况二），则称这次竞争是一次“冒险”。如果要冒险，则必须保证冒险后竞争立即结束。

先一直模拟，直到第一次“冒险”。假设竞争还没有结束，然后继续模拟，直到某一次竞争中，最大蛇可以非常安全地吃掉最小蛇，此时最小蛇一定是上一次竞争中冒险的蛇。设这两次竞争之间一共发生了 $k$ 次冒险，则

$k$ 为偶数时，第一条将冒险的蛇会冒险，然后竞争立即结束；否则第一条将冒险的蛇直接结束竞争。

其实手玩儿一下就可以弄懂——

  • 最后一条冒险的蛇会被吃掉，所以不会冒险；
  • 倒数第二条冒险的蛇不会被吃掉（因为下一条蛇让竞争立即结束了），所以冒险；
  • 倒数第三条冒险的蛇会被倒数第二条冒险的蛇吃掉，所以不冒险；
  • ……
  • 如果 $k$ 是偶数，则第二条冒险的蛇会终止竞争，那么第一条冒险的蛇可以安全地冒险；否则第一条蛇直接结束竞争。

于是我们只需要在模拟的时候维护 $k$ 和第一次冒险时已经有多少条蛇被吃掉即可。

还有个问题是怎么 $O(n)$ 模拟。注意到，对于最大蛇可以安全吃掉最小蛇的情况一，有 $x-z\ge w-y$，即新产生的蛇的体力值单调不增。可以想到用两个队列分别维护原有的蛇和新产生的蛇。

情况一可以满足两个队列都单调，但是情况二能否单调？实际上如果带编号考虑的确不单调，但是我们发现情况二不需要考虑编号——

设第一次冒险时的体力值从小到大排列为 $\{h_1,h_2,\dots,h_n\}$，则有 $h_n-h_1<h_2$。暴力模拟竞争过程

  1. $h_n\to h_n-h_1$ 一定变为最小蛇，则 $\{h_n-h_1,h_2,\dots,h_{n-1}\}$；
  2. $h_{n-1}\to h_{n-1}-h_n+h_1$，$(h_{n-1}-h_n)+h_1\le h_1\le h_2$，在数值上一定等于最小蛇；
  3. $h_{n-2}\to (h_{n-2}-h_{n-1})+(h_n-h_1)<h_2$，一定是最小蛇；
  4. ……

于是在数值的意义上是单调的，因此可以用队列维护。

# 源代码

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
105
106
107
108
109
110
111
112
113
114
115
116
117
118
/*Lucky_Glass*/
#include<queue>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

typedef pair<int,int> pii;
const int N=1e6+10,INF=0x3f3f3f3f;

int n,cas;
int num[N];

//STL的deque会被卡常……
struct DEQUE{
	pii ary[N<<1];
	int le,ri;
	DEQUE(){clear();}
	void clear(){le=N+1,ri=N;}
	bool empty(){return le>ri;}
	void push_back(pii x){ary[++ri]=x;}
	void pop_back(){ri--;}
	void push_front(pii x){ary[--le]=x;}
	void pop_front(){le++;}
	pii front(){return ary[le];}
	pii back(){return ary[ri];}
};

DEQUE org,mdi;

inline int Read(int &r){
	int b=1,c=getchar();r=0;
	while(c<'0' || '9'<c) b=c=='-'? -1:b,c=getchar();
	while('0'<=c && c<='9') r=(r<<1)+(r<<3)+(c^'0'),c=getchar();
	return r*=b;
}
pii PopFront(){
	pii ret;
	bool tmp=false;
	if(org.empty()) tmp=false;
	else if(mdi.empty()) tmp=true;
	else tmp=org.front()<mdi.front();
	if(tmp) ret=org.front(),org.pop_front();
	else ret=mdi.front(),mdi.pop_front();
	return ret;
}
pii PopBack(){
	pii ret;
	bool tmp=false;
	if(org.empty()) tmp=false;
	else if(mdi.empty()) tmp=true;
	else tmp=org.back()>mdi.back();
	if(tmp) ret=org.back(),org.pop_back();
	else ret=mdi.back(),mdi.pop_back();
	return ret;
}
pii Front(){
	if(org.empty()) return mdi.front();
	else if(mdi.empty()) return org.front();
	else return min(mdi.front(),org.front());
}
pii Back(){
	if(org.empty()) return mdi.back();
	else if(mdi.empty()) return org.back();
	else return max(mdi.back(),org.back());
}
bool Empty(){return org.empty() && mdi.empty();}
pii operator -(pii mx,pii mn){return make_pair(mx.first-mn.first,mx.second);}

void Solve(){
	int tim=0,rem=-1,ris=0;
	while((++tim)<=n-1){
		if(org.empty()) swap(org,mdi);
		pii mn=PopFront(),mx=PopBack(),now=mx-mn;
		if(Empty() || now>Front()){
			//吃掉后不是最小蛇，则一定可以不被吃掉
			if(~rem){
				//如果有蛇冒险，则最后一条冒险的蛇一定被吃掉
				//所以最后一条冒险的蛇不会冒险
				//倒数第二条冒险的蛇就不会被吃掉，选择冒险
				//倒数第三条冒险的蛇一定会被吃掉，不冒险
				//...
				//如果冒险的蛇有奇数条，第一条将要冒险的蛇就不会冒险，被吃的蛇的个数为 rem-1
				printf("%d\n",n-rem+(ris&1));
				return;
			}
		}
		else{ //“冒险”
			if(rem==-1) rem=tim; //存储第一次“冒险”前被吃了多少蛇
			ris++; //“冒险”总次数
		}
		mdi.push_front(now);
	}
	printf("1\n");
}
int main(){
	Read(cas);
	bool fir=true;
	while(cas--){
		if(fir){
			Read(n);
			for(int i=1;i<=n;i++)
				Read(num[i]);
			fir=false;
		}
		else{
			int tmp;Read(tmp);
			for(int i=1,p,q;i<=tmp;i++)
				Read(p),Read(q),num[p]=q;
		}
		org.clear(),mdi.clear();
		for(int i=1;i<=n;i++)
			org.push_back(make_pair(num[i],i));
		Solve();
	}
	return 0;
}

THE END

Thanks for reading!

> Linked 听闻-网易云