louhc

分类

未归档(78) 题解(81)

/ 注册

全部文章（共6篇）

题解 | 信息学奥赛一本通取石子游戏

思路首先,函数什么的不怎么管用.(亏我想了好久)这题做法十分神奇.设表示在区间[l,r]的石子左边添加一堆L[i][j]的石子会导致先手必败,如果没有该种策略值为0.与此同理.易证决策不可能吧同时存在多个.预处理边界.因为相同的两堆会导致这样的情况:先手在一堆取多少,后手就在后一堆取多少,先手明显...

博弈论

2019-09-03

1 853

题解 | 信息学奥赛一本通取石子

思路不知道为什么好多大佬写的都是玄学的.这里介绍从某位神仙博客看来的神奇推理.过滤石子数为0的堆,我们把石子数为1的堆(以下称为单数堆)的个数记为,大于1的堆(以下称为复数堆)石子数总和+堆数-1记为.先手存在必胜策略当且仅当满足以下条件: 若,需要满足和至少有一个是奇数. 若,需要满足. 下...

博弈论

2019-09-02

1 833

题解 | 信息学奥赛一本通 S-Nim

思路简单的博弈论题.直接上函数,预处理出的函数值,然后对于每个局面,所有石子数异或起来,大于0则输出,否则输出.复杂度为. 代码 #include<bits/stdc++.h> using namespace std; #define i64 long long #define fp(...

博弈论

2019-09-01

0 612

题解 | 信息学奥赛一本通巧克力棒

思路博弈的拓展.第一步你必须取出一些巧克力棒.如果你取出的巧克力棒函数值异或和不为0,你就死了.因为不管你吃巧克力还是再拿巧克力,对方都可以吃巧克力使异或和为0.异或和为0的话情况就恰恰相反,你赢定了(当然前提是你足够聪明).所以答案就要看是否存在异或和为0的子序列.复杂度为. 代码 #inclu...

博弈论

2019-09-01

0 518

题解 | 信息学奥赛一本通取石子游戏

思路博弈论模板题.直接像动态规划一样求出所有的函数值并异或起来.这里需要输出方案,枚举和,取完后若函数值为,那么就是合法方案.复杂度为(表示). 代码 #include<bits/stdc++.h> using namespace std; #define i64 long long ...

博弈论

2019-09-01

0 603

题解 | 信息学奥赛一本通移棋子游戏

思路博弈论模板级别的题.算出每个节点的函数值(所有出点的函数值求mex,没有出边的函数值为),然后将所有起点的异或起来就是整个游戏的函数值.若函数值大于,就是win,否则就lose.复杂度大概为. 代码 #include<bits/stdc++.h> using namespace s...

博弈论

2019-09-01

0 474