louhc

题解

未归档(78)

/ 注册

全部文章 / 题解（共81篇）

题解 | 信息学奥赛一本通 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

题解 | 信息学奥赛一本通有趣的数列

思路我们将按次序填入,填入未填的,编号最小且为奇/偶数的项.也就是说,位置必须在之后再填.因为,任何时候已填的奇数项不能少于偶数项.这样子可以看成一个栈,填入一个奇数项表示一个元素进栈,填入一个偶数项表示栈顶弹出.所以答案就是卡特兰数第项.复杂度大概为. 代码 #include<bits/s...

卡特兰数

2019-09-01

0 573

题解 | 信息学奥赛一本通序列统计

思路不降的话先改成严格上升,也就是第个数加上,范围就是.然后长度为的序列个数为(选任n个,然后排序,第i项减i还原成不降序列).总答案就是,也就是.用卢卡斯定理求解即可.复杂度. 代码 #include<bits/stdc++.h> using namespace std; #defi...

排列组合

2019-09-01

0 698

题解 | 信息学奥赛一本通数三角形

思路选任意不同的三个点方案数为.然后需要减去共线的三个点的方案数.首先横纵方向.然后考虑枚举每个向量(也就是斜率和长度相同的线段同时枚举),该向量起始位置和中间的某个点为一种方案,那么对于向量,贡献为.上下翻转也是可行的,贡献再乘2.这样子复杂度就是. 代码 #include<bits/st...

排列组合

2019-09-01

0 645