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 […]
[九省联考 2018] 一双木棋
思路 WC 试机题,没想到居然能做出来QwQ 放过棋子的部分一定是一个阶梯形的,我们试图用状压表示一下这个形状,可以想出一种简单的方案,用一个$n+m$位的二进制数,如果一位是$1$就表示这一段轮廓线 […]
[SCOI 2011] 地板
Luogu P3272 思路 设$0$表示没有插头,$1$表示一个还没拐过弯的插头,$2$表示一个拐过弯的插头,大力讨论就可以了 反正插头DP就是一种大力讨论出奇迹的东西 代码
[bzoj 3125] CITY
bzoj 3125 思路 很平凡的插头DP 代码
[ural 1519] Formula 1
Luogu P5056 思路 传说中的插头DP模版题 写插头DP题解是不可能的,这辈子都不可能的,所以贴一个dalao的链接好了 代码
[bzoj 2159] Crash 的文明世界
bzoj 2159 思路 $$n^k=\sum \limits_{i=1}^k S_k^i\cdot i\cdot C_x^i$$ 故原式可进行如下化简 $$S(i)=\sum\limits_{j=1 […]
[HAOI2010]最长公共子序列
思路 LCS转移的时候顺便记录一下方案数就行,滚动数组 代码
[HNOI2008]玩具装箱TOY
Luogu P3195 bzoj 1010 思路 设$f_i$为前$i$个玩具的最小花费,则有转移方程 $$f_i=\min\limits_{0\leq j<i}\{f_j+(i-(j+1)+\ […]