集训补题合集

本文主要是介绍集训补题合集，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

好多题都不会啊，这可咋整
先写着吧....大概会割掉....

cf490

求带点权树上的简单路径构成的点权序列的最长上升子序列的长度的最大值

一个比较容易想到的做法就是dp，设f[x,i]表示以x为根的子树中，以i为结尾的最长上升子序列的长度，g[x,i]就是下降。这里我们规定只能选取深度递降的顺序
那么每次合并子树就好了，这样直接做是n^2logn的。还可以用线段树记录这个结尾的状态，那么两个dp状态合并就是线段树合并了，这样就少一个n

牛客多校1C

给一棵树要求删掉一个节点，使得剩余每棵树中的cf490的答案最大值最小

这个做法就很强。首先可以找原树的最长路径所在的链c，那么要删的点一定在这条链上（否则最大值不变）
不妨假设删掉了一个点x，那么这条最长链被分成两部分c1和c2，此时再按照cf490的方法求一次最长链得到c'，则分类讨论

1. c和c'相交，这个时候删掉它们的交点会更优秀（不仅让原本的最长变短了，还让变短后的最长也变短了）
2. c和c'相离，这个时候删掉c上的任意一点都一样

于是就可以发现如果我们不断这么做下去，最终将得到若干条链的交，且这个交在不同层次的最长链上，删掉交里的点一定是最优秀的
每次对当前的交二分（取中点），判断新的交在哪一侧，这样就只是再多了一个log

牛客多校1H

定义函数\(f_h(x)=x\text{ mod } h\)，求最小的\(h\)使得\(f_h\)是给定有限正整数集的perfect hash

不是perfect当且仅当存在\(a\neq b\)，却\(f(a)=f(b)\)，即 \(a_i-a_j\equiv 0\pmod h\)，其中\(i\neq j\)
也就是说如果我们能算出任意两对数的差值，就可以方便地枚举答案了
直接开两个桶bct[i]和bct[INF-i]，做卷积就好了....

这篇关于集训补题合集的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！