DP 复习
Link：Vjudge Workbook HDU-1159 Common Subsequence 最长公共子序列板子题。 dp[i][j]={dp[i−1][j−1]+1(si=tj)max(dp[i−1][j],dp[i][j−1])otherwisedp[i][j] = \begin{cases} dp[i - 1][j - 1] + 1 & (s_{i} = t_{j}) \\ \max(dp[i - 1][j], dp[i][j - 1]) \\ otherwise \end{cases} dp[i][j]=⎩⎨⎧dp[i−1][j−1]+1max(dp[i−1][j],dp[i][j−1])otherwise(si=tj) HDU-5904 LCIS 由于是连续值，可以先预处理出数组 a,ba, ba,b 的满足条件的最长公共子序列。 fa[a[i]]=fa[a[i]−1]+1fb[b[i]]=fb[b[i]−1]+1\begin{aligned} fa[a[i]] &= fa[a[i] - 1] + 1 \\ fb[b[i]] &= ...
OI集训 Day30
Content：模拟赛 Date：2025.8.15 Problem-A 图书配对 题目描述 给定 nnn 本图书，定义 merge(ai,aj)merge(a_{i},a_{j})merge(ai,aj) 表示 aia_iai, aja_{j}aj 直接拼接得到的结果，求满足 merge(ai,aj)∣9merge(a_{i},a_{j}) \mid 9merge(ai,aj)∣9 的个数（一个数只能取一次）。 解题思路 我们可以运用小学奥数的知识，如果一个数能被 999 整除，当且仅当这个数的各个数位之和能被 999 整除，知道这个之后就是一个很经典的问题了。 提交记录：Link Problem-B 菜品搭配 题目描述 给定数组 aaa，求 ∑i=0n−2∑j=i+1n−1∑k=j+1n(ai⊕aj)×(aj⊕ak)\displaystyle \sum_{i=0}^{n-2} \sum_{j=i+1}^{n-1} \sum_{k=j+1}^{n} (a_{i} \oplus a_{j}) \times (a_{j} \oplus a_{k})i=0∑n−2j=...
OI集训 Day29
Content：杂题 Date：2025.8.14 CodeForces-1870E Another MEX Problem 题目大意 给你一个数组 aaa，你可以选择任意互不相交的子数组，先计算每一个子数组的 MEX 值，然后将这些 MEX 值的异或和作为这个方案的价值，求你可以获得的最大价值。 解题思路 首先我们肯定可以暴力 DP，定义 dpi,jdp_{i,j}dpi,j 表示前 iii 个数能否凑出价值为 jjj 的方案，转移显然是 O(n3)O(n^3)O(n3) 的。 考虑如何优化。由于 MEX 的性质，可以发现从 iii 往后的一段区间内 MEX 值是单调不降的，所以其中一定有大量相等的段。这些段本质是一样的，所以我们只需要考虑那些前后不同的位置即可，这些符合条件的转移区间至多有 2n2n2n 个，所以我们就得到了复杂度为 O(n2)O(n^2)O(n2) 得做法。 提交记录：Link Luogu-P12426 BOI acroym 题目大意 已知一个由 B, O, I 组成得字符串每个区间得众数得出现次数，且 B 为全局众数，求原串种 B 出现的位置。 解题思...
OI集训 Day28
Content：网络流进阶 Date：2025.8.13 昨天太累了，没写，就今天补上吧 课堂内容 上下界网络流 OI Wiki：Link 很可惜，没学懂，但是大概意思应该是用差分的思想将原来的上下界网络流转换为网络最大流。没学过真的听不懂啊…… 题目 模拟题-6.2 异或 题目大意 给你一个长度为 nnn 的数组 aaa，问你满足 (ai⊕aj)<(aj⊕ak)(a_{i} \oplus a_{j}) < (a_{j} \oplus a_{k})(ai⊕aj)<(aj⊕ak) 的三元组 (i,j,k)(i,j,k)(i,j,k) 有多少个。 解题思路 由于异或 相同为 0，不同为 1 的运算规则，可以发现要满足上述的不等式 (ai⊕aj)<(aj⊕ak)(a_{i} \oplus a_{j}) < (a_{j} \oplus a_{k})(ai⊕aj)<(aj⊕ak) 只与这三个数第一个在二进制下不同的位置 ppp 有关。具体来说： 若 ak,p=1a_{k,p} = 1ak,p=1，则 ai,p=aj,p=0a_{i,...
OI集训 Day27
昨天忘记传了喵~ Content：网络流 Date：2025.8.12 课堂内容 二分图匹配 Hall 定理 假设 G=(X,Y,E)G = (X,Y,E)G=(X,Y,E) 是一个二分图，且 ∣X∣≤∣Y∣|X| \le |Y|∣X∣≤∣Y∣。对于 W⊆XW \subseteq XW⊆X，记 NG(W)N_{G}(W)NG(W) 表示在图 GGG 中所有与集合 WWW 中的点相邻的点的集合。那么 XXX 的完美匹配存在，当且仅当 ∣W∣≤∣NG(W)∣|W| \le |N_G(W)|∣W∣≤∣NG(W)∣ 对于所有 W⊆XW \subseteq XW⊆X 存在。 匈牙利算法 不断搜索增广路，每次考虑一条增广路，看看把一个匹配拆了能否增加一个新的匹配。 模板代码：Link 网络最大流算法 Dinic Dinic 是求解网络最大流的其中一个算法，也是最常用的算法。其核心思想为：每次用 BFS 寻找增广路，然后用 DFS 统计增广路上的最大流量。但是这样会有一些问题，如果给定的网络是如下情况的话： 如果直接按照上面说的方法走，第一次增广路可能是 1→2→3→41 \to ...
OI集训 Day26
Content：图论 Date：2025.8.11 课堂内容 差分约束 Problem 给定一个包含 nnn 个不等式的不等式组，要求求出这个不等式组的任意一组解，或者判断不等式组无解。 Solution 对于给定的这个问题，整理一下，发现要求解： {x1−x2>c1x2−x3>c2x3−x4>c3…xn−x1>cn⇒{x1>x2+c1x2>x3+c2x3>x4+c3…xn>x1+cn\begin{cases} x_1 - x_{2} > c_{1} \\ x_{2} - x_{3} > c_{2} \\ x_{3} - x_{4} > c_{3} \\ \dots \\ x_{n} - x_{1} > c_{n} \end{cases} \Rightarrow \begin{cases} x_1 > x_{2} + c_{1} \\ x_{2} > x_{3} + c_{2} \\ x_{3} > x_{4} + c_{3} \\ \dots \\ x_{n} > x_{1} + ...
OI集训 Day25
Content：图论基础 Date：2025.8.10 课堂内容 图论基础知识 图的定义：由点集 VVV 和边集 EEE 组成，记作图 G(V,E)G (V, E)G(V,E)。 阶：图的点数，记作 ∣G∣|G|∣G∣。 相邻：称图中的两个点 相邻，当且仅当 (i,v)∈E(i,v) \in E(i,v)∈E。 连通：无向图中若存在 v0=u,vk=vv_0 = u, v_k = vv0=u,vk=v 的路径则称 u,vu, vu,v 连通。 弱连通：若有向图变为无向图后 u,vu, vu,v 连通，则称 u,vu, vu,v 弱连通。 连通图：无向图中任意两点连通的图称作连通图。 弱连通图：有向图中任意两点弱连通的图称作弱连通图。 简单图：不存在重边和自环的图。 稀疏图/稠密图：∣E∣≪∣V∣2|E| \ll |V|^2∣E∣≪∣V∣2 的图称作稀疏图，∣E∣|E|∣E∣ 接近 ∣V∣2|V|^2∣V∣2 的图称作稠密图。 拓扑排序 Problem 给定一个有向无环图（DAG），要求求出一个序列 ppp，其中 uuu 在排列 ppp 中的位置记作 quq_uqu，则...
OI集训 Day24
Content：模拟赛 Date：2025.8.9 Problem-A IEEE 754 题目描述 题目背景告诉你浮点数表示法(IEEE 754 标准)，要求你求 5n5^n5n，其中 n<1024n < 1024n<1024。 思路 赛场上是直接写的高精度，但是赛后看过题解发现有更简单的做法。 首先用 Python 计算发现，510235^102351023 大约有 800 位，而 double 类型的存储精度有 308 位，所以可以用 double 类型计算，但是要计算的是 5(−n)5^(-n)5(−n)，因为是浮点数。 提交记录：Link Problem-B 探险 题目描述 给定一个数组 aaa，有两个人轮流操作，每次交换一对 i,ji,ji,j，谁进行操作后数组 aaa 有序（从小到大），则这个人获胜。同时有 qqq 个修改操作，分为两类： 111 iii jjj：将 aia_iai 与 aja_jaj 交换。 222 kkk：将 aaa 循环位移 kkk 次。 你需要对于初始状态和每一个修改后的状态，判断是先手获胜还是后手获胜。 思路 赛场...