一种因子游戏时间限制1秒 空间限制256M网页链接牛客tracker牛客tracker 每日一题完成每日打卡即可获得牛币。获得相应数量的牛币能在【牛币兑换中心】换取相应奖品助力每日有题做丰盈牛币日益多题目描述A l i c e AliceAlice和B o b BobBob正在玩打牌游戏。他们两人手里各有N NN张牌每张牌上都写着一个正整数两个人都知道对方手里的所有牌上的数字。游戏规则如下每回合A l i c e AliceAlice先从自己手里剩余的牌中挑一张打出。然后B o b BobBob观察打出的牌上面的数字再从自己手里剩余的牌中挑一张打出。如果该回合中B o b BobBob打出的牌与Alice打出的牌上的数字不互质即最大公因数大于1 11则A l i c e AliceAlice获胜游戏结束否则继续进行下一回合若双方都没有牌了则B o b BobBob获胜。A l i c e AliceAlice和B o b BobBob都足够聪明。现在现在你提前得知了他们两个人手中的牌请你判断最后谁能获胜。输入描述第一行一个正整数N 1 ≤ N ≤ 500 N1≤N≤500N1≤N≤500含义如上所述。第二行N NN个以空格隔开的正整数a i ​ 1 ≤ a i ≤ 500 a_i​1≤a_i≤500ai​​1≤ai​≤500表示A l i c e AliceAlice手中的牌。第三行N NN个以空格隔开的正整数b i 1 ≤ b i ≤ 500 b_i1≤b_i≤500bi​1≤bi​≤500表示B o b BobBob手中的牌。输出描述若A l i c e AliceAlice获胜输出字符串A l i c e AliceAlice否则输出B o b BobBob。示例1输入3 1 3 15 1 3 14输出Bob解题思路本题是博弈策略 二分图完美匹配的综合应用题核心是将双方的最优博弈转化为互质配对的最大匹配问题通过匈牙利算法高效求解。博弈模型等价转化Bob获胜的充要条件是存在一种一一配对的方案使得每一对Alice的牌与Bob的牌都互质。Alice的目标在某一轮打出一张牌让Bob剩余的牌中没有能与之互质的牌直接获胜。Bob的目标全程每一轮都能选出一张互质的牌应对且每张牌仅使用一次撑到所有牌打完即获胜。该问题可严格映射为二分图匹配模型左部顶点集合为Alice的所有牌右部顶点集合为Bob的所有牌。两点之间连边当且仅当对应两个数字的最大公约数等于1互质。若该二分图存在大小为n nn的完美匹配说明Bob可以完美应对所有轮次最终Bob获胜否则Alice可以在某一轮打破局面获得胜利。由Hall定理可严格证明若不存在完美匹配则必然存在Alice的一个子集其可匹配的Bob牌数小于子集大小Alice优先打出该子集即可确保胜利。算法实现匈牙利算法采用DFS增广的匈牙利算法求解二分图最大匹配预处理邻接矩阵对每一对Alice与Bob的牌计算gcd若互质则连边。依次为每个左部节点寻找增广路通过访问标记数组避免重复遍历右部节点。若某个左部节点无法找到增广路说明最大匹配小于n nn直接判定Alice获胜。若所有左部节点都匹配成功说明存在完美匹配判定Bob获胜。算法时间复杂度为O ( n 3 ) O(n^3)O(n3)邻接矩阵实现n 500 n500n500时运算量可控完全适配1秒时间限制。总结核心逻辑将博弈胜负判定转化为互质二分图的完美匹配存在性问题通过匈牙利算法求解最大匹配根据匹配是否满员判定胜负。关键操作gcd判定连边、DFS增广匹配、匹配失败提前终止判定Alice胜。效率保障500节点规模的匈牙利算法实际运行效率充足无需更复杂的网络流实现。代码简要说明邻接矩阵构建二维数组G[x][y]标记Alice第x张牌与Bob第y张牌是否互质通过内置__gcd函数计算判断。匈牙利DFS函数遍历所有右部节点若节点未访问且存在连边则尝试匹配若该节点未被匹配或其原匹配点可找到新的增广路则更新匹配关系并返回成功。匹配主循环逐个处理Alice的每张牌重置访问数组后执行DFS增广若任意一张牌无法匹配直接输出Alice并结束程序。结果输出若全部节点匹配成功输出Bob否则提前输出Alice。输入优化关闭流同步并解绑tie提升输入输出效率适配数据规模。代码内容#includebits/stdc.husingnamespacestd;#defineendl\ntypedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvvt;typedefpairll,llpll;constll N1e310;constll INF1e18;constll M1e610;constll mod1e97;ll n;ll A[510],B[510];boolG[510][510];ll mt[510];boolvis[510];boolDFS(ll x){for(ll y1;yn;y){if(!vis[y]G[x][y]){vis[y]1;if(!mt[y]||DFS(mt[y])){mt[y]x;return1;}}}return0;}voidsolve(){cinn;for(ll i1;in;i)cinA[i];for(ll i1;in;i){cinB[i];for(ll j1;jn;j)G[j][i](__gcd(A[j],B[i])1);}for(ll i1;in;i){memset(vis,0,sizeof(vis));if(!DFS(i)){coutAlice\n;return;}}coutBob;}intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);solve();return0;}