贪心

今日又是三道集训队作业原题。。又没部分分。。 反正我都不会必定爆零就没交了。。 $\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$ 上求出最长 ...

中下 $\text{score：24 + 40 + 0 = 64 rk：23/34}$ Problem A：Mythological V题目描述小S打算送给小M一棵 $n$ 个点的圣诞树，点从 $1$ 到 $n$ 标号，他打算给树上挂上 $m$ 个礼物，每个礼物在树上的某个点上，礼物可以重叠。 小M给了小S $q$ 个限制，其中第 $i$ 个形如“第 $a_i$ 个礼物和第 $b_i$ 个礼物在树上的最短路径经过了点 $c_i$”。 小S想要构造出符合小M条件的挂礼物方案。可怜的小S当然不会啦，所以他向你求助。 数据范围对 $100\%$ 的数据，$n, m \le 250, ~ q \le 5 \times 10^4$ 题解好久没写过 $2-SAT$ 了 虽然我的暴力虽然 $\text{WA}$ 了但竟然没有 $\text{T}$？说不定改对了能过呢 考虑两个礼物 $a, b$ 放置位置经过 $c$ 代表着什么，说明 $a, b$ 放置的位置在以 $c$ 为根的树上位于不同的 $c$ 儿子的子树上 那么现在以 $1$ 为根，设 $g_{i, j, 0}$ 表示第 $j$ 个礼 ...

题目描述有 $N$ 人站在一条数轴上。他们人手一个烟花，每人手中的烟花都恰好能燃烧 $T$ 秒。每个烟花只能被点燃一次。$1$ 号站在原点，$i$ 号 $(1 \le i \le N)$ 到 $1$ 号的距离为 $X_i$。保证 $X_1 = 0$，$X_1, X_2, …, X_N$ 单调递增（可能有人位置重叠）开始时，$K$ 号的烟花刚开始燃烧，其他人的烟花均未点燃。他们的点火工具坏了，只能用燃着的烟花将未点燃的烟花点燃。当两人位置重叠且其中一人手中的烟花燃着时，另一人手中的烟花就可以被点燃。忽略点火所需时间。求至少需要以多快的速度跑，才能点燃所有人的烟花（此时可能有些人的烟花已经熄灭了）。速度必须是一个非负整数 数据范围对 $100\%$ 的数据，$1 \le K, N \le 10^5, ~ 1 \le T \le 10^9, ~ 0 \le X_i \le 10^9, ~ X_1 = 0$ 题解很显然所有人一定会不断向拿烟花的人靠近 可以发现，一个拿烟花棒的人和另一个人相遇时，让另一个人跟着拿烟花的人走直至烟花在灭掉的瞬间将烟花传递的情况和在相遇时传递时一样的（注意相对位置， ...