打卡信奥刷题（3427）用C++实现信奥题 P10192 [USACO24FEB] Moorbles S

P10192 [USACO24FEB] Moorbles S

题目描述

Bessie 和 Elsie 正在玩弹珠游戏。游戏的玩法如下：Bessie 和 Elsie 开始时各有一定数量的弹珠。Bessie 取出AAA个弹珠放在蹄子下，Elsie 猜测AAA是偶数还是奇数。如果 Elsie 猜对了，她从 Bessie 那里赢得AAA个弹珠，如果她猜错了，她输给 BessieAAA个弹珠（如果 Elsie 有少于AAA个弹珠，她就会输掉所有弹珠）。一名玩家失去所有弹珠时即失败。

游戏进行了一定回合后，Elsie 拥有NNN（1≤N≤1091\le N\le 10^91≤N≤109）个弹珠。她感觉获胜很难，但她只是想不要输。在与 Bessie 玩得足够久之后，Elsie 对 Bessie 的习惯有了很好的了解，她发现在回合iii，Bessie 只可能会取出KKK（1≤K≤41\le K\le 41≤K≤4）种不同数量的弹珠。距离 Bessie 感到无聊退出游戏只有MMM（1≤M≤3⋅1051\le M\le 3\cdot 10^51≤M≤3⋅105）个回合了。你能求出一个字典序最小的行动序列，使得无论 Bessie 如何选择，Elsie 都不会输吗？

输入格式

输入的第一行包含一个整数TTT（1≤T≤101\le T\le 101≤T≤10），为测试用例的数量。每个测试用例的描述如下：

• 第一行包含三个整数NNN，MMM和KKK，分别表示 Elsie 拥有的弹珠数量，回合数及 Bessie 可能进行的选择数。
• 以下MMM行，第iii行包含KKK个不同的空格分隔的整数ai,1ai,2…ai,Ka_{i,1}a_{i,2}\ldots a_{i,K}ai,1​ai,2​…ai,K​（1≤ai,j≤1031\le a_{i,j}\le10^31≤ai,j​≤103），表示 Bessie 在回合iii可能取出的弹珠数量。

输入保证所有测试用例的MMM之和不超过3⋅1053\cdot 10^53⋅105。

输出格式

对于每一个测试用例，输出 Elsie 保证不输的字典序最小的行动序列，或者如果她会输则输出−1−1−1。行动序列输出在一行中，包含MMM个空格分隔的单词，每个单词为Even（偶）或Odd（奇）。

注意：Even的字典序小于Odd。

输入输出样例 #1

输入 #1

2 10 3 2 2 5 1 3 1 3 10 3 3 2 7 5 8 3 4 2 5 6

输出 #1

Even Even Odd -1

输入输出样例 #2

输入 #2

1 20 8 2 3 5 3 5 3 5 3 5 3 5 3 5 3 5 3 5

输出 #2

Even Even Even Odd Even Odd Even Odd

说明/提示

样例解释 1

在第一个测试用例中，唯一字典序更小的行动序列是Even Even Even，但 Bessie 可以使 Elsie 输，通过先出555，将 Elsie 的弹珠数量从101010减少到555，然后再出333，将 Elsie 的弹珠数量从555减少到222，然后出333，这会输光她所有的弹珠。

如果 Elsie 采用正确的行动序列Even Even Odd，那么如果 Bessie 以同样的方式进行游戏，最后当她出333时，Elsie 将获得那333个弹珠，将她的弹珠数量增加到555。可以进一步证明，只要 Elsie 操作是Even Even Odd，Bessie 无法以其他的方式赢走 Elsie 的所有弹珠。

在第二个测试用例中，可以证明，对于 Elsie 可以选择的任何行动顺序，Bessie 都存在一种方式可以赢走 Elsie 的所有弹珠。

测试点性质

• 测试点333：M≤16M\le 16M≤16。
• 测试点4−64-64−6：M≤1000M\le 1000M≤1000。
• 测试点7−127-127−12：没有额外限制。

C++实现

#include<bits/stdc++.h>#defineintlonglongusingnamespacestd;intT,n,m,k,a[300005],b[300005],dp[300005],suf[300005];boolans[300005];signedmain(){cin>>T;while(T--){cin>>n>>m>>k;for(inti=1;i<=m;i++)a[i]=b[i]=-1e18;for(intj=1;j<=m;j++){for(inti=1,x;i<=k;i++){cin>>x;if(x%2==0)b[j]=max(b[j],-x),a[j]=max(a[j],x);elsea[j]=max(a[j],-x),b[j]=max(b[j],x);}}intsum=n;for(inti=1;i<=m;i++){if(a[i]>b[i])sum-=b[i],ans[i]=0;elsesum-=a[i],ans[i]=1;if(sum<=0)break;dp[i]=sum;}if(sum<=0){cout<<-1<<endl;continue;}suf[m]=dp[m];for(inti=m-1;i>=1;i--)suf[i]=min(suf[i+1],dp[i]);inttot=0;for(inti=1;i<=m;i++){if(ans[i]==0)continue;inttmp=suf[i]+tot;tmp=tmp-b[i]+a[i];if(tmp>0)tot+=-b[i]+a[i],ans[i]=0;}for(inti=1;i<=m;i++){if(ans[i])cout<<"Odd"<<' ';elsecout<<"Even"<<' ';}puts("");}return0;}

后续

接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容