louhc

分类

未归档(78) 题解(81)

/ 注册

全部文章（共160篇）

题解 | 信息学奥赛一本通股票交易

思路因为所有限制都是整数,中间过程参与运算的数字也肯定都是整数,而且数据范围允许,我们可以设计状态表示第天拥有支股票时相对初始状态最多有的钱.这天可以不买也不卖,所以的一种决策是.只有天前的状态有用,我们可以直接取的状态.(由于上一种转移,这肯定是最优的)然后这天要么买,要么卖,否则肯定不是最优的...

单调队列动态规划

2019-09-03

0 686

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

思路首先,函数什么的不怎么管用.(亏我想了好久)这题做法十分神奇.设表示在区间[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

题解 | 信息学奥赛一本通车的放置

题解枚举上半部分与下半部分分别有多少车.设上半部分有个车,那么上半部分方案数为.下半部分少了几列可以放,方案数为.然后根据乘法原理,乘起来即可.复杂度为.(如果求逆元直接使用快速幂就是,而如果求出最后一个逆元,逆推回去就是,下面直接使用前者) 代码 #include<bits/stdc++....

排列组合

2019-09-01

1 585

题解 | 信息学奥赛一本通树屋阶梯

思路很明显所有的阶梯都顶到某一列的顶部.枚举顶到第一列阶梯顶部的阶梯的长度,接下来列都不能到第一列,前列的最下面行全部空出来,这样子就形成一个子问题,而最后列也是一个子问题,中间空出来那部分也由该子问题扩充过去.如图,第一列选了黄色部分的三块,红色部分是一个子问题,绿色部分是一个子问题,中间白色部...

高精度卡特兰数

2019-09-01

0 761

题解 | 信息学奥赛一本通超能粒子炮·改

思路设,答案就是.根据卢卡斯定理,我们可以化简上面的式子.也就是.整理一下.递归就OK了.复杂度大概是(至于怎么分析,上面那个式子只有两个部分的变量有可能大于能递归下去). 代码 #include<bits/stdc++.h> using namespace std; #define ...

卢卡斯定理排列组合

2019-09-01

0 722