好多题都不会啊，这可咋整
先写着吧....大概会割掉....
cf490
求带点权树上的简单路径构成的点权序列的最长上升子序列的长度的最大值
一个比较容易想到的做法就是dp，设f[x,i]表示以x为根的子树中，以i为结尾的最长上升子序列的长度，g[x,i]就是下降。这里我们规定只能选取深度递降的顺序
那么每次合并子树就好了，这样直接做是n^2logn的。还可以用线段树记录这个结尾的状态，那么两个dp状态合并就是线段树合并了，这样就少一个n
牛客多校1C
给一棵树要求删掉一个节点，使得剩余每棵树中的cf490的答案最大值最小
这个做法就很强。首先可以找原树的最长路径所在的链c，那么要删的点一定在这条链上（否则最大值不变）
不妨假设删掉了一个点x，那么这条最长链被分成两部分c1和c2，此时再按照cf490的方法求一次最长链得到c'，则分类讨论
- c和c'相交，这个时候删掉它们的交点会更优秀（不仅让原本的最长变短了，还让变短后的最长也变短了）
- c和c'相离，这个时候删掉c上的任意一点都一样
于是就可以发现如果我们不断这么做下去，最终将得到若干条链的交，且这个交在不同层次的最长链上，删掉交里的点一定是最优秀的
每次对当前的交二分（取中点），判断新的交在哪一侧，这样就只是再多了一个log
牛客多校1H
定义函数(f_h(x)=x ext{ mod } h)，求最小的(h)使得(f_h)是给定有限正整数集的perfect hash
不是perfect当且仅当存在(a
eq b)，却(f(a)=f(b))，即 (a_i-a_jequiv 0pmod h)，其中(i
eq j)
也就是说如果我们能算出任意两对数的差值，就可以方便地枚举答案了
直接开两个桶bct[i]和bct[INF-i]，做卷积就好了....
牛客多校2I
没啥好说的，纯粹是菜
一开始竟然整了一个迭代加深的dfs，事实上直接用四维bfs就好了....
牛客多校2L
欧老师：一般无向图没啥好的性质，考虑均摊或者度数分块就行了
考虑暴力怎么做。每次更新一个点之后暴力枚举它的邻居更新邻居的状态（是否为冠军）
为了不那么暴力对度数分块，记度数>sqrt(n)的点为大点，否则为小点，那么大点的数量是有一个上界A的，而小点的度数有一个上界B。
若修改点是小点，那么就直接暴力，这部分是O(nB)的
若修改点是大点，那么就分邻居的情况讨论：
- 邻居是大点，那么这样的 大-大 点对不会超过A个
- 邻居是小点，那么我们对每个大点x维护一个集合S，按照点权顺序存放x的既是小点又是冠军的邻居。由于当前点的权值不减，因此当前大点的冠军小点邻居不增
hdu01G
n个人传1个球，初始球在1号人手上，每次拿球的人随机传给别人。现在已知球回到1号人的方案数为x，求这是传了几轮得到的方案数
设f[i]表示i轮球回到1的方案数，则考虑1所在圈的大小：
- 恰好为2，就是f[i-2] * (n-1)，即1和另一个人配对组成长度为2的圈
- 至少为3，就是f[i-1] * (n-2)，即在前一个圈中的最后一轮传球中插入一个除1和x外的第三人。
于是就可以用特征根求通项，解一个BSGS就好了
hdu01J
给定序列(left{a_n
ight})
Q次询问求下标l到r，值域a到b之间出现了多少不同的数字
已经不会套路了....
记last[i]为第i个位置的数上一次出现的位置，那么统计区间内不同的数字，就是统计区间内last[x]< l的x的数量
于是就变成了一个三维偏序问题。经典的离线莫队分块平衡复杂度的操作可以看HH的项链(实在愧对队友，这题俺还写过...)
hdu02J
给定(x,p)，(p)为质数。规定(a_n=nx ext{ mod } p)，求数列(left{a_1,a_2,ldots,a_{p-1} ight})逆序对的奇偶性
这题就是Zolotarev定理...({mathbb {Z}_p}^*)中的元素(a)的勒让德符号(left(frac{a}{p}
ight))和排列(p_i=ai ext{ mod } p)的奇偶性(逆序对的奇偶性)是相关的。
上课讲的方法比较神奇，这里其实可以直接算
排列(left{p_i
ight})的逆序对可以这么算({dfrac{prodlimits_{i<j}{left(p_i-p_j
ight)}}{prodlimits_{i<j}{left(i-j
ight)}}}=prodlimits_{i<j}{dfrac{p_i-p_j}{i-j}}=prodlimits_{i<j}{dfrac{xi-xj}{i-j}}=x^{frac{p-1}{2}})
牛客多校3B
这场好难，不过做的都1A了...算是可喜可贺吧
给n*m的棋盘要求染色。每次染色代价为对因位置的权值，并且规定若某矩形的三个顶点染色了，则第四个点可以免费染。求染黑整个棋盘的最小代价。
容易发现答案至多染n+m-1个点，否则必然会出现某个四角都染色的矩形。
把行和列看成n+m个点，染色则相当于连一条i-j带权边，那么免费染色的含义就是把长度为3的边连成一个4元环。由于免费操作不改变图的连通性，因此最终全部染黑就要求初始的选择联通了所有n+m个点，这就是求一个最小生成树。