主页
搜索
最近更新
数据统计
赞助我们
系统公告
1
/
1
请查看完所有公告
ARC185A题解
最后更新于 2025-06-15 23:24:19
作者
for3to1
分类
题解
题解
AT_arc185_a
复制 Markdown
查看原文
更新内容
### Description Alice 和 Bob 手中各有 $n$ 张牌 $1,2,...,n$，从 Alice 开始轮流出牌，如果一个人出牌后场上所有的牌之和能被 $m$ 整除，则出牌者输；如果两人牌都出完后双方都未输，则 Alice 胜。问当双方都以最优策略出牌时，谁能获胜。 ### Solution 显然地，当 Alice 和 Bob 手中的牌都 $\ge 2$ 时，牌局并不会结束。所以我们直接讨论当 Alice 和 Bob 手中只剩一张牌的情况。 由于 Alice 是先手，所以当两人都只剩一张牌时，Alice 出牌。设 Bob 最后剩下的牌是 $a$，则 Alice 出牌后，场上数字和为 $n\times (n+1)-a$。若 Bob 想赢，则需 $n\times (n+1)-a \equiv 0\ \pmod m$。所以，$a=n\times (n+1)\pmod m$。 此时我们来看 Alice 如何应对。若 Alice 想获胜，则需使 Bob 不剩下数字为 $a$ 的牌。此时我们再倒退一轮，设 Alice 出完倒数第二张牌后剩下一张数字为 $b$ 的牌，则 Bob 出牌后场上的牌的数字和为 $n\times (n+1)-a-b$。因为 $n\times (n+1)-a \equiv 0\ \pmod m$ 且 $1 \le b \le n$，所以 $n\times (n+1)-a-b \equiv 0\ \pmod m$ 不成立。 由上，当 $1 \le a \le n$ 时，Bob 获胜；否则牌局结束，Alice 获胜。 ### Code ```cpp #include<bits/stdc++.h> using namespace std; #define int long long int t; signed main(){ cin>>t; while(t--){ int n,m; cin>>n>>m; if((n*(n+1))%m==0) cout<<"Alice\n"; else if((n*(n+1))%m<=n) cout<<"Bob\n"; else cout<<"Alice\n"; } return 0; } ```
正在渲染内容...
点赞
0
收藏
0
