10-31 题
目录
- 10-31 题
- G - Minimum Permutation
- G - P-smooth number
- G - Dream Team
- P14254 分割（divide） - 洛谷
G - Minimum Permutation
可以用一个栈维护当前选了哪些数，从前往后考虑，首先检查 \(a_i\) 是否不在栈中，是则考虑加入，若当前栈顶大于 \(a_i\) 且其在之后有出现那么就可以把栈顶 pop 掉。
G - P-smooth number
考虑 meet in middle，对前 \(9\) 个质数跑出来的结果和第 \(10\sim 25\) 的质数跑出来的结果用数组存起来。
然后把它们拼起来，排序后，枚举前面的数组，双指针维护后面的数组能选到最大多少。
G - Dream Team
费用流板子。
P14254 分割（divide） - 洛谷
除了根节点的连通块，其他连通块的根节点所在的深度一样，并且第一个连通块的最大叶子最小。
枚举深度，那么小于该深度的点都属于根节点，然后就分割出若干连通块，枚举第一个连通块的最大叶子深度（这是因为更小的最大叶子可以被根节点选掉），设有 \(t\) 个该深度的连通块，\(s\) 个大于该深度的连通块。
若和它一样也取到该深度的连通块在 \(2\sim k\) 的连通块存在内则答案为 \(t\times (A_{s+t-1}^{k-1}-A_{s}^{k-1})\)，
否则 \(k+1\) 取到和它一样深度，且 \(2\sim k\) 取到 \(s\) 中，要求 \(s=k-1\)，方案数为 \(t\times (k-1)!\)。