P10192 [USACO24FEB] Moorbles S题目描述Bessie 和 Elsie 正在玩弹珠游戏。游戏的玩法如下Bessie 和 Elsie 开始时各有一定数量的弹珠。Bessie 取出AAA个弹珠放在蹄子下Elsie 猜测AAA是偶数还是奇数。如果 Elsie 猜对了她从 Bessie 那里赢得AAA个弹珠如果她猜错了她输给 BessieAAA个弹珠如果 Elsie 有少于AAA个弹珠她就会输掉所有弹珠。一名玩家失去所有弹珠时即失败。游戏进行了一定回合后Elsie 拥有NNN1≤N≤1091\le N\le 10^91≤N≤109个弹珠。她感觉获胜很难但她只是想不要输。在与 Bessie 玩得足够久之后Elsie 对 Bessie 的习惯有了很好的了解她发现在回合iiiBessie 只可能会取出KKK1≤K≤41\le K\le 41≤K≤4种不同数量的弹珠。距离 Bessie 感到无聊退出游戏只有MMM1≤M≤3⋅1051\le M\le 3\cdot 10^51≤M≤3⋅105个回合了。你能求出一个字典序最小的行动序列使得无论 Bessie 如何选择Elsie 都不会输吗输入格式输入的第一行包含一个整数TTT1≤T≤101\le T\le 101≤T≤10为测试用例的数量。每个测试用例的描述如下第一行包含三个整数NNNMMM和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输入 #12 10 3 2 2 5 1 3 1 3 10 3 3 2 7 5 8 3 4 2 5 6输出 #1Even Even Odd -1输入输出样例 #2输入 #21 20 8 2 3 5 3 5 3 5 3 5 3 5 3 5 3 5 3 5输出 #2Even 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 OddBessie 无法以其他的方式赢走 Elsie 的所有弹珠。在第二个测试用例中可以证明对于 Elsie 可以选择的任何行动顺序Bessie 都存在一种方式可以赢走 Elsie 的所有弹珠。测试点性质测试点333M≤16M\le 16M≤16。测试点4−64-64−6M≤1000M\le 1000M≤1000。测试点7−127-127−12没有额外限制。C实现#includebits/stdc.h#defineintlonglongusingnamespacestd;intT,n,m,k,a[300005],b[300005],dp[300005],suf[300005];boolans[300005];signedmain(){cinT;while(T--){cinnmk;for(inti1;im;i)a[i]b[i]-1e18;for(intj1;jm;j){for(inti1,x;ik;i){cinx;if(x%20)b[j]max(b[j],-x),a[j]max(a[j],x);elsea[j]max(a[j],-x),b[j]max(b[j],x);}}intsumn;for(inti1;im;i){if(a[i]b[i])sum-b[i],ans[i]0;elsesum-a[i],ans[i]1;if(sum0)break;dp[i]sum;}if(sum0){cout-1endl;continue;}suf[m]dp[m];for(intim-1;i1;i--)suf[i]min(suf[i1],dp[i]);inttot0;for(inti1;im;i){if(ans[i]0)continue;inttmpsuf[i]tot;tmptmp-b[i]a[i];if(tmp0)tot-b[i]a[i],ans[i]0;}for(inti1;im;i){if(ans[i])coutOdd ;elsecoutEven ;}puts();}return0;}后续接下来我会不断用C来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现记录日常的编程生活、比赛心得感兴趣的请关注我后续将继续分享相关内容