查网站服务器速度,江苏成章建设集团有限公司官方网站,浙江做网站的公司,wordpress nginx 502题目大意 Alice \text{Alice} Alice和 Bob \text{Bob} Bob在玩一个游戏#xff1a;有一个由正整数组成的集合 S S S#xff0c;两人轮流从中选数#xff0c; Alice \text{Alice} Alice先手。每次一个人可以从当前集合中选一个数 x x x#xff0c;把 x x x以及 x x x在集合中…题目大意 Alice \text{Alice} Alice和 Bob \text{Bob} Bob在玩一个游戏有一个由正整数组成的集合 S S S两人轮流从中选数 Alice \text{Alice} Alice先手。每次一个人可以从当前集合中选一个数 x x x把 x x x以及 x x x在集合中所有的因数从集合中删除注意 x x x必须在集合中。当一个人无法选数也就是集合为空时这个人就输了。问一开始集合为 { x ∣ 1 ≤ x ≤ n , ϕ ( x ) ≤ m } \{x|1\leq x\leq n,\phi(x)\leq m\} {x∣1≤x≤n,ϕ(x)≤m}时当双方都采用最优策略时谁会获胜。
如果 Alice \text{Alice} Alice会获胜则输出 Alice \text{Alice} Alice否则输出 Bob \text{Bob} Bob。 1 ≤ n ≤ 100 , 0 ≤ m ≤ n 1\leq n\leq 100,0\leq m\leq n 1≤n≤100,0≤m≤n 题解
如果初始集合为空即 m 0 m0 m0则后手胜。
如果初始集合非空的话则 1 1 1一定在集合中。我们考虑先手不选 1 1 1的话能否获胜。
如果先手不选 1 1 1能获胜则先手必胜如果先手不选 1 1 1必败那么先手就选 1 1 1给后手留下了一个不能选 1 1 1的必败的局面
你也许会觉得一开始不能选 1 1 1的局面中有 1 1 1但先手选 1 1 1之后留下的局面没有 1 1 1了两个局面不一样所以前一个必败不能说明后一个必败。但是这两个局面的前提都是不能选 1 1 1而且不管选什么 1 1 1都会被删除后面同样也不能选 1 1 1所以两个局面是等价的。
也就是说如果 m 0 m0 m0则输出 Bob \text{Bob} Bob否则输出 Alice \text{Alice} Alice。
code
#includebits/stdc.h
using namespace std;
int n,m;
int main()
{
// freopen(game.in,r,stdin);
// freopen(game.out,w,stdout);scanf(%d%d,n,m);if(m0) printf(Bob\n);else printf(Alice\n);return 0;
}
