打卡信奥刷题（3279）用C++实现信奥题 P8901 [USACO22DEC] Circular Barn S

P8901 [USACO22DEC] Circular Barn S题目描述Farmer John 和他的死对头 Farmer Nhoj 在一个环形牛棚内玩游戏。牛棚内有N(1≤N≤105)N(1 \le N \le 10^5)N(1≤N≤105)个房间第iii个房间初始时内有aia_iai​头奶牛(1≤ai≤5×106)(1 \le a_i \le 5 \times 10^6)(1≤ai​≤5×106)。游戏玩法如下两位农夫将总是在同一个房间里。进入一个房间后每位农夫各执行一次行动Farmer John 在先。两位农夫在游戏开始时进入房间111。如果当前房间中的奶牛数量为零则此时执行行动的农夫即失败。否则执行行动的农夫选择一个整数PPP其中PPP为111或一个不超过当前房间中奶牛的数量的质数并从当前房间中移除PPP头奶牛。两位农夫均完成行动之后两位农夫移动到环形牛棚的下一间房间。也就是说如果农夫们在房间iii那么他们会移动到房间i1i1i1除非他们在房间NNN在这种情况下他们会移动到房间111。当两位农夫均采用最优策略时求获胜的农夫。输入格式输入包含TTT个子测试用例。输入的第一行包含T(1≤T≤1000)T(1 \le T \le 1000)T(1≤T≤1000)。下面是TTT个子测试用例。每个子测试用例的第一行包含NNN第二行包含a1,⋯ ,aNa_1, \cdots ,a_Na1​,⋯,aN​。输入保证所有NNN之和不超过2×1052 \times 10^52×105。输出格式对于每一个子测试用例输出获胜的农夫为Farmer John或Farmer Nhoj之一。输入输出样例 #1输入 #15 1 4 1 9 2 2 3 2 7 10 3 4 9 4输出 #1Farmer Nhoj Farmer John Farmer John Farmer John Farmer Nhoj说明/提示样例 1 解释对于第一个子测试用例Farmer John 可以从第一个房间中移除111、222或333头奶牛。无论他移除多少头奶牛Nhoj 都可以移除剩余的奶牛迫使 FJ 在他们绕回第一个房间时失败。对于第二个子测试用例FJ 可以移除555头奶牛迫使 Nhoj 面对剩下的444头奶牛。现在Nhoj 可以移除111、222或333奶牛。现在的情况类似于第一个子测试用例。对于第三个和第四个子测试用例FJ 可以立即移除第一个房间的所有奶牛使 Nhoj 失败。对于第五个子测试用例FJ 可以从第一个房间中移除111、222或333奶牛然后 Nhoj 可以随后移除余下的奶牛。当他们绕回第一个房间时FJ 将会失败。测试点性质测试点2−42-42−4满足N1N1N1。测试点1,2,5−71,2,5-71,2,5−7满足ai≤1000a_i \le 1000ai​≤1000。测试点8−208-208−20没有额外限制。C实现#includebits/stdc.husingnamespacestd;constintN1e510,M5e6;intT,n,x,cnt,ans,mx[4],v[M10],vis[M10],prime[M];voidget_prime(intn){vis[1]1;mx[1]1;v[1]1;for(inti2;in;i){if(!vis[i]){prime[cnt]i;mx[i%4]i;}for(intj1;jcnti*prime[j]n;j){vis[i*prime[j]]1;if(!(i%prime[j])){break;}}v[i]!(i%4)?i/2:(i-mx[i%4])/21;}}intmain(){scanf(%d,T);get_prime(M);while(T--){scanf(%d,n);ans1e9;for(inti1;in;i){scanf(%d,x);if(v[x]/2ans/2)ansv[x];}if(ans1){puts(Farmer John);}else{puts(Farmer Nhoj);}}return0;}后续接下来我会不断用C来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现记录日常的编程生活、比赛心得感兴趣的请关注我后续将继续分享相关内容