「postOI」Colouring Game
2022/9/5 23:25:42
本文主要是介绍「postOI」Colouring Game,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
题意
有 \(n\) 个格子排成一行,一开始每个格子上涂了蓝色或红色。
Alice 和 Bob 用这些格子做游戏。Alice 先手,两人轮流操作:
- Alice 操作时,选择两个相邻的格子,其中至少要有一个红色格子,然后把这两个格子涂成白色;
- Bob 操作时,选择两个相邻的格子,其中至少要有一个蓝色格子,然后把这两个格子涂成白色。
注意白色的格子也可以被选中,只要满足“至少一个红/蓝色格子”的条件。当轮到一方操作,但该方无法进行操作时,另一方获胜。
如果两人都采取最优策略,谁会获胜?
\(n \le 5 \times 10^5\)。
解析
首先贪心地想,两人会采取什么策略?不妨把游戏看成一个“轮次”的游戏,红色格子是 A 的轮次,蓝色格子是 B 的轮次。显然双方都想让自己的轮次尽可能多,对方尽可能少。由于每次操作至少选择一个己方的颜色,所以每轮会至少消耗一个己方轮次。
- 如果是两个己方颜色,则会消耗两个己方轮次,显然不优;
- 如果是己方颜色和白色,则只消耗一个己方轮次;
- 如果是己方颜色和对方颜色,则不仅只消耗一个己方轮次,还会减少一个对方轮次,应该是比较优的策略。
换句话说,会优先选策略三;然后会选择策略二;最后,其实容易发现除非全是红色,否则不会用到策略一,因为可以替代成两次策略二。
于是只考虑策略二三。观察策略的特点,当两人都在采取策略三时,两人的轮次差是不变的,而采取策略二时:
- 如果两人剩余轮次数不同,则剩余轮次多的人获胜;
- 如果两人剩余轮次数相同,则后手获胜,或者说,取走最后一个
RB
或BR
的一方获胜。
于是我们可以判断:
- 如果两种颜色的数量不同,则较多的颜色对应的玩家必胜;
- 如果两种颜色相同,则取走最后一个
RB
或BR
的一方获胜。
第二种情况如何考虑?既然只需要考虑 RB
和 BR
,我们可以简化字符串,简化后就是 RBRBRBR...
。只是这样一段 RB 交替的串吗?也可以几个串连起来(用 |
划分串)RBR|RBRB|BRB
。注意到采取策略三时,我们不可能跨串选择格子(因为这样的两个格子是同色的),于是每个串是独立的子游戏。
“独立的子游戏”?nim游戏?SG函数?尝试用 SG 函数解题。那么整个游戏的 SG 值是每个串的 SG 值的异或和。
考虑一个串的 SG 值,由于是 RB 交替的,我们发现这个串里 R 多还是 B 多其实没有影响(比如 RBR
和 BRB
其实没有区别),这样一来,一个串就可以用其长度代替了。记 \(SG(i)\) 表示长度为 \(i\) 的串的 SG 值,考虑选择 \(i, i + 1\) 两个格子,会将串分成两个长度分别为 \(i - 1, n - i - 1\) 的两个串,而这两个串又互不影响了,转移到的状态的 SG 值就是这两个串的 SG 值异或,则
这样我们可以 \(O(n^2)\) 计算 \(SG(n)\)。但这样显然不够……怎么优化?不能优化?那把表打出来看看……好像是以 \(34\) 为周期?除了前 \(68\) 个,剩下的以 \(34\) 为周期,于是可以先暴力算出 \(SG(0 \sim 1000)\),然后按周期推 \(SG(0 \sim n)\)。
代码
#include <cstdio> #include <cstring> #include <algorithm> const int MAXN = 5e5 + 10; char col[MAXN]; int sg[MAXN]; bool tmp_is_exi[1005]; void calcSg() { sg[0] = 0; for (int n = 1; n <= 1000; ++n) { memset(tmp_is_exi, 0, sizeof tmp_is_exi); for (int i = 1; i < n; ++i) { tmp_is_exi[sg[i - 1] ^ sg[n - i - 1]] = true; } for (int i = 0; ; ++i) { if (!tmp_is_exi[i]) { sg[n] = i; break; } } } for (int i = 1001; i < MAXN; ++i) { sg[i] = sg[i - 34]; } } bool solveCase() { int len; scanf("%d%s", &len, col + 1); int cnt_red = 0; for (int i = 1; i <= len; ++i) { cnt_red += col[i] == 'R'; } if (cnt_red != len - cnt_red) { return cnt_red > len - cnt_red; } int las = 1, overall_sg = 0; for (int i = 1; i < len; ++i) { if (col[i] == col[i + 1]) { overall_sg ^= sg[i - las + 1]; las = i + 1; } } overall_sg ^= sg[len - las + 1]; return overall_sg != 0; } int main() { calcSg(); int cnt_cas; scanf("%d", &cnt_cas); while (cnt_cas--) { printf("%s\n", solveCase() ? "Alice" : "Bob"); } return 0; }
这篇关于「postOI」Colouring Game的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-15PingCAP 黄东旭参与 CCF 秀湖会议,共探开源教育未来
- 2024-05-13PingCAP 戴涛:构建面向未来的金融核心系统
- 2024-05-09flutter3.x_macos桌面os实战
- 2024-05-09Rust中的并发性:Sync 和 Send Traits
- 2024-05-08使用Ollama和OpenWebUI在CPU上玩转Meta Llama3-8B
- 2024-05-08完工标准(DoD)与验收条件(AC)究竟有什么不同?
- 2024-05-084万 star 的 NocoDB 在 sealos 上一键起,轻松把数据库编程智能表格
- 2024-05-08Mac 版Stable Diffusion WebUI的安装
- 2024-05-08解锁CodeGeeX智能问答中3项独有的隐藏技能
- 2024-05-08RAG算法优化+新增代码仓库支持,CodeGeeX的@repo功能效果提升