[CSP-S2020] 贪吃蛇

前言

喜欢思维题,更喜欢做不出来但看了题解直呼妙的思维题。

但是讨厌考试时做不出来的思维题。/youl

题目

洛谷

讲解

这种题显然要先挖掘性质。

  • 性质一:如果一条蛇吃了之后不是最弱蛇,它一定吃。

证明的话稍微分类讨论一下就好了:

  1. 如果最强蛇吃了之后还是最强蛇,不吃白不吃。
  2. 最强蛇吃了之后不是最强蛇,那么次强蛇上位,次强蛇如果选择不吃,安全;次强蛇如果吃,吃的一定是次弱蛇,吃了之后一定比最强蛇吃了最弱蛇还要弱,在之后的操作中如果次强蛇会被吃,那么现在这次操作它一定会选择不吃,依然安全。

现在问题就变成最强蛇吃了最弱蛇之后自己是最弱蛇的情况了。

为了方便,我们将所有蛇按实力动态排序为 \([1,n]\)。

现在我们假设 \(n\) 吃了 \(1\),原来的 \(n\) 就变成了 \(1\) (动态更新排名),考虑 \(n-1\) 要不要吃 \(1\),如果 \(n-1\) 吃了 \(1\) 之后不是最弱蛇或者只剩一条蛇,它就会选择吃,否则我们需要假设 \(n-1\) 吃 \(1\),然后看 \(n-2\) 的抉择...

可以发现最后一定可以找到一条必吃的蛇,然后判断它和最初始的 \(n\) 的奇偶性是否相同即可判断最初的 \(n\) 是否选择吃。

用 set 模拟这个过程可以做到 \(O(Tn\log_2n)\),\(70pts\) 到账。

显然正解应该是 \(O(Tn)\) 的,题目限制提示我们应该会用到单调性,由于第二个过程可以 \(O(n)\) 实现,所以我们只需考虑优化第一个过程。

大力思考第一个过程中有什么性质。

  • 性质二:后吃的蛇一定比先吃的蛇弱。

现在我们用两个双端队列存储这些蛇,第一个存的是初始没用过餐的蛇,第二个存的是用过餐的蛇,队首弱,队尾强。

我们每次要做的是从两个队列的队尾取出一个最强的,从队列一的队首取出最弱的(由性质一+过程一可得出队列二中一定不存在最弱的),吃掉之后与次弱比较,强于次弱则直接加入队列二的队首。

在性质一的证明 2. 中我们粗略说明了最强蛇和次强蛇都吃,次强蛇一定比最强蛇弱的结论。

所以这么吃下去,用过餐的蛇一定也是单调的,但是这只说明了队列一中的蛇连续吃满足性质二,有没有可能最强蛇在队列二中,且吃了之后比当前队列二队首强呢?

不可能。

我们考虑当前队列二队首 \(h_2\) 是怎么进来的:

在 \(h_2\) 还没进来的时候,它一定是队列一队尾,它和队列二队尾 \(t_2\) 比较之后发现自己更强,于是吃掉了那个时候的最弱蛇 \(s_1\) ,可以说明没吃的时候 \(h_2\) 比 \(t_2\) 强

在 \(h_2\) 进来之后,最弱蛇 \(s_1\) 已经由之前的次弱蛇 \(s_2\) 顶替,由 \(h_2\) 强于 \(t_2\),\(s_1\) 弱于 \(s_2\) 可知此时如果 \(t_2\) 吃掉这条 \(s_2\) ,一定比 \(h_2\) 吃掉 \(s_1\) 更弱,所以吃掉之后可以直接放到队列二队首,性质二完全正确!

在过程一结束之后只需要对这两个队列进行归并排序即可做到 \(O(n)\)。

总时间复杂度 \(O(Tn)\)。

代码

其实没有想象中那么难打
//12252024832524
#include <bits/stdc++.h>
#define TT template<typename T>
using namespace std;

typedef long long LL;
const int MAXN = 1000005;
const int INF = 0x3f3f3f3f;
int n;
int a[MAXN];

LL Read()
{
	LL x = 0,f = 1; char c = getchar();
	while(c > '9' || c < '0'){if(c == '-') f = -1;c = getchar();}
	while(c >= '0' && c <= '9'){x = (x*10) + (c^48);c = getchar();}
	return x * f;
}
TT void Put1(T x)
{
	if(x > 9) Put1(x/10);
	putchar(x%10^48);
}
TT void Put(T x,char c = -1)
{
	if(x < 0) putchar('-'),x = -x;
	Put1(x); if(c >= 0) putchar(c);
}
TT T Max(T x,T y){return x > y ? x : y;}
TT T Min(T x,T y){return x < y ? x : y;}
TT T Abs(T x){return x < 0 ? -x : x;}

struct node
{
	int val,ID;
	bool operator < (const node &px)const{
		if(val^px.val) return val < px.val;
		return ID < px.ID;
	}
	node operator - (const node &C)const{
		return node{val-C.val,ID};
	}
}les[MAXN];

int main()
{
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	int T = Read();
	for(int cas = 1;cas <= T;++ cas) 
	{
		if(cas == 1)
		{
			n = Read();
			for(int i = 1;i <= n;++ i) a[i] = Read();
		}
		else 
		{
			int k = Read();
			for(int i = 1,pos;i <= k;++ i) pos = Read(),a[pos] = Read();
		}
		deque<node> q1,q2;
		for(int i = 1;i <= n;++ i) q1.push_back(node{a[i],i});
		int q1len,q2len;
		while((q1len = q1.size()) + (q2len = q2.size()) > 2)//最小的一定是q1的头,所以执行循环时q1永不空, 
		{
			if(q2len && q1.back() < q2.back())//q2大! 
			{
				node ne = q2.back() - q1.front(),se = node{INF,n+1};//new & second 
				if(q1len > 1 && q1[1] < se) se = q1[1];
				if(q2len && q2[0] < se) se = q2[0];
				if(se < ne) q2.push_front(ne),q1.pop_front(),q2.pop_back();
				else break;
			}
			else//复读机嘛 
			{
				node ne = q1.back() - q1.front(),se = node{INF,n+1};//new & second 
				if(q1len > 1 && q1[1] < se) se = q1[1];
				if(q2len && q2[0] < se) se = q2[0];
				if(se < ne) q2.push_front(ne),q1.pop_front(),q1.pop_back();
				else break;
			}
		}
		if(q1len+q2len <= 2)
		{
			Put(1,'\n');
			continue;
		}
		//归并 
		int tot = 0;
		while(!q1.empty() && !q2.empty())
			if(q1.front() < q2.front()) les[++tot] = q1.front(),q1.pop_front();
			else les[++tot] = q2.front(),q2.pop_front();
		while(!q1.empty()) les[++tot] = q1.front(),q1.pop_front();
		while(!q2.empty()) les[++tot] = q2.front(),q2.pop_front();
		int ans = tot;
		while(tot > 2) 
		{
			if(les[tot] - les[1] < les[2]) les[1] = les[tot] - les[1],--tot;
			else break;
		}
		if((tot & 1) == (ans & 1)) Put(ans-1,'\n');
		else Put(ans,'\n');
	}
	return 0;
}
上一篇:CSP-J2011模拟赛#3----考试总结


下一篇:【CCF-CSP】集合竞价