Description 有一个$1\dots N$的排列$p_{1\dots N}$,定义这个排列的权值为其建出笛卡尔树后所有节点的权值之和,定义一个节点的权值为,如果这个节点有两个儿子$p_a, p […]
分类:DP
[HNOI 2019] 校园旅行
#LOJ 3057. 看到有个$m\leq 10^4$的部分分,就可以开始考虑$O(m^2)$暴力了。用$f_{x, y}$记录一下是否可以从$x$走回文路径走到$y$,之后对每对$f_{x, y}= […]
[十二省联考 2019] 皮配
LOJ #3051. 假如没有$k$个不能选的限制,整个问题可以拆成两个不相互影响的问题——给每个城市确定一个阵营,给每个学校确定一个派系。然后乘法原理直接乘起来就可以了。 现在出现了$K$个限制,但 […]
[bzoj 2369] 区间
bzoj 2369 首先,最优解一定可以通过选两个线段达到。也就是说当选了多个线段的时候,只要选最左边那个和最右边那个就可以达到一样的效果 其次,假如一个线段被另一个线段所包含,那么包括他的可能成为最 […]
[51nod 1727] 小Q的数列
51nod 1727 思路 啊不想写了粘个标解走人(逃 考虑到是双射,并且在$n>1$时,一组Alice数列每个数全加$1$、Bob数列每个数全减$1$就可以得到一组新的解(从数列的生成函数上可以看出 […]
[Luogu P4890] Never·island
Luogu P4890 思路 将所有线段端点排一下序,然后对于某一截线段,可以分以下四种情况: 左端点是出发,右端点是回来。假如两个端点属于属于同一队,那么就将代表这一队的点的点权加上线段长度。假如两 […]
[CodeChef] Graph on a Table
CodeChef TBGRAPH 思路 先考虑一个naive的DP,设$f_{i, j}$为一个二元组,记录走到$(i, j)$最多走的步数和方案数。很显然这是$O(n^2\cdot m^2)$的会T […]
[清华集训 2014] 主旋律
UOJ #37. 思路 考虑如何容斥。设$a_i$为图被划分为至少$i$个强连通分量的方案数,则有$$\text{ans}=\sum \limits_{i=1}^{n}(-1)^{i-1}a_i$$ […]
[LOJ #511] 「LibreOJ NOI Round #1」验题
LOJ #511 思路 我下辈子都不会相信某只猫说什么“代码难度中等偏大” 考虑一下如果我们在做交互题,可以快速地知道一些点必须选,一些点必须不选,一些点随意的情况下的独立集数量,那么应该怎么做。 这 […]
[九省联考 2018] 秘密袭击
LOJ #2473. 思路 首先,原来的问题可以转化为枚举点权,统计每个点权在连通块中第$k$大的方案数。设$a_{i}$为联通块中第$k$大的数大于等于$i$的方案数,则答案为$$\begin{sp […]