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

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

原文链接www.cnblogs.com/zhouzhendong/p/UOJ370.html首先易知答案肯定是一条链，因为挂在链的最下面肯定比挂在其他节点上赚。问题被转化成了从一个集合中不断选数加入到当前序列尾端，使得序列的所有前缀AND之和最小。我们发现，假如加入一个数后可以使序列的AND值变小，那么必然不会去加一个...

原文链接www.cnblogs.com/zhouzhendong/p/UOJ373.html　　真是一道毒瘤题。UOJ卡常毒瘤++。我卡了1.5h的常数才过QAQ　　Orzjry　　标算居然是指数做法。1.感受一下线图上点的含义1.1一阶线图　　L(G)上的一个点对应G中的一条边。1.2二阶线图　　$L^2(G)$上一...

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

原文链接https://www.cnblogs.com/zhouzhendong/p/CF840C.html首先，我们可以发现，如果把每一个数的平方因子都除掉，那么剩下的数，不相等的数都可以相邻，相等的数都不能相邻。也就是说我们把所有数分成了一些集合，同一个集合内的元素不能相邻，不同集合之间的元素可以相邻。关键部分到了...

原文链接https://www.cnblogs.com/zhouzhendong/p/CF700E.html首先建个SAM。一个结论：对于parent树上任意一个点x，以及它所代表的子树内任意一个点y，设节点y代表的最长串为S，设节点x代表的串为T1,T2,T3,...，设F(S,T)表示串T在S中的出现次数，则F(S...

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

原文链接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/CF1110D.html　　给定n个数，每一个数都是在[1,m]里的整数。　　从中取出形如{x,x,x}或者{x-1,x,x+1}的集合，各个集合不能相交，问最多能取出几个。　　$n,mleq10^6$　　标算非常简洁。　　我这里讲讲...

原文链接https://www.cnblogs.com/zhouzhendong/p/CF830D.html考虑用$dp[i][j]$表示深度为$i$的树里，有$j$条路径的方案数。分四种情况转移即可：枚举$j,k$，我们来算一下$dp[i-1][j]$和$dp[i-1][k]$对$dp[i]$的贡献。设$tmp=dp...

一，问题描述给定一个背包，已知背包的最大承重为packageWeight，再给出若干件(numbers件)物品，已经每件物品的重量和对应的价值。物品的重量存储在weight[]数组中，物品的价值存储在value[]数组中。现在要求：应该挑选哪几件物品，使得背包装下最大的价值（注意：装的物品的重量不能超过背包的承重）（本...