为什么要学卡特兰数？ 为了解决一类计数问题 NOIp能考吗：能 以此记录我模拟赛中被强行卡特兰数卡爆的贪心神题 什么是卡特兰数？ 卡特兰数又称卡塔兰数，卡特兰数是组合数学中一个常出现在各种计数问题中的数列。以比利时的数学家欧仁·查理·卡塔兰 (1814–1894)的名字来命名。–百度百科 用人话来说，就是开头为1，2，5，14，42，132，429，1430，4862…的数列 卡特兰数的...

Oct,22ed,2018　　DAY -18 又是颓废的一天呢 我好菜啊，一个圆方树弄了一整天（点双怎么那么毒瘤）。（铁人两项怎么那么多点） Oct,23rd,2018　　DAY -17 又双叒叕颓了一天 下午考了一个蜜汁模拟塞，全部都是历年T1，写的是时候出现了巨多问题，什么输入写挂啊，忘记初始化啊，双向边写成单项边啊，导致我比机房dalao多调了半个小时。（好在我最终的没有写挂。）先膜一...

题面 传送门：洛谷 Solution 这题极其巧妙。 首先，如果直接做m次排序，显然会T得起飞。 注意一点：我们只需要找到一个数。 所以说，我们可以考虑一个绝妙的想法：我们可以用二分答案的方法缩小要找的数的区间。 考虑二分一个值，判定p位置的数排序之后，p位置上的数是否>=mid 如果>=mid,则向右找，否则向左找。 怎么判定p位置的数排序之后是否>=mid呢？ 考虑这...

题面： 传送门：Codeforces 题目大意：给你一颗有根树，点有权值，问你每个节点的子树中距离其不超过k的点的权值的最小值。（边权均为1，强制在线） Solution 这题很有意思。 我们一般看到这种距离不超过k的题目，第一反应一般是建以深度为下标，以dfs序为时间轴的的主席树。 很不幸，区间最小值并不能通过减去历史状态得出某个子树的状态。 所以说，这题妙在思想的转换。 考虑以dfs序...

题面 传送门：洛谷 Solution 你们搞的这道题啊，excited！ . 这题真的很有意思。 首先，我们可以先理解一下题面：固定一个a，找到一个b，c就是a与b的公共子树中的某个点。 那么，我们显然可以把这个b分成两类，第一种是在a上面的，第二种在a下面的。 对于b在a上面的情况，**显然，c一定是a的子树中的某个点，**答案即为$min(K，depth[a])*size[a]$ 对于...

题面 洛谷 Solution 这题十分有意思。 首先，我们可以先想想离线做法，因为在线做法可以从离线做法推出。（虽然这题推不出） 我们可以明确一点，一个熊孩子开心的时间是满足二分的要求的（如果他某个时刻开心了，那之后的时刻都会保持开心）。 对于判断一个区间是否为全0，我们可以用主席树以一个log的代价来判断。 得到每个熊孩子开心的时刻之后，我们就可以直接前缀和解决问题了。 时间复杂度$O(...

题面：洛谷 Solution 首先，我们可以先康一康题目的数据范围：n<=18，应该是状压或者是搜索。 事实上，这题搜索和状压DP都是能做的。 （因为搜索在我心中留下了阴影（斗地主），所以在这里，我讲状压DP的做法） 根据我们以往设计状压DP的经验，我们可以很轻松地设计这一题的状态： 设f[i]表示打下的猪猪的状态为i的方案数，（状态在这里用二进制方式来表示，例如：00101表示打下...

题面 蒟蒻博客：QAQ Solution 这是一道神题 首先，我们不妨想一下K=0，即求最短路方案数的部分分。 我们很容易可以想到一个做法，就是魔改迪杰斯特拉做法： 一个点可以更新到达其他点的距离，那个点的方案数就是这个点的方案数；如果一个点所更新出来的距离和之前的相等，那个点的方案数加等当前点的方案数。 用式子可以表现为： $$f[i]=f[i] (dis[j]>dis[i]+x)...

题面： 传送门：洛谷 Solution 看到这题，我们肯定会有一个大胆想法。 那就是直接用堆模拟这个过程。 对于q，我们只需要在堆中多维护一个T,记录每个点插入的时间，在新的元素插入时直接计算所比较的点的当前长度就可以完成插入了。 时间复杂度$O(M*log(M))$ 这样的做法只能获得65-70分，因为后面的数据非常大。 所以说，我们要另寻他路。 首先，我们经过看题解手玩可以发现一个很显...

题面 传送门：洛谷 Solution 这是一道神奇的题目，我们有两种方法来处理这个问题，一种是DP，一种是组合数。 这题需要高精度，以下省略此声明 . DP 如果你对数学不感兴趣/喜欢写DP/(不想虐待自己)，这里是DP做法。 首先，我们可以发现，这个数最多有$w/k$位(向上取整),如下图所示： 那么，我们就可以以这个特性做DP啦。 设$f[i][j]$表示枚举到第i位(指2^k进制下...