原文链接https://www.cnblogs.com/zhouzhendong/p/UOJ290.html真是一道好题！首先，如果不是仙人掌直接输出0。否则，显然先把环上的边删光。问题转化成多个树求解，把答案乘起来即可。现在我们考虑如何求一个树的答案。再转化一下题意可以变成选出若干条长度至少为2的路径使得它们两两没有...

原文链接https://www.cnblogs.com/zhouzhendong/p/UOJ291.html结论：这个写错的树状数组支持的是后缀加和后缀求和。这里的后缀求和在x=0的时候比较特殊，返回0。于是我们需要查询v[L-1]和v[R]相同的概率是多少。我们可以用树套树维护一下左端点在一个区间内，右端点在另一个区...

原文链接https://www.cnblogs.com/zhouzhendong/p/UOJ375.html首先，我们可以建出一个k个点的自动机，第i个点表示当前数对k取模为i-1。显然每一个点有m-1条出边。然后，稍加观察，我们就可以发现，如果一些节点的出边集合是相同的，我们就可以将他们合并。具体是怎样的节点呢？对于...

原文链接https://www.cnblogs.com/zhouzhendong/p/UOJ374.html想出正解有点小激动。不过因为傻逼错误调到自闭。不如贺题首先我们考虑如何$O(n)$求一个答案。首先，计算两条路径的贡献时，由于两国连续交战数次只算一次，所以我们可以只看这两条路径的交的最深点。也就是说，我们可以对...

原文链接https://www.cnblogs.com/zhouzhendong/p/UOJ55.html做法还是挺容易想到的。但是写的话……首先这种题如果只要求一棵树中的满足条件的点数（不需要在加点的同时维护答案），那么显然可以点分治：假设当前点分中心为x，设点y与x的距离为d[y]，然后...

原文链接https://www.cnblogs.com/zhouzhendong/p/UOJ395.html记得同步赛的时候这题我爆0了，最暴力的暴力都没调出来。首先我们看看68分怎么做——求两个串的本质不同的公共子串个数。　　它是一个模板题，然而我当时并不会，甚至连SAM都忘了怎么写QAQ。&...

原文链接https://www.cnblogs.com/zhouzhendong/p/UOJ172.html首先，这个问题显然是个背包问题。然后，可以证明：一个字符串的border长度可以划分成$O(log|S|)$个等差数列。(以下图片摘自 金策-《字符串算法选讲》)由于长度n可以随便取，所以我们可以在对n...

原文链接https://www.cnblogs.com/zhouzhendong/p/UOJ407.html套路啊。先按照两个节点顺序各搞一个kruskal重构树，然后问题转化成两棵kruskal重构树，不断询问，每次询问让你判断是否有点同时存在于第一棵树的一个子树和第二棵树的一个子树中。这个东西就转成dfs序之后主席...

原文链接https://www.cnblogs.com/zhouzhendong/p/UOJ218.html如果我们可以知道每次弹出栈之后新的栈顶是什么，那么我们就可以在一棵区间覆盖、区间求和的线段树上完成这个问题。于是本题的重点转到了如何求新的栈顶。考虑用一个主席树维护一下每一个时刻每一个位置的栈顶元素的进栈时间，那...

原文链接https://www.cnblogs.com/zhouzhendong/p/UOJ42.html首先我们把式子改写一下：$$(-1)^{lfloorafloor}\=1-2(lfloorafloormod2)\=1-2(lfloorafloor-2lfloorfraca2floor)$$于是问题就变成了求解...

原文链接https://www.cnblogs.com/zhouzhendong/p/UOJ276.html首先，读入的时候就将所有的$w_i$减掉$k$。于是我们要求的就是平均值最接近0的。直接点分治，然后得到一些一端为当前点分中心的路径，设$a,b$为其中两条路径，设$v_a,v_b$为路径的边权和，$t_a,t_...

原文链接https://www.cnblogs.com/zhouzhendong/p/UOJ110.html我们发现n=2000的子任务保证A=1！分两种情况讨论：$nleq100$：　　贪心地从高位到低位逐位考虑，看当前位是否可以放0。用$dp[i][j]$表示前$i$个数是否可以在各段sum的or值不超过当前上限的...

原文链接https://www.cnblogs.com/zhouzhendong/p/UOJ185.html首先暴力DP是$O(3^nn^3)$的，大家都会。我们换个方向考虑。假设我们求的是树上每一个节点到图上的节点的映射，而且图上的一个点可以被树上多个点映射到，那么就是求图上所有点都被映射到至少一次的方案数。我们发现...

原文链接https://www.cnblogs.com/zhouzhendong/p/UOJ201.html首先把题目里面的提示抄过来：结论：假设带权无向图G有100个节点1000条边，且所有权值各不相同。那么，G中一定存在一个单调上升路径，它的长度大于等于20。证明：假设每个节点上有一个探险家。我们按权值从小到大枚举...

原文链接https://www.cnblogs.com/zhouzhendong/p/UOJ460.html　　本题的构造方法很多。这里只介绍一种。　　首先，总边数为$frac{n(n-1)}2$，每一棵树需要$n-1$条边，所以答案最多是$lfloorfracn2floor$。　　然后我们来找到构造出 $l...