原文链接www.cnblogs.com/zhouzhendong/p/UOJ299.html不会概率题的菜鸡博主做了一道概率题。写完发现运行效率榜上的人都没有用心卡常数——矩阵怎么可以用数组呢？矩乘怎么可以用循环呢？截止2019-05-15暂居运行效率榜一。首先，根据期望的线性性，容易得知，总期...

原文链接www.cnblogs.com/zhouzhendong/p/UOJ401.html首先，对于一个排列，它的连续段一定只有包含关系，没有相交关系。我们可以据此得到一棵表示连续段的树。对于一个连续段节点，它有若干儿子。由于它的每一个儿子都是连续段，所以我们可以将这些儿子各自看作一个数。设节点x的度数为d[x]。设...

原文链接www.cnblogs.com/zhouzhendong/p/UOJ400.html老年选手没有码力。先对第一棵树进行边分治，然后，设点x到分治中心的距离为$D[x]$，点x在原树上的深度为$d[x]$，那么$$d[x]+d[y]-d[LCA(x,y)]-d'[LCA(x,y)]=frac12(D[x]+d[x...

原文链接www.cnblogs.com/zhouzhendong/p/UOJ435.html分块题果然是我这种蒟蒻写不动的。由于种种原因，我写代码的时候打错了很多东西，最致命的是数组开小了。**windows不能检测数组越界，能眼查出来这运气是真的好。首先树链剖分，把问题转化为序列上的问题。然后我们分块。考虑如何维护每...

原文链接www.cnblogs.com/zhouzhendong/p/UOJ440.html菜鸡选手到省选了才做联赛题。首先我们分析一下性质：1.假如一个格子是0，那么它的右上角一定是0。2.假如一个格子的左边和上面两个格子一样，那么从这个格子到终点的任何两条路径相同。不难发现，对于第3个斜列，我们发现这个斜列至少有一...

原文链接www.cnblogs.com/zhouzhendong/p/UOJ335.htmlCLY大爷随手切这种题。日常被CLY吊打系列。首先从pruffer编码的角度考虑这个问题。pruffer编码的长度为$n-2$，如果点$i$在pruffer编码中出现了$d_i-1$次，那么点$i$的度数就是$d_i$，对答案的...

原文链接www.cnblogs.com/zhouzhendong/p/UOJ73.html纯属理性愉悦。发现就是求$aimesbmodc$。写个快速乘就好了。直接打开的话会发现gedit卡死了。用SublineText开开看了看好像没什么特别的。看看这份代码的长度，怎么这么大？仔细看会发现下面有一行注释起来的英文，不知...

原文链接www.cnblogs.com/zhouzhendong/p/UOJ206.htmlT=1的情况直接大力从两边向中间询问即可。T=2的情况挺妙的，我没想到。　　考虑首先花费n+1代价得到全局最大值和最小值，也就是a[1]和a[n]。　　然后考虑将值域均分为n-1段，每一段询问一下。答案一定在相邻两段区间的左边一...

原文链接www.cnblogs.com/zhouzhendong/p/UOJ129.html　　考虑把大于等于$sqrtn$的质数和小于$sqrt n$的分开考虑：　　1.小于等于$sqrtn$的质数最多只有8个。　　2.一个小于等于n的正整数最多包含1个大于$sqrtn$的质因子，所以不同的这种质因子可以分...

原文链接www.cnblogs.com/zhouzhendong/p/UOJ346.html首先按照$m_i$的大小排个序。如果某一个区间和一个m值比他小的区间有交，那么显然可以将这个区间控制的区域删除掉重合的那一段。如果一个区间被删没了，那么显然答案为0。在这个处理之后，一个区间可能会变得不连续。那么我们就将它前后相...

原文链接https://www.cnblogs.com/zhouzhendong/p/UOJ345.html我真的是越来越菜了，连树形DP都感觉陌生了。首先，我们来看看在不断生长叶子会发生什么。第一种：顺着生长方向走。第二种：在某一个节点的某些子树依次生长，达到他们之间互相消耗的作用。 对于一个子树x，假设初...

原文链接www.cnblogs.com/zhouzhendong/p/UOJ465.htmltmd并查集写挂，调到自闭。cly和我写挂了同一个地方。一下救了两个人感觉挺开心。首先直接写bfs/记忆化dfs可以容易地得到一个$O(m^2)$，或者$O(nm)$的做法。常数不大的情况下应该可以得到70分。注意到本题中不要求...

原文链接www.cnblogs.com/zhouzhendong/p/UOJ104.html首先证明一个结论：对于一种分割方案，分割的顺序不影响最终结果。证明：对于树a[x]和a[y]，如果x与y之间有分割，那么它们对答案的贡献就是a[x]*a[y]，否则无贡献。于是问题转化成DP：设dp[i][j]表示把前j个数分成...

原文链接www.cnblogs.com/zhouzhendong/p/UOJ416.html完了完了SB选手Tarjan写挂。考虑先Tarjan缩个点双建个圆方树。然后发现，确定起点和终点后，中间点的可选方案数就是  这条路径上的所有点双size之和-2。定义原点表示原图中的点，方点表示圆方树中新加...

原文链接www.cnblogs.com/zhouzhendong/p/UOJ196.html先离散化，设离散化后的值域为$[0,m]$。首先把问题转化一下，变成：对于每一个位置$i$，求出它最终不超过$j$的方案数。考虑如何求这个东西。对于一个固定的$j$，考虑一个这样的过程：初始时，有若干个区间，两两不相交，且区间内...