2024-02-14 模拟赛补题
考场上写出:
1if (sub1 :: check()) sub2 :: solve();
这个sb操作直接少 60pts。
T1. 脐
题意
给定一个长度为 nnn 的排列 ppp,求有多少棵树满足:
∀1≤i<j≤n\forall 1 \le i < j \le n∀1≤i<j≤n,如果树中存在边 (i,j)(i, j)(i,j),那么一定存在边 (pi,pj)(p_i, p_j)(pi,pj)。
答案对 998244353998244353998244353 取模。
1≤n≤2×1061 \le n \le 2 \times 10^61≤n≤2×106。
题解
不会。
T2. 最初日
题意
给定一个 n×nn \times nn×n 的矩阵 aaa,每行每列都是 1∼n1 \sim n1∼n 的排列。
你要选出 nnn 个格子,满足每行每列都只有一个格子被选中。设 rir_iri 是第 iii 行被选中的格子的元素,cic_ici 是 iii 列被选中的格子的元素。要求你选的格子满足,∀1≤i,j≤n\forall 1 \le i, j \le n∀1≤ ...
网络流学习笔记
网络最大流
原版
板子没什么好说的,代码:
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657struct flow { int head[N], nex[M << 1], tot = 1, dep[N], S, T, cur[N]; bool vis[N]; struct E { int to, nxt, flow; } edge[M << 1]; void ad(int x, int y, int z) { edge[++tot] = (E) {x, y, z}; nex[tot] = head[x]; head[x] = tot; } void add(int x, int y, int z) { ad(x, y, z); ad(y, x, 0); } bool ...
P4426 毒瘤笔记
前置知识点:虚树,dp。
题意
给定一个 nnn 个点 mmm 条边的无向简单联通图,满足 n−1≤m≤n+10n - 1 \le m \le n + 10n−1≤m≤n+10。求图的独立集个数,对 998244353998244353998244353 取模。
题解
首先,注意到 m≤n+10m \le n + 10m≤n+10,也就是说非树边只有最多 111111 条。将这些非树边连接的 s=22s=22s=22 个点(下面称为关键点)找出来,接着 2s2^s2s 枚举每个关键点的状态,最后对整棵树树形 dp 就可以在 O(n2s)\mathcal{O}(n2^s)O(n2s) 复杂度下解决这个问题,可以得到 70+pts 的好成绩。
于是沿着这一条思路,可以想办法优化。我们先将朴素树形 dp 给推出,设 fx,0/1f_{x, 0 / 1}fx,0/1 表示 xxx 为根的子树中 xxx 选或不选的方案数。那么有:
{fx,0=∏v∈x.son(fv,0+fv,1)fx,1=∏v∈x.sonfv,0\begin{cases}
f_{x, 0} = \prod\limits_{v ...
线性代数学习笔记
高斯消元
高斯消元是用于求解 nnn 元线性方程组的算法。这里不讲别的,只讲算法流程。
首先,可以用一个 nnn 行 (n+1)(n + 1)(n+1) 列的矩阵来表示一个 nnn 元线性方程组:
{a1,1x1+a1,2x2+⋯+a1,nxn=a1,n+1a2,1x1+a2,2x2+⋯+a2,nxn=a2,n+1⋯an,1x1+an,2x2+⋯+an,nxn=an,n+1\begin{cases}
a_{1, 1}x_1 + a_{1, 2}x_2 + \cdots + a_{1, n} x_n = a_{1, n + 1}\\
a_{2, 1}x_1 + a_{2, 2}x_2 + \cdots + a_{2, n} x_n = a_{2, n + 1}\\
\cdots\\
a_{n, 1}x_1 + a_{n, 2}x_2 + \cdots + a_{n, n} x_n = a_{n, n + 1}
\end{cases}
⎩⎨⎧a1,1x1+a1,2x2+⋯+a1,nxn=a1,n+1a2,1x1+a2,2x2+⋯+a2,nxn=a2,n+1⋯a ...
P4565 & CF757G 笔记
前置知识:线段树合并,可持久化线段树,边分治,可能会用到一点点虚树。
P4565
边分树神题啊。。。
题意
给定两棵边有边权的树 T1,T2T_1, T_2T1,T2,结点数都为 nnn。设 di(x)d_i(x)di(x) 表示第 iii 棵树上 xxx 的带权深度,
求一组点对 (x,y)(x, y)(x,y),使得 d1(x)+d1(y)−d1(p)−d2(p′)d_1(x) + d_1(y) - d_1(p) - d_2(p')d1(x)+d1(y)−d1(p)−d2(p′) 最大,
其中 p,p′p, p'p,p′ 分别代表 x,yx, yx,y 在两树上的 LCALCALCA。为了方便,只需输出最大值。
题解
先考虑变换一下这个式子,设 disi(x,y)dis_i(x, y)disi(x,y) 表示 (x,y)(x, y)(x,y) 在第 iii 棵树上的距离。那么原式就等于 12(dis1(x,y)+d1(x)+d1(y)−2d2(p′)){1 \over 2}(dis_1(x, y) + d_1(x) + d_1(y) - 2d_2 ...
P4220 通道笔记
边分治神题。
前置知识:边分治,虚树。
题意
给定 333 棵有边权的树,每棵树都含有 nnn 个节点,令 disi(x,y)dis_i(x, y)disi(x,y) 表示 (x,y)(x, y)(x,y) 在第 iii 棵树上的距离。求一组 (i,j)(i, j)(i,j),使得 ∑k=13disk(i,j)\sum\limits_{k = 1}^3 dis_k(i, j)k=1∑3disk(i,j) 最大,为了方便,只需输出最大值。
题解
考虑边分治。下面用 TiT_iTi 来表示第 iii 棵树。
对 T1T_1T1 进行边分治,设 d1(x)d_1(x)d1(x) 表示 xxx 点到分治边一侧的距离,那么答案就转化成了 d1(i)+d1(j)+dis2(i,j)+dis3(i,j)d_1(i) + d_1(j) + dis_2(i, j) + dis_3(i, j)d1(i)+d1(j)+dis2(i,j)+dis3(i,j)。然后将当前分治块内的所有点在 T2T_2T2 上拉出来,建一棵虚树 T2′T'_2T2′,再设 d2(x)d_2(x ...
动态 DP 学习笔记
动态 DP
P4719 动态 DP:
题意
给定一棵 nnn (n⩽105n \leqslant 10^5n⩽105) 个点的树,点带点权。
有 mmm (m⩽105m \leqslant 10^5m⩽105) 次操作,每次操作给定 x,yx,yx,y,表示修改点 xxx 的权值为 yyy。
你需要在每次操作之后求出这棵树的最大权独立集的权值大小。
题解
首先考虑 m=0m=0m=0 时的做法,可以简单地设计出 dp 转移方程式 fx,0/1f_{x, 0 / 1}fx,0/1 表示 xxx 选或不选的答案。
{fx,0=∑v∈x.sonmax{fv,1,fv,0}fx,1=px+∑v∈x.sonfv,0\begin{cases}
f_{x, 0} = \sum\limits_{v \in x.\text{son}} \max\{f_{v, 1}, f_{v, 0}\} \\
f_{x, 1} = p_x + \sum\limits_{v \in x.\text{son}} f_{v, 0}
\end{cases}
⎩⎨⎧fx,0=v∈x.son∑max{fv,1,fv,0 ...
P4338 历史笔记
神题啊!神题(赞叹)
形式化题意
给定一棵 nnn 个点的树,第 iii 个点有点权 aia_iai。且每个点都有颜色,初始时颜色都为 111,第 iii 个点的颜色是 cic_ici。
你可以对一个点 xxx 进行一次操作:
计数有多少 vvv,满足 vvv 在 x→1x \to 1x→1 的路径(包含 xxx 和 111)上,且 cv≠xc_v \ne xcv=x。
将满足条件的 vvv 的个数记作 cntcntcnt,并使 ans:=ans+cntans := ans + cntans:=ans+cnt,初始时 ans=0ans = 0ans=0。
将 x→1x \to 1x→1 路径上的点颜色全部变为 xxx。
现在知道了第 iii 个点总共被操作 aia_iai 次,问如何安排 ∑a\sum a∑a 次操作,使最后 ansansans 最大。然后还有 mmm 个询问,每次如下:
x w 表示将 ax:=ax+wa_x := a_x + wax:=ax+w 后的答案。
题解
第一步就是一个比较难的性质的观察:每个点对答案的贡献是相互独立的。这里每个点对答案 ...
P3703 树点涂色笔记
又是一道妙题,加深了蒟蒻对 LCT\text{LCT}LCT 的理解。
题意
给定一棵 nnn 个节点的有根树,根节点为 111。最开始每个节点都有颜色,且颜色互不相同。
定义一条路径的权值为:路径上点的不同颜色数。
现在一共会有 mmm 组询问,每组询问有三种:
1 x 将 xxx 到根节点 111 上的所有点都染色为以前从未出现过的颜色。
2 x y 询问 x→yx \to yx→y 路径的权值。
3 x 询问 xxx 的子树内的结点中,到根节点的路径的最大权值。
题解
思路
考虑如何维护 111 操作,容易想到:任一时刻,对于每种颜色,拥有该颜色的点在树上的联通块有且仅有一个,且一定是直上直下的链。
这个性质的存在,使得此题可以用 LCT\text{LCT}LCT 解决。一个经典的处理方法是:
对于 LCT\text{LCT}LCT 上的一条边,若两端点的颜色相同,则该边为实边。
若两端点颜色不同,该边为虚边。
容易证明这种赋实边、虚边的方法是符合 LCT\text{LCT}LCT 的性质的。
所以操作 111 就可以转换成 LCT\text{LCT}LCT 的 acce ...
P5024 保卫王国笔记
神题,神题啊!!(战术后仰)
题意
给定一棵 nnn 个节点的树,点有点权。有 mmm 个询问,每次询问规定某两个点选或不选,求最小点覆盖。
题解
概念
做题的第一步是:看懂题意。
点覆盖:在树上选择某些点,使得对于树上的每一条边,都满足两端点至少有一点被选。
最小点覆盖:即选择的点点权和最小的点覆盖。
独立集:在树上选择某些点,使得对于树上的每一条边,都满足两端点没有同时被选。
最大独立集:即选择的点点权最大的独立集。
不难看出,**一棵树上的点覆盖和独立集是一一对应的,一个点覆盖的补集就是一个独立集。**所以,最大独立集是最小点覆盖的补集。(虽然这些东西和题意无关,但还是可以扯一下)
思路
先考虑没有询问时,如何求得最小点覆盖?答案是显然的,直接树形 dp 即可,设 fx,0/1f_{x, 0 / 1}fx,0/1 表示 xxx 为根的子树中,xxx 选或不选的最小点覆盖权值和,则有:
fx,0=∑v∈x.sonfv,1fx,1=∑v∈x.sonmin{fv,0,fv,1}+px\begin{aligned}
f_{x, 0} &= \sum\li ...










