ErikTse Runtime

  • 首页 / Home
  • | 算法学习 / Algorithm
    • 所有 / All
    • 简单 / Easy
    • 中等 / Medium
    • 困难 / Hard
  • | 技术分享 / Technology
    • 所有 / All
    • 网络技术 / NetWork
    • 资源共享 / Resource
    • 项目实践 / Event
  • ETOJ在线评测系统
Keep Going.
温故而知新.
  1. 首页
  2. 算法学习
  3. 中等
  4. 正文

[杭电多校7 | HDUOJ7216]Triangle Game(Nim博弈)

2022年8月9日 171点热度 0人点赞 0条评论

题目传送门:Problem - 7216 (hdu.edu.cn)

题意 / Problem

两个人玩游戏,给定3个数字,分别表示一个三角形的三条边,双方轮流进行一次操作,将三条边的其中一条减去一个正整数的长度,且使得新的三个数依然可以组成三角形。当无法操作时就输了。

思路 / Thought

先将结论,当(a - 1) ^ (b - 1) ^ (c - 1)不为0时必胜,否则必败。

典型的Nim博弈,可以分为两个状态,我将其设为W态和L态。

  • W态:\( (a-1)\oplus (b-1)\oplus (c-1) \ne 0 \)
  • L态:\( (a-1)\oplus (b-1)\oplus (c-1) = 0 \)

现在来证明:

不妨设\( a <= b <= c \)。非退化三角形的定义为\( a + b > c \),即\( (a-1) + (b-1) \ge (c-1) \)。(上面的状态公式是从这里分析出来的,利用了异或的性质\(a + b = 2 * (a \& b) + a \oplus b \ge a \oplus b\))

当选手处于L态时,由于\( (a-1)\oplus (b-1) \oplus (c-1) = 0 \),所以\( (a-1) \oplus (b - 1) = (c - 1) \Rightarrow (a-1)+(b-1) \ge (a-1)\oplus(b-1) = (c-1) \),所以L态一定为非退化三角形。

此时又分为两种情况:

  • \( a = 1\)时,\( b = c \),此时为必败态,无法操作。
  • \( a > 1\)时,此时一定存在一种方案使得某个长度减小后使得状态变为W态。

当选手处于W态时,不妨设\( (a-1)\oplus (b-1)\oplus(c-1) = r\),那么在\((a-1), (b-1), (c-1)\)这三个数当中必然存在一个数字的二进制最高位与r的二进制最高位相同,也就是说这三个数中存在一个数 \(k\) 异或\(r\)后变小,即\(k \oplus r < k\),因为二进制位的最高位从1异或1变为0了,后面的位数不管多大也比之前的小咯。

所以找出这个\(k\)并将其异或\(r\),等价于减少的操作,此时因为异或了一个\(r\),导致状态从W到了L,也就是\((a-1)\oplus(b-1)\oplus(c-1)\oplus r = 0\)。

所以状态L可以变为必败态或状态W,状态W可以变为状态L,也就是说如果一开始是状态W就直接赢,一开始是状态L最后只能输。

代码 / Code

#include <bits/stdc++.h>
#define int long long
using namespace std;

void solve()
{
	int a, b, c;cin >> a >> b >> c;
	cout << (((a - 1) ^ (b - 1) ^ (c - 1)) ? "Win" : "Lose") << '\n';
}

signed main()
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	
	int _;cin >> _;
	while(_ --)solve();
	return 0;
}
本作品采用 知识共享署名-非商业性使用 4.0 国际许可协议 进行许可
标签: C++ Nim博弈 博弈论 思维 算法竞赛
最后更新:2022年8月24日

Eriktse

18岁,性别未知,ACM-ICPC现役选手,ICPC亚洲区域赛银牌摆烂人,CCPC某省赛铜牌蒟蒻,武汉某院校计算机科学与技术专业本科在读。

点赞
< 上一篇
下一篇 >

文章评论

取消回复

Eriktse

18岁,性别未知,ACM-ICPC现役选手,ICPC亚洲区域赛银牌摆烂人,CCPC某省赛铜牌蒟蒻,武汉某院校计算机科学与技术专业本科在读。

文章目录
  • 题意 / Problem
  • 思路 / Thought
  • 代码 / Code

友情链接 | 站点地图

COPYRIGHT © 2022 ErikTse Runtime. ALL RIGHTS RESERVED.

Theme Kratos | Hosted In TENCENT CLOUD

赣ICP备2022001555号-1

赣公网安备 36092402000057号