2024.5 做题记录

5.09

CF575A

维护转移矩阵，线段树维护一段区间的矩阵乘法。

CF1575H

建 KMP 自动机， $dp_{i,j,k}$ 表示前 $i$ 位，当前自动机上走到 $j$ ，已经匹配了 $k$ 次的最小代价。当转移到终止节点时匹配次数加 $1$ 。

AT_codefestival_2016_final_h

$f_{i,0/1}$ 表示从后往前走到 $i$ ，谁先手。发现 $f_{i,0}=-f_{i,1}$ ，改为一维。 $f_i=\min -f_j+sum_{j-1}-sum_{i-1}$ 。只与 $(i,n]$ 的 $\min -f_j+sum_{j-1}$ 有关。 $mn=\min(mn,2\times sum_{i-1}-mn)$ 。

因为 $a_i\le 10^6$ ，改变 $a_n$ 时 $mn$ 的初值也只有 $10^6$ 种，而中间 $sum_{i-1}$ 不变。连边 dfs 记录每个 $mn$ 初值会变成什么。

5.10

CF1517F

容斥求出半径小于 $r$ 的方案数。 $dp_{u,x,y}$ 表示 $u$ 的子树内，最深的未染色点的距离和最浅的染色点的距离。发现 $x,y$ 只有一个有用。前后缀和优化，状态数 $O(dep)<O(siz)$ 。

CF1951G

用相邻两个球之间的距离来描述一个状态，鞅与停时定理。

1=\frac{1}{n}\sum f(a_i)+f(a_{i\mod n+1})-f(a_i-1)-f(a_{i\mod n+1}-1)

差分 $g(x)=f(x\mod n+1)-f(x)$ 。

n\sum g(a_i-1)-g(a_i)

令 $g(x)-g(x-1)=\frac{n}{m}x$ ， $g(0)=f(0)=0$ ， $g(x)=-\frac{n}{m}\binom{x+1}{2},f(x)=-\frac{n}{m}\binom{x+1}{3}$ 。终止势能为 $f(m)$ 。

CF1007B

$O(n\sqrt n)$ 预处理出每个数的所有因数，记为集合 $p_i$ 。显然题目要求计数 $u\mid A,v\mid B,w\mid C$ 。容斥，大力分讨。可以用 bitset 维护交集。如果把分解因数写成先分解质因数再 dfs 求因数，复杂度 $O(n)$ ，常数约为 $400$ 。

5.12

CF662C

状压每一行，记录每种状态在 $m$ 列上出现的次数和最小代价，fwt。 $ans_{i\oplus j}=\sum num_i\times val_j$ 。

模板子集卷积

加一维记录集合元素个数， $f_{popcount(i),i}=a_i$ 。先将每一维 or 卷积，再 $O(n^2)$ 将外层加法卷积。复杂度 $O(n^2 2^n)$ 。

CF1034E

无法子集卷积。因为对 $4$ 取模，可以将 $a_i$ 乘 $4^{popcount(i)}$ ，然后进行不取模 or 卷积。如果 $a_i\times b_j\to c_k$ 且 $i\text{&} j\neq 0$ ， $popcount(i)+popcount(j)>popcount(k)$ 。最后 $c_i$ 除 $4^{popcount(i)}$ 再对 $4$ 取模。

CF960G

枚举最大值的位置，左边有 $a-1$ 个最大值，右边有 $b-1$ 个。分治NTT求 $\prod (x+i)$ 。

5.13

CF377D

$\max l_i\le L\le \min v_i\le \max v_i\le R\le \min r_i$ 。矩形的交，扫描线。

5.14

CF1895F

容斥。存在 $a_i\in [x,x+k-1]$ 的方案数等于 $\min a_i\le x+k-1$ 的方案数减 $\max a_i<x$ 的方案数。当确定了一个序列的最小值和差分数组就可以确定一个序列。前半部分方案数为 $(x+k)\times (2k+1)^{n-1}$ 。后半部分矩阵快速幂 $O(x^3\log n)$ 。

5.15

CF1886E

观察发现每个项目只与程序员数量和最小值有关，所以每个项目对应能力值连续的程序员最优。状压项目数。设 $dp_{i,s}$ 为前 $i$ 个程序员匹配的项目状态为 $s$ 是否可行，无法接受。交换维度，改为 $dp_s$ 表示状态 $s$ 能与前缀 $[1,i]$ 匹配的最小 $i$ 。

全选不一定优。预处理 $f_{i,s}$ 表示第 $i$ 个项目从 $j$ 开始匹配程序员，最少要匹配到哪里。

5.17

CF249D

$j$ 贡献到 $i$ 满足 $x_j<x_i,y_i\times b-x_i\times a>y_j\times b-x_j\times a,y_i\times d-x_i\times c<y_j\times d-x_j\times c$ 。发现第一个限制无用，随便维护。

5.20

CF79D

异或差分后 $2k$ 个关键位置，状压。 $u,v$ 最短路等于同时删 $u,v$ 的代价。

CF626F

$dp_{i,j,k}$ 表示分了前 $i$ 人， $j$ 组没封闭，代价为 $k$ 。按权值从小到大加入，每个人代价是所有没封闭的组的数量乘相邻两个权值的差。