打卡信奥刷题（3101）用C++实现信奥题 P7210 [COCI 2020/2021 #3] Vlak

P7210 [COCI 2020/2021 #3] Vlak题目描述Nina 和 Emilija 在纸上做游戏。刚开始纸是空白的。在一个回合里一个玩家将一个字母加入到纸上一个单词的末尾。接着二者交替顺序。规定 Nina 为先手。玩家们选择字母时必须遵循这样的原则每一次添加字母后的单词必须是该玩家最喜爱歌曲中某个单词的前缀。如果某个玩家无法继续执行她的回合那么她就输了。如果两位玩家选择的策略都是最佳的请判断谁是赢家。输入格式第一行包含一个正整数n nn表示 Nina 最喜爱歌曲中的单词数量。接下来的n nn行每一行输入 Nina 最喜爱歌曲中的一个单词。接下来的一行包含一个正整数m mm表示 Emilija 最喜爱歌曲中的单词数量。接下来的m mm行每一行输入 Emilija 最喜爱歌曲中的一个单词。输入的单词都只包含小写字母且单词长度总和不超过200000 200000200000。输出格式输出获胜的玩家Nina或Emilija。输入输出样例 #1输入 #12 aaa bbb 3 aab aba bbb输出 #1Nina输入输出样例 #2输入 #22 acg beh 2 adi bfj输出 #2Emilija输入输出样例 #3输入 #33 ja sam vlak 5 sto zgazit ce te mali输出 #3Nina说明/提示样例 1 解释如果 Nina 先写下字母b那么 Emilija 将必须写下b然后 Nina 将继续写下b。则当前的单词为bbb而 Emilija 将无法继续执行下一步因此 Nina 获胜。如果 Nina 先写下字母a那么 Emilija 将写下b。单词将变成ab因此 Nina 将无法继续执行下一步因此她将输掉。数据规模与约定对于其中40 4040分的数据单词长度总和不超过2000 20002000。对于100 % 100\%100%的数据单词长度总和不超过200000 200000200000。说明本题分值按 COCI 原题设置满分70 7070。题目译自 COCI2020-2021 CONTEST #3T2 Vlak。C实现#includebits/stdc.husingnamespacestd;intm,n;inttr[200005][30],ss;intf[200005];string s;boolb[2][200005];inlinevoidadd(string st,intbo){intsizst.size(),w0;for(intk0;ksiz;k){if(!tr[w][s[k]-a1])tr[w][s[k]-a1]ss;wtr[w][s[k]-a1];b[bo][w]1;}b[bo][w]1;}inthanshu(intu,intr){if(~f[u])returnf[u];if(r0){for(intk1;k26;k){if(!tr[u][k]||!b[0][tr[u][k]])continue;if(!hanshu(tr[u][k],1))returnf[u]0;}returnf[u]1;}else{for(intk1;k26;k){if(!tr[u][k]||!b[1][tr[u][k]])continue;if(hanshu(tr[u][k],0))returnf[u]1;}returnf[u]0;}}intmain(){memset(f,-1,sizeof(f));cinn;for(inti1;in;i)cins,add(s,0);cinm;for(inti1;im;i)cins,add(s,1);hanshu(0,0);if(!f[0])coutNina;elsecoutEmilija;return0;}后续接下来我会不断用C来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现记录日常的编程生活、比赛心得感兴趣的请关注我后续将继续分享相关内容