8.1 ~ 8.31 做题总结
stripe_python
·
·
个人记录
【2】P6640 [BJOI2020] 封印
钦定 i 为 S 中子串的起始位置,求出最长公共子串长度,记为 f_i。枚举最长公共子串的起点 i,则询问 [l,r] 的答案为
\max_{i \in [l,r]} \min(f_i,r-i+1)
二分答案 k,则 \exists i \in [l,r], \min(f_i,r-i+1) \ge k。拆开不等式得 f_i \ge k \land r-i+1 \ge k,转化为 \max\limits_{i \in [l,r-k+1]} f_i \ge k。用 ST 表维护,复杂度 1log。
### 【2】[P6793 [SNOI2020] 字符串](https://www.luogu.com.cn/problem/P6793)
不妨视匹配 $s,t$ 的权值为 $\text{lcp}(s,t)$,转为最大权完美匹配。
对 $A{\tt{\#}}B$ 后缀排序得到 $\text{ht}$ 数组,权值可以描述为 $\text{ht}$ 数组的区间 $\min$。由于区间 $\min$ 满足四边形不等式,或者说相交劣于包含的性质,我们可以直接贪心匹配权值最小的边。
考虑维护贪心过程。对 $\text{ht}$ 建小根笛卡尔树,自底向上贪心。对节点 $u$,我们维护失配的 $s,t$ 数目 $x,y$,并在 $u$ 处尽可能匹配。
形式化地,我们求出 $q=\min(x,y)$,对答案累加 $q \times \min(k,\text{ht}[u])$ 后,将 $x \gets x-q, y \gets y-q$ 传递给父亲进行匹配即可。
线性 SA 可以做到总复杂度线性。
### 【2】[P6657 【模板】LGV 引理](https://www.luogu.com.cn/problem/P6657)
连边 $(x,y) \to (x+1,y)$ 和 $(x,y) \to (x,y+1)$。由于坐标单调,只应计算 $\text{inv}=0$ 的路径权值。
根据组合意义 $e(a_i,b_j)=\dbinom{b_j-a_i+n-1}{n-1}$,构造矩阵求出行列式即可。
### 【3-】[P7736 [NOI2021] 路径交点](https://www.luogu.com.cn/problem/P7736)
将 $e(i,j)$ 设为从第一层 $i$ 号点到最后一层 $j$ 号的点的路径数。构造 $M$ 后求得 $\det M$ 即为答案。
这是由 LGV 的组合意义导出的。
### 【1】[P4336 [SHOI2016] 黑暗前的幻想乡](https://www.luogu.com.cn/problem/P4336)
枚举颜色集合 $S$,对 $S$ 的导出子图求出生成树数目。$S$ 的组合意义是钦定至多,容斥系数 $(-1)^{|U \setminus S|}$。复杂度 $O(n^3 2^n)$。
### 【2+】[P7531 [USACO21OPEN] Routing Schemes P](https://www.luogu.com.cn/problem/P7531)
建超级源汇 $S,T$,再补一条 $T \to S$ 的边,用 BEST 定理求出欧拉回路计数。
由于 BEST 定理不考虑循环同构的欧拉回路,需要消序,除掉 $s! \times (s-1)!$,推一下,结论是除掉 $S$ 的数目。
### 【1】[HDU5909 Tree Cutting](https://acm.hdu.edu.cn/showproblem.php?pid=5909)
<https://www.luogu.com.cn/article/g1eilmzl>。
### 【3】[CF1119H Triple](https://www.luogu.com.cn/problem/CF1119H)
<https://www.luogu.com.cn/article/g1eilmzl>。
### 【3】[P13275 [NOI2025] 集合](https://www.luogu.com.cn/problem/P13275)
<https://www.luogu.com.cn/article/g1eilmzl>。
### 【1+】[QOJ5423 Perfect Matching](https://qoj.ac/problem/5423)
做法和 [CF1519E](https://www.luogu.com.cn/article/bgwzhxzn) 几乎一样,为啥不会呢。
将连边刻画为 $i\pm a_i=j\pm a_j$。从线图还原,建边 $i-a_i \to i+a_i$,转成边的完美匹配,然后按照那个贪心做法来就好了。
### 【2】[P3829 [SHOI2012] 信用卡凸包](https://www.luogu.com.cn/problem/P3829)
给四个圆心丢进去求出凸包。由于凸包转了一圈,所以加上圆的周长就对了。
### 【1】[P3260 [JLOI2014] 镜面通道](https://www.luogu.com.cn/problem/P3260)
**光 = 水。**
水不能流对偶障碍连通,转化成最小割,容量设为 $1$ 求上边界到下边界的最大流即可。
### 【2+】[AGC025D Choosing Points](https://www.luogu.com.cn/problem/AT_agc025_d)
<https://www.luogu.com.cn/article/hmfwsxgr>。
### 【2】[AT_dwango2016qual_e 花火](https://www.luogu.com.cn/problem/AT_dwango2016qual_e)
<https://www.luogu.com.cn/article/zuesdtga>。
### 【2】[QOJ6964 Werewolves](https://qoj.ac/problem/6964)
<https://www.luogu.com.cn/article/gqgn9cb6>。
### 【2】[CF1354G Find a Gift](https://www.luogu.com.cn/problem/CF1354G)
<https://www.luogu.com.cn/article/6ggqxpwk>。
### 【1】[ZR3589 彩虹剖分](https://zhengruioi.com/problem/3589)
做了 40min。$u <v$ 导致 $100 \to 0$。
怎么没有人是我这个做法,hyw。
<https://www.luogu.com.cn/article/1q12w3q6>。
### 【2】[QOJ14975 Judgment of Mahou Shoujo](https://qoj.ac/problem/14975)
<https://www.luogu.com.cn/article/n2ldeqzn> 的 ddp 部分。
### 【2-】[P16958 [SCCPC 2026] 括号序列](https://www.luogu.com.cn/problem/P16958)
<https://www.luogu.com.cn/article/i94l431j>。
### 板刷 Boruvka
<https://www.luogu.com.cn/article/1s6sdmyy>。
#### 【2】[ZR3598 没啥题](https://zhengruioi.com/problem/3598)
#### 【2】[AT_cf17_final_j Tree MST](https://www.luogu.com.cn/problem/AT_cf17_final_j)
#### 【2】[CF888G Xor-MST](https://www.luogu.com.cn/problem/CF888G)
#### 【1】[P9701 [GDCPC 2023] Classic Problem](https://www.luogu.com.cn/problem/P9701)
### 【2+】[QOJ18303 Good Night](https://qoj.ac/problem/18303)
### 【0】[CF1904F Beautiful Tree](https://www.luogu.com.cn/problem/CF1904F)
优化建图以后赋一组拓扑序即可。