二分图判定 没啥技巧，最难的是把图论模型建起来。 luogu1330 封锁阳光大学 相邻两个点只能封锁一个，但是要覆盖所有边。对应到二分图上就是左部右部点的数量取较小值。 图可能不连通，取的是每一张二分图的左右边的较小值。 #include<bits/stdc++.h> using namespace std; #define int …

[ARC101E] Ribbons on Tree 对于以 $x$ 为根的子树，如果 $(x,fa_x)$ 的边没有被覆盖，那么说明子树内没有任何一个点与子树外的点匹配。 把这些没有被覆盖的边看作特殊边，那么整棵树就被若干特殊边划分成了若干连通块。我们要求的是不含任何特殊边的匹配方案。 考虑容斥。钦定一个边集 $S$，表示 $S$ 内的边一定是特殊…

聊聊状态压缩。 顾名思义，就是把一个状态压成一个整数，从而使得问题的所有状态可以度量。 一般都是用二进制状态压缩来表示子集与全集的关系，对应着二进制每一位都是 $0$ 或 $1$。更高的进制能表示更多的信息，但状态的数量也会随之增加，并且实现的时候要自己手写位运算，较为复杂，本文不会涉及。 信息的表示 luogu7076 [CSP-S2020] 动…

搜索剪枝 纯搜索剪枝题很少，早就融入各种搜索之中了。 但是在各种多项式时间的搜索里，剪枝仍然是重要的。 目前只有一道题，以后看情况加。 luogu1120 小木棍 能注意到长度一定是所有木棍总和的倍数，并且至少是 $\max{a_i}$，所以只对这部分搜索就行。 设dfs(cnt,len,lst)表示当前还剩下 $cnt$ 根木棍要拼接，当前木棍剩…

专门放一些不大可能会考的计数题，长期更新。 大约是输入的只有问题规模，输出的只有相应方案数。 luogu6561 [SBCOI2020] 人 两两不相邻这个条件不是很容易搞。 考虑把 $[1,2m]$ 分成 $m$ 个数对，形如 $(\text{odd},\text{even})$，其中 $\text{odd} +1 =\text{even} $ …

计数杂题。 CF840C On the Bench 先进行一些基本的观察。 $\texttt{Observation}$ ${a_i}$ 中乘积为完全平方数的数集，一定是相对封闭的。因此我们可以将 ${a_i}$ 划分成若干个集合，满足其中两两乘积为完全平方数。 $\texttt{proof}$ 考虑和 $a_i$ 相乘为完全平方数的数集 ${a_…

满足「结合律」的静态信息 CF1175E Minimal Segment Cover 预处理 $rt_x$ 表示点 $x$ 经过一条线段能到达的最右边的点。 跳区间显然是满足结合律的，可以倍增之，复杂度 $O(n \log_2 n)$。 这类题目有一个重要的小技巧：为了满足最优性，倍增时跳到不能到达 $y$ 的最远的点 $p$，然后判断能一次跳过 …

Trie luogu2922 [USACO08DEC]Secret Message G 给定两个字符串序列 $a$ 与 $b$，对于 $b$ 中每个字符串 $t$，求 $a$ 中有多少个字符串 $s$，满足以下两个条件之一 $s$ 是 $t$ 的前缀。 $t$ 是 $s$ 的前缀。 两个字符串序列中所有字符串长度之和不超过 $500000$。 把 …

突破口永远在环上。 找环是常用操作，但是并没有一个合适的模板。 笔者在写这篇文章之前就做过一些基环树的简单题，但是每一次写的找环都不尽相同。仅仅用dfs的回溯模拟一个栈，显然是不够公式化的，且容易出 bug，因此我们需要确定一种可靠的写法。 关于dfn的那套理论再合适不过了。 当然这玩意只能找一个环。 int cnt, num, fa[N]…

树形 DP 计数。 luogu8867 建造军营 对于图中一条非割边，看守与否都相同，因此可以用 Tarjan 算法求出边双再缩点，把非树边单独拿出来，讨论每一条树边。 然而貌似不是很好做，子树外是否建造会影响子树内。考虑设 $f_x$ 为军营只在以 $x$ 为根的子树中出现，且至少存在 $1$ 个军营的方案数。 转移时对于边 $(x,y)$，如果…