自动搬运

查看原文

来自洛谷，原作者为

	rhn7 洛谷用户数：1789309

搬运于2025-08-24 22:55:37，当前版本为作者最后更新于2024-03-05 21:27:28，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

话说这次银组前两题难度堪比铂金

考虑最坏情况，Elsie 猜偶数时 Bessie 拿出的是最大的奇数，没有奇数拿出的就是最小的偶数，Elsie 猜奇数时 Bessie 拿出的是最大的偶数，没有偶数拿出的就是最小的奇数。

我们设第 $i$ 轮 Elsie 猜偶数最多亏 $e_i$，猜奇数最多亏 $o_i$。

求字典序最小是一个简单贪心。对于每轮，如果出偶数能保证后面不输，就出偶数，否则出奇数。

关键是怎么判断后面不输，很容易想到对 $\min(e,o)$ 求后缀和，看其是否小于当前弹珠个数。

这样做过不了样例二，原因是题目要求任意时刻都有弹珠，上述方法只判断了最后时刻是否有弹珠，所以要看亏的最大的时刻有没有亏光，即对 $\min(e,o)$ 求以 $i$ 为开头的最大子段和。

代码如下：

#include<bits/stdc++.h>
#define rd(x) scanf("%lld",&x)
using namespace std;
typedef long long ll;
const ll N=3e5+5;
ll T,n,m,k,x,e[N],o[N],f[N];
void solve(){
	rd(n);rd(m);rd(k);f[m+1]=0;
	for(ll i=1;i<=m;i++){
		ll m1=1e15,m2=1e15;o[i]=e[i]=0;
		for(ll j=1;j<=k;j++){
			rd(x);
			if(x&1) m1=min(m1,x),e[i]=max(e[i],x); 
			else m2=min(m2,x),o[i]=max(o[i],x);
		}
		if(e[i]==0) e[i]=-m2;if(o[i]==0) o[i]=-m1;
	}
	for(ll i=m;i>=1;i--) f[i]=max(0ll,f[i+1])+min(e[i],o[i]);//DP过程 
	if(f[1]>=n) return printf("-1"),void();//注意无解的判断 
	for(ll i=1;i<=m;i++){
		if(n-e[i]>f[i+1]&&n>e[i])printf("Even"),n-=e[i];//f[i+1]可能<0，所以要判断 n>e[i]
		else printf("Odd"),n-=o[i];
		if(i<m) printf(" ");
	}
}
int main(){rd(T);while(T--) solve(),printf("\n");}

本蒟蒻赛时脑残把 f[i]=max(0ll,f[i+1])+min(e[i],o[i]); 写成了 f[i]=max(0ll,f[i+1]+min(e[i],o[i]));，由于数据水居然过了，求大佬 hack。