ucup
ucup hefei 题解
比赛链接 B 很有意思的题 首先题目的要求为可以拆分成 \(2\) 个不相交的不降子序列 根据 \(dilworth\) 定理,最小链覆盖 \(=\) 最长反链,所以要求最长反链 \(\le 2\) 即原序列的逆序列的最长不降子序列长度 \(\le 2\) 不难得到一个 \(dp\) 做法为: 令 ......
ucup nanjing 题解
比赛链接 D 收获很大的一道题 首先考虑朴素的 \(dp\),令 \(f_{x,i}\) 为 \(x\) 子树中的每一个叶子到 \(x\) 的距离都为 \(i\) 的最小代价 不难列出 \(dp\) 式子为:\(f_{x,i}=\min\limits_{i\in \{0,1\}}\{cost(u,i ......
ucup 题目乱炖
Season 2022 #6299. Binary String 如果 \(0\) 的个数小于 \(1\) 的个数那么就反转 \(01\) 以及反转序列,接下来假设 \(0\) 的个数大于等于 \(1\) 的个数。 称有 \(11\) 的序列为”未完全展开的“,那么序列的种类数有两个阶段:展开过程中 ......
【题解】1st ucup Stage 20: India G - Perfect Strings
考虑卡特兰数 \(C_n = \sum_{i=0}^{n-1}C_iC_{n-1-i}\),故有递推式 \[C = xC^2 +1 \]解出卡特兰数递推式: \[C = \frac{1 - \sqrt{1 - 4x}}{2x} \]考虑本题的递推式: \[F_n = \sum_{i=0}^{n-1} ......