性质&构造性

wfycsw · 2023-09-11 17:43:15 · 个人记录

\text\ By\text\ Myself

P7737

Description

经典的闯关式找性质题目。

首先缩点变DAG，然后根据题目性质，进行拓扑排序将最后一个使 y 的度数为零的点 x 连边 x->y ，由于题目性质，这不会影响原本的联通性，于是就变成了一棵叶向树。

然后对于询问操作，考虑将新增边的 2\times k 个端点和 S,T 关键点，构建虚树，有点权 siz 和边权 \sum siz ，同时连新增边，边权为 0 。然后从 S 和 T 分别BFS ， 算交集的权值和即可。

qoj3300

给定数列 a_1,a_2,\dots,a_n 和 b_1,b_2,\dots,b_m ，定义矩阵 A 有 A_{i,j}=a_i+b_j ，定义一个点 a_{i,j} 为h黑色当且仅当 a_{i,j}\ge 0 ，计数二元组 (S,T) 数量满足，只能通过往下或往右，存在从 (1,S) 到 (n,T) 只经过黑色格子的路径。

喵喵题

首先有一个显然的性质:任意两行的黑色格子有包含关系。

考虑一个优秀的暴力，记 A(i,j)=0/1 表示 (1,i) 是否能到 (n,j) ，求 A(i,j) 可以通过判断能否到上一个 A(k,j)=1,k>i ,递推转移是 O(n^2) 的。

考虑优化。发现 (1,i) 能到 (n,j) 的必要条件是存在一个列k纯黑,所以将所有贯穿上下的纯黑的列求出来，作为中转站，接着求出每个纯黑的列中能到达的最靠后的纯黑的列，并处理出每个 (1,i) 是否能到往后最近的纯黑的列以及每个 (n,j) 是否能到往前最近的纯黑的列。一条对答案有贡献的路径可以刻画为 (1,i)->(?,k1)->(?,k2)\dots->(n,j) 。

CF1720E

记 cnt 为初始颜色数。

对于 k\le cnt ，答案为 k-cnt 。

对于 k<cnt ，答案不超过 2 ，因为可以通过构造 2 个正方形的通解。(构造十分nb，这里不细说)

只需判断答案能不能为一，用差分前缀和即可。