ATC 简单 DP 题解

ABC248F Keep Connect DP 过程中最多形成上下点所在的两个联通块，记录上下点是否连通 $f_{i,j,0/1}$。 ARC123C 1, 2, 3 - Decomposition 先枚举答案，然后搜索转移合法性 $f_{当前位,进位,未终止的123串数}$，既然答案不超过 $5$，复杂度可以保证。 AGC054B Greedy Division 考虑定下了每个数贡献的正负，在正负这一组内的相对位置，那么构造出的操作序列是唯一的。记 $f_{i,j,k}$ 为考虑到第 $i$ 位，放了 $j$ 个到正，和为 $k$。答案为 $\sum_i i!(n-i)!f_{n,i,\frac{\sum a_j}{2}}$。 AGC054A Remove Substrings 注意到答案最多为 $2$，证明用反证是简单的。 ABC145E All-you-can-eat 既然最优化不可撤回可以使用数据结构多一个 $\log$。但是注意到放到最后吃的是选择吃的时间最长的一定不劣，所以排序后直接背包就可以了。 ARC132C Almost Sorted 可以状压，既然 $d\le 5

训练日记 · 2024-02-13 · 464 人浏览

EDU VP 题解

Edu 160 A Rating Increase 枚举分割，能中止就中止。 B Swap and Delete 枚举删除数量，能否使得 $0$ 和 $1$ 数量相等。 C Game with Multiset 使用 map 统计每个数字个数，查询时从大到小能减则减。 D Array Collapse 发现对于序列的任意区间一定无法删除最小值。考虑在笛卡尔树上 DP。答案可以由两棵子树相乘，若在区间左边或右边存在祖先，则区间最小值可以被从左 / 右边删除。 E Matrix Problem 费用流建图，左侧点表示行，右侧点表示列，边表示网格中某个点，边权为 $1$ 或 $-1$ 分别对应点初始值为 $0$ 和 $1$。 Edu 159 A Binary Imbalance 注意到若能插入一次，便可以沿着插入无穷次。 B Getting Points 二分工作日数量，每天上节课并处理出最多可以完成的任务数量。 C Insert and Equalize 若从结果反过来考虑，可以发现过程中一定可以存在某个时刻序列除 $a_{n+1}$ 都等于原序列最大值，于是 $x$ 为原序列所有数与最大

题解笔记 · 2024-01-08 · 490 人浏览

DFS 生成树及其应用

无向图的 DFS 生成树 若有一张图 DFS 的结果如下，其中黑色边表示 DFS 过程中走的边，灰色表示未走的边。 称如 $(1,3)$，DFS 经过的边为树边（span-edge），如 $(5,1)$ 连接一个点及其祖先的非树边为返祖边（back-edge）。本图只存在这两种边，且并非偶然。记连接生成树中旁系亲属的边为横叉边（cross-edge），则它在图中不会存在。证明如下： 若有一条边 $(u,v)$，在探索到 $u$ 时 $v$ 尚未探索，则 $(u,v)$ 为非树边等价于探索 $u$ 其他子节点时访问到了 $v$，$u$ 和 $v$ 满足祖先关系。 这是无向图 DFS 生成树一个重要性质。 找桥 返祖边不可能是桥，因为仅保留树边的生成树就足以保证连通。 若树边 $(u,v)$ 是桥，将原图分成两个不连通的部分，则其中一个为以 $v$ 为根的子树，子树中连接的最低深度的返祖边不能连通到 $u$ 或 $u$ 的祖先。基于这一个要求，就有通行的实现方法，记录所有子树的 $low$。 将无向图定向生成强联通分量 若存在割边则一定无解。 否则直接对其 DFS，将树边从父到子定向

学习笔记 · 2024-01-07 · 530 人浏览

ATC 小清新杂题题解

ABC225G X 假如已经确定了选择的点，考虑所有共一个角的点对。若选且只选了一个点，则共角一定是划线方案的一个端点，费用为 $\frac{c}{2}$。这很最小割，集合划分模型。额外维护第 $0,n+1$ 行和第 $0,m+1$ 列即可。 ABC137F Polynomial Construction 妙妙构造题。题意很像拉插，而拉格朗日插值和中国剩余定理的灵魂在于 $n$ 项的和式。对于每个确定的 $x$，当前点可以得到 $y$，其他确定点只能得到 $0$。仿造这个过程，我们有 $1-(x-a)^{p-1}$ 用于调整取值，二项式定理拆开即可。 ABC135F Strings of Eternity 假如 $s$ 已经被复制扩展使大小达到 $+\infty$，那么我们唯一可以调整的就是 $t$ 在模 $\lvert{s}\rvert$ 意义下的起始位置。若该位置可以放置，则后继位置也是固定的，这是一个 $n$ 点最多 $n$ 条边的图。求最长路或输出环即可。 ABC225F String Cards 贪心是错误的，但是若 $s+t<t+s$，则在答案中 $s$ 一定在 $t

训练日记 · 2024-01-05 · 338 人浏览

远古 NOI 水题题解

P1244 NOI2000 青蛙过河 每一次操作，先将荷叶铺满生成一垛，再类似二进制分组的合并。上限为 $(m+1)2^n$。 P4408 NOI2003 逃学的小孩 有结论 A 和 B 一定要在树的直径的两端。找到一条直径，并以两点跑一次多源最短路即可。 P1949 NOI2001 聪明的打字员 直接 $10$ 进制状压 bfs 可以过。 P5751 NOI1999 01串 先进行前缀和，然后每个限制都是对两个前缀和的差的限制。差分约束板子题。 P5763 NOI1999 内存分配 小模拟题，有点 CSP-S 2023 T3 的感觉。直接记录每一个被占用的内存块，暴力维护队列即可。 P7302 NOI1998 免费的馅饼 不难有 $f_i$ 表示最后一个接的点是 $i$，从 $j$ 点转移有限制 $\lvert{p_i-p_j}\rvert\le2(t_i-t_j)$，由绝对值的非负性可以拆成两个必须同时满足的条件 $$ \left \{ \begin{array}{l} p_i-p_j\le2t_i-2t_j\\p_j-p_i\le2t_i-2t_j \end{array} \ri

训练日记 · 2024-01-05 · 438 人浏览
2023 - 2025 YRQ 的博客. All Rights Reserved.
Theme Jasmine by Kent Liao