一种因子游戏【牛客tracker 每日一题】
一种因子游戏
时间限制：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 ） N（1≤N≤500）N（1≤N≤500），含义如上所述。
第二行N NN个以空格隔开的正整数a i （ 1 ≤ a i ≤ 500 ） a_i（1≤a_i≤500）ai（1≤ai≤500），表示A l i c e AliceAlice手中的牌。
第三行N NN个以空格隔开的正整数b i （ 1 ≤ b i ≤ 500 ） b_i（1≤b_i≤500）bi（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 n=500n=500时运算量可控，完全适配1秒时间限制。
总结
核心逻辑：将博弈胜负判定转化为互质二分图的完美匹配存在性问题，通过匈牙利算法求解最大匹配，根据匹配是否满员判定胜负。
关键操作：gcd判定连边、DFS增广匹配、匹配失败提前终止判定Alice胜。
效率保障：500节点规模的匈牙利算法实际运行效率充足，无需更复杂的网络流实现。
代码简要说明
- 邻接矩阵构建：二维数组
G[x][y]标记Alice第x张牌与Bob第y张牌是否互质，通过内置__gcd函数计算判断。 - 匈牙利DFS函数：遍历所有右部节点，若节点未访问且存在连边，则尝试匹配；若该节点未被匹配，或其原匹配点可找到新的增广路，则更新匹配关系并返回成功。
- 匹配主循环：逐个处理Alice的每张牌，重置访问数组后执行DFS增广；若任意一张牌无法匹配，直接输出
Alice并结束程序。 - 结果输出：若全部节点匹配成功，输出
Bob；否则提前输出Alice。 - 输入优化：关闭流同步并解绑tie，提升输入输出效率，适配数据规模。
代码内容
#include<bits/stdc++.h>usingnamespacestd;#defineendl'\n'typedeflonglongll;typedefunsignedlonglongull;typedefvector<vector<ll>>vvt;typedefpair<ll,ll>pll;constll N=1e3+10;constll INF=1e18;constll M=1e6+10;constll mod=1e9+7;ll n;ll A[510],B[510];boolG[510][510];ll mt[510];boolvis[510];boolDFS(ll x){for(ll y=1;y<=n;y++){if(!vis[y]&&G[x][y]){vis[y]=1;if(!mt[y]||DFS(mt[y])){mt[y]=x;return1;}}}return0;}voidsolve(){cin>>n;for(ll i=1;i<=n;i++)cin>>A[i];for(ll i=1;i<=n;i++){cin>>B[i];for(ll j=1;j<=n;j++)G[j][i]=(__gcd(A[j],B[i])==1);}for(ll i=1;i<=n;i++){memset(vis,0,sizeof(vis));if(!DFS(i)){cout<<"Alice\n";return;}}cout<<"Bob";}intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);solve();return0;}