二分图

今日又是三道集训队作业原题。。又没部分分。。 反正我都不会必定爆零就没交了。。 $\text{score：NULL rk：NULL}$ Problem A：Birthday题目描述给定 $n$ 个仅包含 a,b 的字符串。 你需要去掉尽可能少的字符串，使得剩下的字符串中不存在某一个串是另一个串的子串。 数据范围对 $100\%$ 的数据，$1 \le n \le 750, ~ \sum\limits_{i = 1}^n |s_i \le 10^7$ 题解原题 CF590E 由于 $n$ 很小，很显然可以对每一对字符串判断一个是不是另一个的子串，如果是就连个单向边，最终形成一个 $DAG$ 然后在上面搞 那么对于建图，先建个$\text{AC}$自动机，在 $trie$ 的结尾存一下编号，然后把每个串扔上去匹配，每次匹配与走到节点 $fail$ 树上的所有编号（即它的子串）连边 当然直接连边肯定会 $T$，实际上你只要往在 $fail$ 树往上找到的第一个编号以及本身节点的编号（如果存在的话）连边，然后传递闭包就好了，这样复杂度就正确了 那么接下来的任务就是在 $DAG$ 上求出最长 ...

前置「Hall定理」 二分图G中的两部分顶点组成的集合分别为X, Y(假设有|X|≤|Y||X|≤|Y|)。G中有一组无公共点的边，一端恰好为组成X的点(也就是存在完美匹配)的充分必要条件是：X中的任意k个点至少与Y中的k个点相邻，即对于X中的一个点集W ，令N(W)为W的所有邻居， 霍尔定理即对于任意W，|W|≤|N(W) 题解由于最坏情况任选 $k$ 个是选一端连续的区间 $[l, r]$，根据Hall定理的 $|W| \le N(W)$ 可以得到$$\begin{aligned}sum[l, r] &\le (r - l + 1 + d) \cdot k \\sum[l, r] - (r - l +1) \cdot k &\le d \cdot k\end{aligned}$$那么就可以在线段树中将每个点的权值设为 $value - k$，然后维护最大子段和 $sumax$ 那么最后 $sumax \le d \cdot k ? TAK : NIE$ 即可 代码1234567891011121314151617181920212223242526272 ...

题意求一个 $n$ 点 $m$ 边的 $DAG$ 的最长反链，在第二行输出构造的其中一种方案，在第三行输出在保证最长反链的前提下，每个点是否能够设置为反链中的点 题解反正证明也不会，就记录一下具体方法 最长反链：对 $DAG$ 点集 $V$，最长反链为一个集合 $S \subseteq V$，满足 $\forall u \in S, v \in S$，$u$ 不能到达 $v$，$v$ 也不能到达 $u$ 根据 $\text{Dilworth}$ 定理，一个 $DAG$ 的最长反链大小等于其最小可重链覆盖大小 对 $DAG$ 传递闭包后，最小可重链覆盖大小可转化为最小不可重链覆盖大小，即最小路径点覆盖 最小路径点覆盖：将 $DAG$ 用若干不相交的链覆盖，即每个点最多被经过一次，最小使用链的个数 那么最小可重链覆盖则是类似，不同之处仅在于每个点可被经过多次 最小路径点覆盖大小 $=$ $n$ $-$ 该 $DAG$ 拆点二分图的最大匹配大小 那么 $\text{Subtask1}$ 就做完了 把 $DAG$ 拆点后最小路径点覆盖就相当于是求该拆点二分图的最大独立集 接下来开始 ...