RyanLi 的博客 - 笔记
type: channel
link: https://blog.ryanli.top/index.php/tag/%E7%AC%94%E8%AE%B0/
items: 2023 国庆集训 Day 6A 笔记
items: 2023 国庆集训 Day 6B 笔记
items: 2023 国庆集训 Day 5A 笔记
items: 2023 国庆集训 Day 5B 笔记
items: 2023 国庆集训 Day 3B 笔记
items: 2023 国庆集训 Day 4A 笔记
items: 2023 国庆集训 Day 4B 笔记
items: 2023 国庆集训 Day 2B 笔记
items: 2023 国庆集训 Day 3A 笔记
items: 2023 国庆集训 Day 2A 笔记

2023 国庆集训 Day 6A 笔记
type: item
date: 2024-02-14T23:04:00+08:00
description: 更佳的阅读体验：2023 国庆集训 Day 6A 笔记，本文同步发表于 洛谷博客。以下内容为个人总结，如有错误或您有不同见解，欢迎指出。割点 / 割边在无向图中讨论。删掉这个点 / 边，图变得不连通。Tarjan 求割点随便找个根节点，跑 DFS，记录 DFS 访问的时间戳 $dfn$。对于根节点，我们判断其是否是割点，只需判断是否有大于 $1$ 个子树。考虑非根节点 ：考虑非树边长什么样子：一定是从祖先到子孙。那么假设 $x$ 不是割点，那么子树内的每个点都能到 $x$ 的上面部分。设 $low[x]$ 表示 $x$ 子树内，通过非树边走到的最浅是哪里。如果存在 $x$ 的儿子 $y$ 满足 $low[y] \ge dfn[x]$，那么 $x$ 就是割点。int dfn[N], low[N], cut[N], tmp, num, cnt, rt; void dfs(int x, int fa) { dfn[x] = low[x] = ++num; for (int i = h[x]; i; i = ne[i]) { int y = to[i]; if (y == fa) continue; if (!dfn[y]) { dfs(y, i ^ 1), low[x] = min(low[x], low[y]); if (x != rt && low[y] >= dfn[x]) cut[x] = 1; if (x == rt) tmp++; } else low[x] = min(low[x], dfn[y]); } }缩点参考材料stk[++st] = u; for (int i = point[u]; i != -1; i = edge[i].nxt) { int v = edge[i].v; if (!dfn[v]) { Tarjan(v); low[u] = min (low[u], low[v]); // 因为v在u的子树内，所以low[v]可以用于更新low[u] if (low[v] >= dfn[u]) { // 子树中没有可以连到父亲上面的边 cut[u] = 1; dccn++; dcc[dccn].clear(); dcc[dccn].push_back(u); // u是割点，可能包含在多个点双中，不能弹出 while (true) { int w = stk[st]; dcc[dccn].push_back(w); st--; if (w == v) // 做到子树全部弹出为止，不然v的兄弟也会被弹出 break; } } } }Tarjan 求割边void tarjan(int x, int fa) { low[x] = dfn[x] = ++num; vis[x] = true, st[++top] = x; int cnt = 0; for (int i = h[x]; i; i = ne[i]) { int y = to[i]; if (y == fa && (++cnt) < 2) continue; if (!dfn[y]) tarjan(y, x), low[x] = min(low[x], low[y]); else low[x] = min(low[x], dfn[y]); } if (dfn[x] == low[x] && ++sc) while (z = st[top--]) { col[z] = sc, vis[z] = false; if (z == x) break; } }强连通分量在有向图中，如果两个点 $u$，$v$ 满足同时存在从 $u$ 到 $v$ 和从 $v$ 到 $u$ 的路径，则称两个点强连通。如果有向图任意两个点强连通，则称为强连通图。有向图的极大强连通子图称为强连通分量。注意到强连通关系是传递的，所以有向图可以划分为若干不交的强连通分量。在有向图的 DFS 树中，有 树边、非树边（没用）、返祖边（有用） 和 横叉边（部分有用） 的四种边。DFS 到 x 时，我们用栈维护 $x$ 的每个祖先目前的强连通分量。遍历所有 $x$ 的边 $(x, y)$：如果 $y$ 未被遍历过，则 $dfs(y)$。如果 $y$ 被遍历过，如果 $y$ 在某个祖先的强连通分量中，则形成了环，将若干连通分量合并，否则不做更新。合并操作可以通过记录 $low$ 数组实现。int sta[N], num; bool vis[N]; void tarjan(int x) { low[x] = dfn[x] = ++num; sta[++top] = x, vis[x] = true; for (int i = h[x]; i; i = ne[i]) { int y = to[i]; if…

2023 国庆集训 Day 6B 笔记
type: item
date: 2024-02-14T23:04:00+08:00
description: 更佳的阅读体验：2023 国庆集训 Day 6B 笔记，本文同步发表于 洛谷博客。以下内容为个人总结，如有错误或您有不同见解，欢迎指出。矩阵矩阵的运算加 / 减法两个 一样大 的矩阵，对应位置相加 / 减。乘法要求 $n \times m$ 的矩阵与 $m \times k$ 的矩阵相乘，即第一个矩阵的列数等于第二个矩阵的行数。结果是一个 $n \times k$ 的矩阵，即行数等于第一个矩阵的行数，列数等于第二个矩阵的列数。$$ \left[\begin{matrix} 1 & 2 \\ 3 & 4 \end{matrix}\right] \times \left[\begin{matrix} 1 & 2 & 3 \\ 4 & 5 & 6 \end{matrix}\right] = \left[\begin{matrix} 9 & 12 & 15 \\ 19 & 26 & 33 \end{matrix}\right] $$struct matrix { int n, m; // 矩阵的行数 列数 int a[20][20]; // a[i][j] 代表矩阵第 i 行第 j 列 matrix() { // 构造函数 n = m = 0; memset(a, 0, sizeof(a)); } }; matrix operator*(const matrix &m1, const matrix &m2) { // 计算 m1 * m2, O(n^3) matrix m3; // 结果矩阵 m3.n = m1.n, m3.m = m2.m; for (int i = 1; i <= m3.n; ++i) for (int j = 1; j <= m3.m; ++j) // 计算结果矩阵中第 i 行第 j 列的数 for (int k = 1; k <= m1.m; ++k) m3.a[i][j] += m1.a[i][k] * m2.a[k][j]; return m3; }矩阵快速幂求矩阵 $x$ 的 $y$ 次方。单位矩阵：主对角线为 $1$ 其余为 $0$ 的矩阵 $I = \left[\begin{matrix} 1 & 0 & 0 & \cdots & 0 \\ 0 & 1 & 0 & \cdots & 0 \\ 0 & 0 & 1 & \cdots & 0 \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & 0 & \cdots & 1 \end{matrix}\right]$。matrix qpow(const matrix x, int y) { // 计算 x 的 y 次方 matrix ans; ans.n = ans.m = x.n; for (int i = 1; i <= x.n; ++i) ans.a[i][i] = 1; while (y) { if (y & 1) ans = ans * x; x = x * x, y >>= 1; } return ans; }洛谷 P1962 - 斐波那契数列构造一个矩阵 $\left[\begin{matrix} f_i & f_{i - 1} \end{matrix}\right]$​ 和 $\left[\begin{matrix}1 & 1 \\ 1 & 0\end{matrix}\right]$，可得：$$ \left[\begin{matrix} f_1 & f_0 \end{matrix}\right] \times \left[\begin{matrix} 1 & 1 \\ 1 & 0 \end{matrix}\right] ^n = \left[\begin{matrix} f_{n + 1} & f_n \end{matrix}\right] $$使用矩阵快速幂求解，时间复杂度 $O(\log n)$。递推矩阵决定矩阵大小的因素：和前几项有关，例如洛谷 P1939 【模板】矩阵加速（数列）。$$ \left[\begin{matrix} a_i & a_{i - 1} & a_{i - 2} \end{matrix}\right] \times \left[\begin{matrix} \cdot & \cdot & \cdot \\ \cdot & \cdot & \cdot \\ \cdot & \cdot & \cdot \end{matrix}\right] = \left[\begin{matrix} a_{i + 1} & a_i & a_{i - 1} \end{matrix}\right] $$BZOJ #2396. 神奇的矩阵对于 $N \le 10^3$，直接矩阵乘…

2023 国庆集训 Day 5A 笔记
type: item
date: 2024-02-14T23:03:00+08:00
description: 更佳的阅读体验：2023 国庆集训 Day 5A 笔记，本文同步发表于 洛谷博客。以下内容为个人总结，如有错误或您有不同见解，欢迎指出。并查集并查集是一种用于管理元素所属集合的数据结构，实现为一个森林，其中每棵树表示一个集合，树中的节点表示对应集合中的元素。顾名思义，并查集支持两种操作：合并（Union）：合并两个元素所属集合（合并对应的树）。查询（Find）：查询某个元素所属集合（查询对应的树的根节点），这可以用于判断两个元素是否属于同一集合。并查集在经过修改后可以支持单个元素的删除、移动；使用动态开点线段树还可以实现可持久化并查集。并查集无法以较低复杂度实现集合的分离。初始时，每个元素都位于一个单独的集合，表示为一棵只有根节点的树。方便起见，我们将根节点的父亲设为自己。查询我们需要沿着树向上移动，直至找到根节点。size_t dsu::find(size_t x) { return pa[x] == x ? x : find(pa[x]); }路径压缩size_t dsu::find(size_t x) { return pa[x] == x ? x : find(pa[x]); }合并要合并两棵树，我们只需要将一棵树的根节点连到另一棵树的根节点。void dsu::unite(size_t x, size_t y) { pa[find(x)] = find(y); }启发式合并启发式合并 + 路径压缩：$O(m\alpha)$。不使用启发式合并、只使用路径压缩的最坏时间复杂度是 $O(m \log n)$ 。不使用启发式合并、只使用路径压缩，在平均情况下，时间复杂度依然是 $O(m\alpha(m, n))$。如果只使用启发式合并，而不使用路径压缩，时间复杂度为 $O(m \log n)$。由于路径压缩单次合并可能造成大量修改，有时路径压缩并不适合使用。例如，在可持久化并查集、线段树分治 + 并查集中，一般使用只启发式合并的并查集。带权并查集我们还可以在并查集的边上定义某种权值、以及这种权值在路径压缩时产生的运算，从而解决更多的问题。CEOI1999 - Parity Game带权并查集 / 种类并查集。转化为前缀和，每次询问相当于得知 $S[r]$ 和 $S[l - 1]$ 是否是同奇同偶。种类并查集：对于每个位置建立两个点 $i$，$i + n$ 分别代表， 为奇， 为偶。得知两个位置同奇同偶，那么 $i$ 和 $j$ 连，$i + n$ 和 $j + n$ 连，否则 $i$ 和 $j + n$ 连，$j$ 和 $i + n$ 连。一个集合内部的布尔变量相同，当 $i$ 和 $i + n$ 在同一集合时矛盾。带权并查集：相等连一条权值为 $0$ 的边，否则连一条权值为 $1$ 的边，要求两个点的路径异或和要么都为 $1$ （奇偶性不同），要么都为 $0$（奇偶性相同）。实现时维护到达集合代表点的距离即可。NOI Online #1 提高组 - 序列带权并查集与二分图。把每个位置看成一个点。首先对于 $2$ 操作连边。每次操作可以在一个连通块内部任选一个点加一，任选一个点减一。再对于 $1$ 操作连边。如果形成的图是二分图，则可以在保证左部点总和与右部点总和的差不变的情况下任意的加减。如果形成的图不是二分图，则可以在保证总和奇偶性不变的情况下任意的加减。洛谷 P2391 - 白雪皑皑倒序操作，需要支持将区间没有染色的地方染色。并查集：暴力染色，并删除染过的地方。令 $f[i]$ 从 $i$ 开始第一个没有染色的地方。染色后将 $f[i]$ 设置为 $f[i] + 1$，利用并查集维护。洛谷 P1640 - [SCOI2010] 连续攻击游戏建图分析。对于每种装备，将其两种属性连边。对于每个连通块来说，如果是一棵树，那么恰好会有一个属性选不到，那么让连通块的最大值选不到。否则至少是个基环树，所有值都可以选到。最终答案就是选不到的属性的最小值。CF571D - Campus启发式并查集。集合可以想到并查集，但是并查集会破坏合并结构，我们考虑使用启发式合并。如果得到某个位置最后一次清 0 是什么时刻，那么只考虑这个时刻之后的加法操作即可。我们用启发式合并维护信息，第二类集合维护上一次清零的时间，清零就在根结点处打 tag，需要记录连接的时间。然后可以离线下来，变成前缀和相减。加法操作可以记录自己连上来时候父亲的 tag，查询时拿父亲的 tag 减去记录的值即为正确的答案。最小生成树洛谷 P1396 - 营救最小生成树思想。将边从小到大排序，然后 Kruskal 最小生成树连边，这样当 $S$ 和 $T$ 第一次联通时，当前边的权值就是答案了。CF1245D - Shichikuji and Power Grid建图。新建一个…

2023 国庆集训 Day 5B 笔记
type: item
date: 2024-02-14T23:03:00+08:00
description: 更佳的阅读体验：2023 国庆集训 Day 5B 笔记，本文同步发表于 洛谷博客。以下内容为个人总结，如有错误或您有不同见解，欢迎指出。最短路洛谷 P4667 - [BalticOI 2011 Day1] Switch the Lamp On更优的复杂度：$O(NM)$。每个格子看作点。如果当前电线是左上到右下，建边权为 $0$ 的边； 如果当前电线是右上到左下，建边权为 $1$ 的边，表示需要改变。反之亦然。01 最短路，用队列维护。洛谷 P1462 - 通往奥格瑞玛的道路最大值最小？二分！保留二分值以下的边，跑最短路，检查是否能活着到达 $n$ 号点。洛谷 P1144 - 最短路计数洛谷 P1119 - 灾后重建Floyd 理解。洛谷 P4822 - [BJWC2012] 冻结分层图。分层图，建 $k + 1$ 层点跑最短路。另一视角：动态规划。洛谷 P9402 - [POI2020-2021R3] Droga do domu分层图。按照 $k$ 分层，设 $f[k][i]$ 表示换乘了 $k$ 次，到达第 $i$ 个点最早什么时间到。如何转移？因为公交车线路经过哪些点是有顺序的，我们枚举每条线路，从前向后走即可。洛谷 P2371 - [国家集训队] 墨墨的等式同余最短路。考虑 $b \mod a_1 = \sum_{i = 2}^n a_i x_i \mod a_1$。以 $a_1$ 为中心视角，如果 $b$ 能拼出来，那么 $b + a_1$，$b + 2a_1$，$b + ka_1$ 都能拼出来。也就是 $\mod a_1$ 同余的从一个开头开始，后面都能拼了。我们考虑用 DP / 最短路求出这个开头是多少。设 $f[i]$ 表示用 $a_2, \cdots, a_n$ 拼出最小 $\mod a_1 = i$ 的数是多少，转移，$f[i] = \min_{j = 2}^n f[i - a_j \mod a_1]$。AT_arc084_b - [ABC077D] Small Multiple如同余最短路。洛谷 P5304 - [GXOI/GZOI2019] 旅行者随机分组或二进制分组。分成两组 ，求出从 $A$ 某个点到 $B$ 某个点的最短路。新建超级原点和超级终点即可。差分约束洛谷 P3385 - 【模板】负环负环。洛谷 P5590 - 赛车游戏差分约束。洛谷 P3530 - [POI2012] FES-Festival$A$ 恰好比 $B$ 快 $1$ 秒，可以用两个不等式来约束，$A \le B - 1$，$A \ge B - 1$。我们发现所有关系都可以用不等式来约束，所以考虑差分约束。对于强连通分量，任意两个点都有约束，我们找到最短路最大的两个点 $+ 1$ 即为此连通分量的答案，不同联通分量的答案不影响。连通分量内部，由于此题两点距离是 $1$，所以如果存在一个最短路，那么最短路的所有值都可以取到。连通分量之间由于只有单向关系，可以令一个无限小，一个无限大，使得不同连通分量处于不同的值域。拓扑排序洛谷 P1983 - [NOIP2013 普及组] 车站分级洛谷 P5603 - 小 C 与桌游洛谷 P3243 - [HNOI2015] 菜肴制作洛谷 P6286 - [COCI2016-2017#1] Cezar比较两个字符串字典序大小，我们只需考虑第一个不一样的位置即可。假设第一个不一样的字符分别为 $s_1$，$s_2$，并且 $s_1$ 所在字符串字典序更小，那么一定有 $a < b$，连边跑拓扑序即可。洛谷 P3243 - [HNOI2015] 菜肴制作倒着求字典序最大的拓扑序即可。练习[P4079 [SDOI2016] 齿轮](https://www.luogu.com.cn/problem/P4079)[P4092 [HEOI2016/TJOI2016] 树](https://www.luogu.com.cn/problem/P4092)[P1525 [NOIP2010 提高组] 关押罪犯](https://www.luogu.com.cn/problem/P1525)[P3207 [HNOI2010] 物品调度](https://www.luogu.com.cn/problem/P3207)[P4568 [JLOI2011] 飞行路线](https://www.luogu.com.cn/problem/P4568)P3403 跳楼机[[ABC077D] Small Multiple](https://www.luogu.com.cn/problem/AT_arc084_b)[P3275 [SCOI2011] 糖果](https://www.luogu.com.cn/problem/P3275)[…

2023 国庆集训 Day 3B 笔记
type: item
date: 2024-02-14T23:02:00+08:00
description: 更佳的阅读体验：2023 国庆集训 Day 3B 笔记，本文同步发表于 洛谷博客。以下内容为个人总结，如有错误或您有不同见解，欢迎指出。树形 DP依照树的性质进行的 DP。把树分为许多子结构，通过子结构包含的信息来设计状态，通常是由子结点向父节点转移。以下所有关于树形 DP 的内容，规定 $x$ 为当前结点，$y$ 为其子节点。求树上两两距离和求 $dis[i][j]$。统计每条边的贡献：$size[x] \times (n - size[x])$。洛谷 P3047 - Nearby Cows G令 $f[x][i]$ 为 $x$ 子树内，和 $x$ 距离 $\le i$ 的点的点权和，$f[x][i] = c_x + \sum f[y][i - 1]$。求 $ans_x$ 时，令 $fa[x][i]$ 为 $x$ 的第 $i$ 级祖先，则 $ans_x = \sum f[fa[x][i]][k - i] - f[fa[x][i - 1]][k - i - 1]$。复杂度为 $O(nk)$。洛谷 P2014 - 选课把 $a$ 是 $b$ 的先修课程视为 $a$ 是 $b$ 的父亲，那么会形成一个森林。设 $f[x][i]$ 为 $x$ 子树中修读 $i$ 门课的最大学分数。依次枚举 $x$ 的每个儿子，设当前儿子为 $y$，利用老 $f[x]$ 与 $f[y]$ 合并出新 $f[x]$。老 $f[x]$ 意为不含 $y$ 子树的信息（也就是只考虑 $y$ 之前的所有儿子的子树）。那么 $f_新[x][i] = \max(f_老[x][j] + f[y][i - j])$。注意由于根节点 $x$ 必须选，那么要求 $j > 0$。复杂度为 $O(nm^2)$。经典的树形背包问题，利用 DFS 序可以优化为 $O(nm)$。求树的直径类似于上一题的合并，记录 $x$ 的当前深度。如果要对直径计数，额外记录数量。洛谷 P3174 - 毛毛虫答案为 $\max (\sum (deg[i] - 1) + 2)$，树形 DP 求最长链。或使用两遍 DFS 求直径。树上最大独立集 / 最小点覆盖最大独立集：选择尽可能多的点，但是父亲和儿子不能同时选择； 最小点覆盖：选择尽可能少的点，但是父亲和儿子至少选一个。令 $f[x][0 / 1]$ 表示在结点 $x$ 选 / 不选的情况下，$x$ 子树内的最大独立集点数； 令 $g[x][0 / 1]$ 表示在结点 $x$ 选 / 不选的情况下，$x$ 子树内的最小点覆盖点数。令根节点为 $r$，则答案为 $\max (f[r][0], f[r][1])$，$\min (g[r][0], g[r][1])$。洛谷 P2899 - Cell Phone Network G令 $f[x][0 / 1 / 2]$ 表示 $x$ 子树内的最小信号塔数，其中 $x$ 被儿子 / 自己 / 父亲覆盖。洛谷 P4084 - Barn Painting G令 $f[x][0 / 1 / 2]$ 表示 $x$ 染成三种颜色的子树内方案数。树上拓扑序计数给定一棵外向树（每条边的方向是从父亲到儿子），求其拓扑序个数。$n \le 10^5$。多重集合排列数公式： $\frac{(\sum a_i)!}{\prod a_i!}$，$a_i$ 为集合中第 $i$ 个元素的数量。令 $f[i]$ 表示 $i$ 的子树的拓扑序个数。$i$ 子树内首先第一位必须是 $i$，然后剩下的 $size[i] - 1$ 个位置需要分配给其儿子的子树。若 $i$ 有 $k$ 个儿子 $j_1, j_2, \cdots, j_k$，则分配位置的方案数为 $\binom{size[i] - 1}{size[j_1]} \binom{size[i] - 1 - size[j_1]}{size[j_2]} \cdots \binom{size[i] - 1 - size[j_1] - \cdots - size[j_{k - 1}]}{size[j_k]} = \frac{(size[i] - 1)!}{\prod size[j]!}$。然后再乘上 $f[j_1]f[j_2] \cdots f[j_k]$。树上问题在树上选出 $m$ 条边互不相交的链，使得他们的长度和最大。$n \le 10^5$，$m \le 10$。令 $f[x][i][0 / 1]$ 表示 $x$ 的子树选择 $i$ 条链，是 / 否有一条从儿子伸到 $x$ 的半链的最大长度和。转移时枚举儿子 $y$：$f[x][j][0] + f[y][i - j][0] \to f'[x][i][0]$，$f[x][j][1] + f[y][i - j][0] \to f'[x][i]…

2023 国庆集训 Day 4A 笔记
type: item
date: 2024-02-14T23:02:00+08:00
description: 更佳的阅读体验：2023 国庆集训 Day 4A 笔记，本文同步发表于 洛谷博客。以下内容为个人总结，如有错误或您有不同见解，欢迎指出。状压 DP洛谷 P4363 - 一双木棋只需要将当前局面下所放棋子的轮廓线压入状态即可，DP 初值为 $f[整个棋盘] = 0$。状压当前的轮廓线，依据这一步该谁下进行 min / max 搜索。洛谷 P5369 - 最大前缀和统计每个子集作为最大前缀和的次数。如果某个前缀和是最大前缀和，那么这个前缀的所有后缀和都 $> 0$，后面的所有前缀和都 $\le 0$。设 $f[S]$ 为将 $S$ 排列成所有后缀 $> 0$ 的方案数，$g[S]$ 为将 $S$ 排列成所有前缀 $\le 0$ 的方案数。答案即为 $\sum sum[S]f[S]g[U-S]$，$U$ 为全集。洛谷 P5492 - 随机算法求图上最大独立集。设 $f[S]$ 为 $S$ 内随机一个排列的正确方案数。枚举 $S$ 排列的第一个元素 $x$，加入 $x$ 会导致删除 $x$ 及与其相邻的点集 $c_x$。那么如果 $max⁡[S]=max⁡[S-c_x ]+1$，就令 $f[S]$ 加上 $f[S-c_x]$ 。int ctz[1 << N]; long long f[1 << N], g[1 << N]; long long c[N]; const long long p = 998244353; cin >> n >> m; for (int i = 0; i < m; i++) { cin >> x >> y; c[x] |= 1 << y; c[y] |= 1 << x; } for (int i = 0; i < n; i++) { ctz[1 << i] = i; } for (int S = 1; S < 1 << n; S++) { int x = ctz[S & -S]; g[S] = max(g[S - (1 << x)], g[S - (1 << x) - (c[x] & S)] + 1); } f[0] = 1; for (int S = 1; S < 1 << n; S++) { for (int x = 0; x < n; x++) { if (~S >> x & 1) <=> if (!(S >> x & 1)) continue; if (g[S - (1 << x) - (c[x] & S)] + 1 < g[S]) continue; f[S] = (f[S] + f[S - (1 << x) - (c[x] & S)]) % p; } } cout << f[(1 << n) - 1] /n! << endl; 图上拓扑序计数给定一张 DAG，求其合法拓扑序个数。$n \le 20$，$m \le \frac{n(n - 1)}{2}$。设 $f(S)$ 表示 $S$ 诱导子图的拓扑序个数。转移时，枚举 $S$ 中拓扑序最靠前的节点 $i$：$f(S) = \sum_{i \in S, ind_i = 0}f(S-\{i\})$ 。其中 $ind_i=0$ 表示 $i$ 在 $S$ 中没有入度（而非整个图中）。// topo count long long f[1 << N]; bool valid(int x, int s) { // s 没有连向 x 的边 } for (int s = 1; s < 1 << n; ++s) { for (int x = 0; x < n; ++x) { if (~s >> x & 1) continue; if (valid(x, s)) f[s] += f[s - (1 << x)]; } }边子集拓扑序计数给定一张有向图（不保证是 DAG）。设其边集为 $E$ 。对于 $T \subseteq E$ 定义 $f(T)$ 为保留 $T$ 时整张图的拓扑序数量，求 $∑_{T \subseteq E}f(T)$。$n \le 20$，$m \le n(n-1) $。设 $g(S)$ 表示 $S$ 诱导子图的答案，我们输出 $g(U)$。与其统计每个边集 $T$ 的拓扑序方案数，不如统计每种拓扑序能在多少种 $T$ 下合法。转移时仍然枚举 $S$ 中拓扑序最靠前的节点 $i$ 。要想让 $i$ 最靠前合法，就需要让 $i$ 在 $S$ 内的 $ind=0$。换句话说，不能保留从 $S-\{i\}$ 连向 $i$ 的边，而 $i$ 连向 $S-\{i\}$ 的边可以任意保留。所以 $g(S) = \sum_{i \in S} f(S-\{i\}) 2^{cnt_{i,S-\{i\}}}$，其中 $cnt_{i,S-{i}}$ 表示 $i$ 连向 …

2023 国庆集训 Day 4B 笔记
type: item
date: 2024-02-14T23:02:00+08:00
description: 更佳的阅读体验：2023 国庆集训 Day 4B 笔记，本文同步发表于 洛谷博客。以下内容为个人总结，如有错误或您有不同见解，欢迎指出。单调队列优化 DP洛谷 P1886 - 单调队列int a[N]; deque<int> q; // 存每个数的下标 for (int i = 1; i <= n; ++i) { while (!q.empty() && q.front() <= i - k) q.pop_front(); while (!q.empty() && a[q.back()] <= a[i]) q.pop_back(); q.push_back(i); cout << a[q.front()] << '\n'; }洛谷 P2216 - 理想的正方形洛谷 P2219 - 修筑绿化带求出每一块花园中，花坛应该放在哪里。如果花园的右下角为 $(x, y)$，那么花坛的右下角就应位于 $(x - a + c + 1, y - b + d + 1) \sim (x - 1, y - 1)$ 这个矩形内。求出这个矩形内最小的 $sum$。求最大全 0 正方形给定一个 0 / 1 矩阵，求出最大的全为 0 的子正方形，求不带 $\log$ 的做法。带 $\log$ 的做法：枚举每个点作为左上角，二分正方形边长。令 $f[i][j]$ 表示矩形 $(i, j)$ 位置往下延伸 $0$ 的个数，得到转移方程 $f[i][j] = \begin{cases} 0, a_{i, j} = 1 \\ f[i + 1][j] + 1, a_{i, j} = 0 \end{cases}$。枚举正方形的上边界 $u$，依次从 $1 \sim n$ 枚举正方形的右边界。维护一个左边界的指针，并用单调队列维护左右边界之中的 $f$ 值，需要时刻保证 $r - l + 1 \le \min ⁡f$ 。复杂度为 $O(n^2 )$。带修版本：洛谷 P4259 - 寻找车位洛谷 P2254 - 瑰丽华尔兹设 $f[t][i][j]$ 为 $t$ 时刻到达 $(i, j)$ 的最长路程。假如 $t$ 时刻钢琴是往上方滑动，那么 $f[t][i][j] = \max (f[t - 1][i + 1][j] + 1, f[t - 1][i][j])$。往其他方向同理。复杂度为 $O(nmT)$。由于时间可以被分为 $K$ 段，每段滑动方向相同，则可以修改状态，令 $f[k][i][j]$ 为第 $k$ 个时间段结束后到达 $(i, j)$ 的最长路程。$f[k][i][j] = \max {f[k - 1][i + s][j] + s), 0 \le s \le t_k}$。使用单调队列优化。复杂度 $O(nmK)$。// 不考虑障碍 且只考虑向上的转移 for (int k = 1; k <= K; ++k) { int t_k; for (int j = 1; j <= m; ++j) { deque<int> q; int g[]; for (int i = 1; i <= n; ++i) g[i] = f[k - 1][i][j] + i; for (int i = n; i; --i) { while (!q.empty() && q.front() > i + t_k) q.pop_front(); while (!q.empty() && g[q.back()] <= g[i]) q.pop_back() q.push_back(i); f[k][i][j] = g[q.front()] - i; } } }洛谷 P4381 - Island求若干个基环树的直径之和。对于一个基环树，找到它的环，求出环上每个节点 $i$ 环外延伸的最长距离 $d_i$。将长为 $m$ 的环破为长为 $2m$ 的链。如果从节点 $i$ 外面走到节点 $j$ 外面，则距离为 $j - i + d_i + d_j$，同时要求 $i < j < i + n$。使用单调队列优化求解。复杂度为 $O(n)$。单调队列优化多重背包一共有 $c_i$ 个 $i$ 号物品，有 $w_i$ 的价值和 $v_i$ 的体积。洛谷 P5665 - 划分贪心地使最后一段的和尽可能小。不严谨证明：如果最后一段 $[l, r]$ 的和没到达下界，那么可以不断地把 $a_l$ 分给前一段。由于 $s_i < s_{i+1}$，分给前一段的贡献是 $2a_l s_i$，分给后一段的贡献是 $2a_l s_{i+1}$，则分给前一段更优，同时分给前一段也有利于后面的分段。所以设 $f[r]$ 为 $\max⁡ {l-1: 最后一段分成 [l, r] 可行}$，应有 $sum_r - sum_{l-1}…

2023 国庆集训 Day 2B 笔记
type: item
date: 2024-02-14T23:01:00+08:00
description: 更佳的阅读体验：2023 国庆集训 Day 2B 笔记，本文同步发表于 洛谷博客。以下内容为个人总结，如有错误或您有不同见解，欢迎指出。搜索NOIP2009 提高组 - 靶形数独可行性剪枝：每次最先搜索可能性最少的点。最优化剪枝：剩下的数最优情况下也不超过全局最优解的剪枝。Example 2有 $q$ 次询问，每次询问一个数 $x$，询问 $x$ 每次除以一个约数直到最后变为 $1$ 有多少种方式，比如 $x = 6$，有$(6 \to 1)$、$(6 \to 3 \to 1)$、$(6 \to 2 \to 1)$ 三种。$x \le 10^{15}$，$q \le 10^4$。对 $x$ 做质因数分解可以使用 $\texttt{Pollard-Rho}$ 算法，期望复杂度为 $O(n^{0.25})$。假设得到了 $x = a_1^{p_1}a_2^{p_2}a_3^{p_3}\cdots a_k^{p_k}$，因此只有 $(p_1, p_2, p_3, \cdots, p_k)$ 的无序元组有意义。这样本质不同的元组数量的一个粗略上限是考虑 $2^{50} \sim 10^{15}$，而 $50$ 的拆分数只有 $2 \times 10^5$ 级别，事实上会少很多。直接暴搜出所有可能的元组组合并排列组合一下计算答案即可。SDOI2015 - 排序首先操作的顺序是无关紧要的，所以我们只需要关心每个操作做没做。我们从小到大 DFS，对于第 $i$ 次操作我们将序列分成 $2^{n-i}$ 段，每段长度 $2^i$。我们找到序列中不是连续递增的段，如果这样的段超过 $2$ 个则不行。如果没有这样的段，就不需要执行这个操作。如果有一个这样的段，判断将这个段的前半部分和后半部分交换后是否连续递增，如果是就交换然后继续 DFS。如果有两个这样的段，判断四种交换情况然后 DFS。二分最大平均子段和给定一个长度为 $n$ 的序列 $a_1,a_2,\cdots,a_n$ 和 $k$，求一个长度大于 $k$ 的区间 $[l, r]$ 使得 $\frac{a_l+\cdots+a_r}{r - l + 1}$ 最大。$n \le 10^5$，输出小数，精度 $10^{-6}$。考虑二分答案 $p$，然后让 $b_i = a_i - p$，只需要看 $b_i$ 构成的序列是否有大于 $0$ 的子段，就可以知道 $a_i$ 序列有没有平均值大于 $p$ 的子段。看 $b_i$ 构成的序列是否有大于 $0$ 的子段可以直接找 $b$ 的最大子段和。LOJ 2776 - 蠕虫之忧Subtask 1二分、三分次数都不够，需要使用黄金分割比分。因为黄金分割比位置在下一层二分处还是该位置。Subtask 2复制一维二分到二维，每次询问中线上最大值点，看看他左右两侧哪一侧增高就去哪边，不过注意可以每次二分较短的一维。同时如果之前查询到的全局最大值比当前线上最大值大，则向全局最大值位置继续二分。Subtask 3注意到 $Q$ 很大，可以使用乱搞随机做法。先用 $\frac{q}{2}$ 次随机询问，问一个最大的点，然后用这个点爬山。期望到山顶的路径长度其实很短。Example 3你在玩一个游戏，游戏中的一个关卡是这样的：有一张 $n$ 个节点和 $m$ 条边的有向图，每条边有一个长度，你的角色一开始在 $1$ 号点移动速度为 $1$ 单位长度每秒，每次到达一个点会带权选择一个随机的出边走出去，在边上移动的时候会消耗对应长度的时间。你的目的是在 $L$ 的时间内到达 $n$ 号点，你可以选择在任意时间重开这一关。求在现实世界过关所需要的最小期望时间，输出实数。$n \le 100$，$m \le 200$，其他所有数在 $10^9$ 以内。二分答案 $T$，在游戏中加入一个虚拟按钮，这个按钮的功能是立刻以T的时间通关。用动态规划算出人物在每一个点的期望通关时间和为了达到这个通关时间的决策（继续走、重开还是按按钮），如果最后我们发现在 $1$ 号点按按钮是最优的则实际通关最小期望时间 $\ge T$,否则 $< T$。分治Example 1给定一个排列，随机做 $k$ 次交换两个数，求最后期望逆序对数。$n \le 5 \times 10^5$，$k \le 10^9$。$k=0$ 的时候就是朴素的逆序对问题，需要分治。考虑直接在 $k \ne 0$ 的时候也硬上分治。对于 $(l, r)$ 节点，我们只统计 $k$ 轮过后期望 $(l, mid)$ 与 $(mid + 1, r)$ 之间的贡献。于是我们的第二个状态变成了 $f[k][0 / 1 / 2][0 / 1 / 2]$，表示第一个数在区间左 / 区间右 / 区间外，第二个在区间左 / 区间右 / 区间…

2023 国庆集训 Day 3A 笔记
type: item
date: 2024-02-14T23:01:00+08:00
description: 更佳的阅读体验：2023 国庆集训 Day 3A 笔记，本文同步发表于 洛谷博客。以下内容为个人总结，如有错误或您有不同见解，欢迎指出。线段树多用于辅助数据结构。也有应用线段树思维的分治。矩形叠加问题给定一个 $n \times n$ 的二维平面上的 $m$ 个矩形，对于 $i=1,2,\cdots n$，求所有满足 $x=i$ 的整点中最多被矩形覆盖的整点被多少个矩形覆盖。$n, m \le 10^5$。把 $x$ 维看作是时间，$y$ 维看成一个一维的序列 $a_1, a_2, \cdots a_n$，问题变成：对于一个 $x \in [x_l, x_r]$，$y \in [y_l, y_r]$ 的矩形，相当于是在 $x_l$ 时间对区间 $[y_l, y_r]$ 的 $a$ 全体加 $1$，在 $x_r + 1$ 时间对区间 $[y_l, y_r]$ 的a全体减 $1$。然后对于时间 $1 \cdots n$，询问一下全局所有 $a$ 的最大值。LOJ Round #6 - 花火第二种操作在什么时候执行效果都是一样的，所以考虑一开始就交换两个数。对于一个排列，交换相邻的两个数从而排序所需要的数是确定的——逆序对数。所以我们的问题变成交换两个数使得逆序对个数最少。如果我们交换第 $l$ 个数和第 $r$ 个数，只需要考虑 $[l, r]$ 之内的逆序对改变，因为其他逆序对都没变。不失一般性假设 $h_l > h_r$（反之则没必要交换），减少的逆序对是 $[l, r]$ 中值在 $[h_r + 1, h_l - 1]$ 的数的个数 $\times 2$。也就是说对于每个 $h_i$，在二维平面中画一个点 $(i, h_i)$，我们想找两个点组成矩形的左上角和右下角，能框住最多多少个点。所以现在题面变成，给定平面上 $n$ 个点 $(x_1, y_1) \cdots (x_n, y_n)$，求两个点分别作为左上角和右下角最多能框住多少个点。那么如果 $x_i > x_j, y_i > y_j$，则 $(x_j, y_j)$ 一定不会作为左上角。所以我们可以找出一条从左下到右上的、$x$ 坐标单调递增、$y$ 坐标单调递增的可以作为左上角的点的序列 $s_1, s_2, \cdots, s_k$。同理可以得到一条从左下到右上的、$x$ 坐标单调递增、$y$ 坐标单调递增可以作为右下角的点的序列 $p_1, p_2, \cdots, p_k$。可以发现每一个点 $(x_i, y_i)$ 会对左上角位于一个区间 $s_l, \cdots, s_r$ 和右下角位于一个区间 $p_x, \cdots, p_y$ 的所有矩形有 $1$ 的贡献，直接用之前的矩形叠加问题即可解决。线段树分治考虑一类问题，给你一堆加入、删除操作，维护某个东西。如果加入、删除的数据结构非常困难，但是加入、撤销上一次加入很简单，且问题离线，就可以用 $\log$ 的时间代价使用一种简便的方法。具体方法是考虑某一元素的加入时间 $st$，和删除时间 $ed$。对时间建立一个线段树，把每一个元素的时间段 $[st, ed]$ 放在线段树上变成 $\log$ 个区间，然后在线段树上从上到下直接使用加入、撤销数据结构维护答案。动态连通块个数维护一张无向图 $q$ 次操作，每次加入一条边或删一条边，维护连通块个数。$q \le 10^5$。对每一条边存在的时间建立线段树。考虑线段树分治，对每一条边计算加入删除时间，然后在线段树上从根往下只需要支持加入一个边，撤销上一条边。此时只需要使用按秩合并即可以 $O(n \log^2 n)$ 的复杂度解决。HASHExample 1给定串 $S$ 和 $q$ 次询问，每次询问两个位置 $l_1, l_2$ 的最长公共前缀。$\lvert S \rvert, q \le 3 \times 10^5$。对于字符串，在 $i$ 的 HASH $h_i = (\sum_{j = 0} ^ i a^{i - j} s_j) \mod p$，则对于一个区间 $[l, r]$ 有 $\text{hash}([l, r]) = (h_r - h_{l - 1}) a^{r - l} \mod p$。CF1017E考虑求出凸包后，用一些旋转、平移无关的量表示。一种可行的方法是，考虑凸包上相邻的三个点，把这个三角形的三边长度作为参数构建一个序列，然后只需要看两个序列是否平移同构，直接 HASH 即可（也可以KMP）。这题提示我们，使用 HASH 的一个要点是找到一种表示。CCPC2023 D（矩阵 HASH）给定一个有 $m$ 种括号的长度为 $n$ 的序列，每种括号分为左右两种，有 $q$ 次操作，每次操作有两种情况：修改一个位置的括号类型（哪一种，…

2023 国庆集训 Day 2A 笔记
type: item
date: 2024-02-14T23:00:00+08:00
description: 更佳的阅读体验：2023 国庆集训 Day 2A 笔记，本文同步发表于 洛谷博客。以下内容为个人总结，如有错误或您有不同见解，欢迎指出。搜索LOJ 10020 - 小木棍满足 $nm = \sum a_i = N$， 则需要满足 $N \mod n = 0$。较劣方案：使用 DFS 一根一根构造木棍。代码实现注意细节。#include <bits/stdc++.h> using namespace std; const int N = 70; int n, a[N], L; bool vis[N], flag; void dfs(int s) { // s - 当前木棍长度 bool ok = 0; for (int i = 1; i <= n; ++i) if (!vis[i]) ok = false; if (ok) return flag = true, void(); for (int i = 1; i <= n; ++i) if (!vis[i] && s + a[i] <= L) { vis[i] = 1; s += a[i]; if (s == L) s = 0; dfs(s); if (!s) s = L; s -= a[i]; vis[i] = false; if (flag) return; } } int main() { // read. sort(a + 1, a + n + 1); reverse(a + 1, a + n + 1); int sum = 0; for (int i = 1; i <= n; ++i) sum += a[i]; for (int i = a[1]; i <= sum; ++i) if (!(sum % i)) { L = i; flag = false; dfs(0); if (flag) return cout << i << '\n', 0; } return 0; }搜索优化思路：减少状态数、减少状态处理时间（较难）。分治逆序对使用归并排序。思考题：对有序数列随机交换 $k$ 次，求逆序对的期望个数。归并排序。贪心局部最优解 = 全局最优解。反例：背包问题，局部最优解 $\ne$ 全局最优解。Example有 $n$ 个怪物，每个怪物有攻击力 $a_i$ 和 $b_i$，每一轮可以对一个怪物造成 $1$ 的伤害，每个怪物会对你造成 $a_i$ 的伤害，求你受到伤害最小的攻击顺序，$n \le 10^5$。优先打 $\frac{a_i}{b_i}$ （攻血比）较高的。如何证明？考虑反证法。如果先打攻血比较低的，受到的伤害一定不小于先打攻血比高的。如果 $\frac{a_i}{b_i} < \frac{a_{i + 1}}{b_{i + 1}}$，则原受到 $b_i(a_i + a_{i + 1}) + b_{i + 1}a_{i + 1}$ 的伤害，交换后受到 $b_{i + 1}(a_i + a_{i + 1}) + b_i a_i$，整理后得到 $a_{i + 1} b_i$ 和 $a_i b_{i + 1}$，则有 $a_{i + 1} b_i > a_i b_{i + 1}$。快速幂任意满足结合律的都可以使用快速幂。递归实现：ll qpow(ll a, ll b) { if (!b) return 1; ll res = qpow(a, b >> 1); res = res * res % p; if (b & 1) res = res * a % p return res; }循环实现：ll qpow(ll a, ll b) { ll res = 1; while (b) { if (b & 1) res = res * a % p; a = a * a % p, b >>= 1; } return res; }龟速乘 / 快速乘ll mul(ll a, ll b) { if (!b) return 1; ll res = 0; whlie (b) { if (b & 1) res = (res + a) % p; a = (a + a) % p, b >>= 1; } return res; }矩阵快速幂有结合律，但无交换律。可用于求较大的递推。Example. 求斐波那契数列在模 $p$ 意义下的第 $n$ 项。ST表用于处理 RMQ 问题。Example给定一个序列，询问区间最小值，$n \le 10^5$，$q \le 10^7$。要做到 $O(1)$ 询问，则预处理出 $f_{i,j}=\min_{k\in[i,i+2^i)} a_k$。LCATarjan.记录每个点的深度。先把较低点抬高，使得两点位于同一深度。