CodeForces 1091H. New Year and the Tricolore Recreation
题目简述:给定$n \leq 10^5$个三元组$(b_i, w_i, r_i)$,其中$10^5 \leq b_i < w_i < r_i \leq 10^5$,以及一个限制参数$f$。一个正整数$k$是【好】的,若其为质数,或者为两个(可以相同的)质数之积。A和B进行双人博弈:
在A的回合:A进行一次操作,选择一个$1 \leq i \leq n$和一个【好】数$k \neq f$,将$(b_i, w_i, r_i)$变为$(b_i+k, w_i, r_i)$或者变为$(b_i+k, w_i+k, r_i)$;
在B的回合:B进行一次操作,选择一个$1 \leq i \leq n$和一个【好】数$k \neq f$,将$(b_i, w_i, r_i)$变为$(b_i, w_i, r_i-k)$或者变为$(b_i, w_i-k, r_i-k)$。
一次操作是合法的,如果这个操作之后仍然满足$b_i < w_i < r_i$。第一个无法进行合法操作的一方输掉此次博弈。
假设二人的决策是最优的,问:1. 若$A$先手则谁赢;2. 若$B$先手则谁赢。
解:code
建模:
令$x_i = w_i-b_i, y_i = r_i-b_i$,一个三元组$(b_i, w_i, r_i)$则可以被二元组$(x_i, y_i)$描述,因为我们只会关心他们的相对位置。
则在A和B的回合都是:将$(x_i, y_i)$变为$(x_i-k, y_i)$或者$(x_i, y_i-k)$。而且每次操作后,要求满足$x_i > 0$且$y_i > 0$。
于是,一组$(x_i, y_i)$相当于是两个独立的“取石子游戏”。与传统“取石子游戏”不同的地方则是只允许每次从一堆石子中拿出【好】数个石子。
从而,整个博弈就化为了$2n$个独立的“取石子游戏”。
SG函数:
令$\text{SG}(n)$表示有$n$个石子的“取石子游戏”的SG函数值,则
$$ \text{SG}(n) = \begin{cases} \operatorname{mex}\{ \text{SG}(n-k): k \leq n\text{是好数} \} & n \geq 1 \\ 0 & n = 0 \end{cases}, $$
其中$\text{mex} S$表示集合$S$中未出现的最小非负整数。
观察:当$n \leq 2\times 10^5$时,$\text{SG}(n) \leq 100$。(???)
求解出SG函数值后,根据Sprague-Grundy定理,将$2n$个独立的“取石子游戏”的SG函数值作异或(xor)得到整个博弈的SG函数值。
位运算优化:
我们维护$f[i][j]$表示SG值为$i$的所有已处理的状态是否有向状态$j$的转移。令$u[i]$表示$i$是否是【好】数。若$f[i]$和$u$均用bitset存储,则SG函数的计算以及$f[i][j]$可以如下方式维护:
f[0] = u;
for (int i = 1; i <= 200000; ++ i)
{
for (SG[i] = 0; f[SG[i]][i]; ++ SG[i]);
f[SG[i]] |= u<<i;
}
时间复杂度为$O(n^2/32)$,空间复杂度$O(nm/32)$,其中$m$为最大可能的SG函数值。
注:注意到当$i$较大时,"f[SG[i]] |= u<<i"还有优化空间,因为u的高位bit在运算中是无用的。可自己实现bitset做到此优化。code2
最新文章
- Hello Blog
- 同一网站中HTML相对路径引用
- NO.3 CAS配置问题汇总
- SharePoint 2013 Nintex Workflow 工作流帮助(六)
- cocos2d-x (Android)之-那些常见的error记
- Java [Leetcode 338]Counting Bits
- 使用 spring封装的javamail linux服务器发送邮件失败解决
- mybatis 日志的使用以及设计
- 【Boost】boost::tokenizer详解
- 自定义mysql类用于快速执行数据库查询以及将查询结果转为json文件
- asp.net core日志组件
- Leetcode 150
- 08 bash特性--shell脚本编程入门
- Android JSON 解析关键代码
- Eclipse中新建Java工程的三个JRE选项区别
- LogStash日志分析系统
- DelphiXE8FMX工程实现无边框托动(FMX内部方法)
- ASP.NET实现数据绑定
- 项目经验:GIS<;MapWinGIS>;建模第六天
- 九度oj题目1181:遍历链表