P10192 [USACO24FEB] Moorbles S 题解

rhn7 · 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。