题面 传送门：洛谷 Solution 这题… 我们可以发现题目要求我们维护一个动态森林，而且只查询连通性… 显然LCT模板题啊，关于LCT玩法，可以猛戳这里学习 Code 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859...

为啥要学LCT啊 在开坑之间，我们来先看一段对话： Q：给你一颗森林，现在不断的连接森林中的两棵树，保证不连出环，多次问你某两个点的连通性？ A（dalao&蒟蒻）：这不是SB题吗？显然并查集水过啊。 Q：说的好，但是如果我要删除某些边呢？ A（dalao）：那就可持久化并查集啊，你的问题怎么那么水。 A（蒟蒻）：…（发出gg的声音） 这时候，如果我们并不想写可持久化并查集的话，就得...

题面 传送门：洛谷 Solution 这题的思想挺好的。 对于这种最大值最小类的问题，很自然的可以想到二分答案。很不幸的是，这题是双关键字排序的，我们怎么二分呢？ 先二分a再二分b？怎么看都布星啊。 那a+b作为关键字二分？也布星啊。 那咋搞啊？ 不如，我们换个想法，我们把其中一个关键字枚举，再看在这个关键字的限制下，另外一个尽可能小。 仔细想想，应该是能覆盖到所有的情况的。 所以说，我们...

题面 传送门：洛谷 Solution 首先，长成这样的题目一定是淀粉质跑不掉了。 考虑到我们不知道K的大小，我们可以开一个splay来统计比某个数小的数的数量。 不会点分治的戳我 Code 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545...

什么是淀粉质点分治？ 就是把分治搬到树上，以某个点为根，分别分治处理子树的答案，再计算子树与子树间的答案的玄学算法。 举个例子： 如何求出一颗树上距离为K且所经过的点最少的点对？ 对于这种题，我们可以把某个点（一般为重心）作为根，然后对左右子树递归处理，先分别得出左右子树的答案，再求出横跨两个子树之间的点对的答案。 为什么要学淀粉质 对于上面那道题，如果我们用传统的暴力做法，最优的复杂度只能...

DAY 1 8：30 总算拿到题目啦！ 打开题目一看，T1T2T3全部512MB，1s，没有什么特别奇怪的时间限制的题目，题目应该可做(吧)。 8：32 啥废事都没做，直接开T1。 等等。。。。。。等一下下 这熟悉的题意。。。。。。 这不是神TM的积木大赛原题吗？ 直接5min消灭，过了大样例，稳如老狗。 8：37 快速过了一眼T2,T3。T2好像不怎么可做，想了5分钟只会一个a^n的10分...

什么是裴蜀定理 裴蜀定理（或贝祖定理，Bézout’s identity）得名于法国数学家艾蒂安·裴蜀，说明了对任何整数a、b和它们的最大公约 数d，关于未知数x和y的线性不定方程（称为裴蜀等式）：若a,b是整数,且（a,b)=d，那么对于任意的整数x,y,ax+by都一定是d的倍数，特别地，一定存在整数x,y，使ax+by=d成立。 ——百度百科 用人话来说就是： $\sum a_i*...

什么是边双？ 双连通分量又分点双连通分量和边双连通分量两种。若一个无向图中的去掉任意一个节点（一条边）都不会改变此图的连通性，即不存在割点（桥），则称作点（边）双连通图。一个无向图中的每一个极大点（边）双连通子图称作此无向图的点（边）双连通分量。求双连通分量可用Tarjan算法。——百度百科 用人话来说，就是在无向图上以边为关键字，对原图缩点 为什么要学边双 与强连通分量类似，我们可以求...

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

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