思路 简单的数位DP题.预处理出表示位,最高位为的Windy数有多少.然后将范围转换为前缀和(这是有多套路qwq),从高位枚举到低位,加上选小于当前位的数的合法方案数,如果当前位到顶,继续枚举低位.然后别忘了最后答案+1.(一切都是多么经典qwq)算法复杂度为. 代码 #include<bits/stdc++.h> using namespace std; #define i64 long long #define fp( i, b, e ) for ( int i(b), I(e); i <= I; ++i ) #define fd( i, b, e ) for ( int...

思路 我们先用前缀和将问题转化为求范围内满足条件的数的个数-范围内满足条件的数个数.我们设当前我们在求范围内满足条件的数.我们可以考虑一棵二叉树,往左走表示第位为,往右走为.(表示深度;第位表示最高位,以此类推;这里是进制时).这样走到叶子节点都会得到一个数,我们的任务就是找出恰好往右走了次,结果得到的数不超过的路径条数.事实上我们不需要建出二叉树,只是这样可以使问题更形象我们记录答案与一个计数变量(表示前面有几位选了).先将在进制下每一位求出来存在数组中(是最高位,是次高位,共有位),从枚举到,如果当前,我们就有两种选择,一种是使当前位为,还有一种是使当前位为.如果,i位及之后怎么走都不会超...

思路 因为所有限制都是整数,中间过程参与运算的数字也肯定都是整数,而且数据范围允许,我们可以设计状态表示第天拥有支股票时相对初始状态最多有的钱.这天可以不买也不卖,所以的一种决策是.只有天前的状态有用,我们可以直接取的状态.(由于上一种转移,这肯定是最优的)然后这天要么买,要么卖,否则肯定不是最优的.(因为)于是我们分别转移.如果买股票,的决策有.如果卖股票,的决策有.如果暴力转移,复杂度就是的,过不了.于是我们需要用单调队列优化.先对买卖股票的转移方程拆开来.其中变成,然后维护的最大值,及时弹出已经不合法的状态即可(也就是的状态).卖股票的转移同理.最后答案即为.(很明显最后股票都卖光或者干...

思路 首先,函数什么的不怎么管用.(亏我想了好久)这题做法十分神奇.设表示在区间[l,r]的石子左边添加一堆L[i][j]的石子会导致先手必败,如果没有该种策略值为0.与此同理.易证决策不可能吧同时存在多个.预处理边界.因为相同的两堆会导致这样的情况:先手在一堆取多少,后手就在后一堆取多少,先手明显必败.然后中间的决策可以推过去.设 这样是一个必败态,不管在左边放怎样的石子堆先手都可以取完这一堆引来必败态,所以. .先手在某一边取多少(未取完),后手就在另一边取多少如果先手把一边取完了,后手面临的情况可以看做的石子在左边或右边放一堆石子,且不为或.前面说过,必败的放石子方案是唯一的,因此这个...

思路 不知道为什么好多大佬写的都是玄学的.这里介绍从某位神仙博客看来的神奇推理.过滤石子数为0的堆,我们把石子数为1的堆(以下称为单数堆)的个数记为,大于1的堆(以下称为复数堆)石子数总和+堆数-1记为.先手存在必胜策略当且仅当满足以下条件: 若,需要满足和至少有一个是奇数. 若,需要满足. 下面我们来证明这个结论.先证明的情况.很明显最后时为必败态.不管怎样你都有办法使复数堆不被直接取完(也就是最后都合并成一堆).如果是都是奇数,你可以把一个单数堆与一个复数堆合并,这样子都减一,变成必败态.如果是奇数,是偶数,你直接合并两个复数堆或者从复数堆取一个石子或者合并两个单数堆(当时就得这么干)...

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

思路 博弈的拓展.第一步你必须取出一些巧克力棒.如果你取出的巧克力棒函数值异或和不为0,你就死了.因为不管你吃巧克力还是再拿巧克力,对方都可以吃巧克力使异或和为0.异或和为0的话情况就恰恰相反,你赢定了(当然前提是你足够聪明).所以答案就要看是否存在异或和为0的子序列.复杂度为. 代码 #include<bits/stdc++.h> using namespace std; #define i64 long long #define fp( i, b, e ) for ( int i(b), I(e); i <= I; ++i ) #define fd( i, b, e ) ...

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

思路 博弈论模板级别的题.算出每个节点的函数值(所有出点的函数值求mex,没有出边的函数值为),然后将所有起点的异或起来就是整个游戏的函数值.若函数值大于,就是win,否则就lose.复杂度大概为. 代码 #include<bits/stdc++.h> using namespace std; #define i64 long long #define fp( i, b, e ) for ( int i(b), I(e); i <= I; ++i ) #define fd( i, b, e ) for ( int i(b), I(e); i >= I; --i ) #d...

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

思路 很明显所有的阶梯都顶到某一列的顶部.枚举顶到第一列阶梯顶部的阶梯的长度,接下来列都不能到第一列,前列的最下面行全部空出来,这样子就形成一个子问题,而最后列也是一个子问题,中间空出来那部分也由该子问题扩充过去.如图,第一列选了黄色部分的三块,红色部分是一个子问题,绿色部分是一个子问题,中间白色部分由绿色部分扩充过来.设是行列的答案,可以枚举第一列选的长度.这就是卡特兰数的递推式,求卡特兰数即可.此题需要高精度.所以用Python/Java. 代码 N = int(input()) NN = N<< 1 vis = [0 for i in range(NN + 5)] p = [...

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

思路 我们将按次序填入,填入未填的,编号最小且为奇/偶数的项.也就是说,位置必须在之后再填.因为,任何时候已填的奇数项不能少于偶数项.这样子可以看成一个栈,填入一个奇数项表示一个元素进栈,填入一个偶数项表示栈顶弹出.所以答案就是卡特兰数第项.复杂度大概为. 代码 #include<bits/stdc++.h> using namespace std; #define i64 long long #define fp( i, b, e ) for ( int i(b), I(e); i <= I; ++i ) #define fd( i, b, e ) for ( int i(...

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