kketchup的小窝

网络流入门写在前面本文是笔者第一次学习网络流写的 $\text{blog}$，可能比较简陋，但还是尽可能让所有人看懂 qwq。 本篇主要介绍网络流算法，具体题目的建模可以看这一篇。 网络流引入 网络流，简单来说就是在一个很多水管的地方，水流从起点流向终点，在水管有多种限制的情况下最大化总流量。 网络一个有向图 $G=(V,E)$，满足以下两个条件则为网络。 $1.$ $\forall e=(u,v)\in E$（称为弧），都有一个称为容量的值 $w=c(u,v)$，也可记作弧 $(u,v,w)$。$2.$ 此图内有且仅有一个起点（源点）$S$ 和终点（汇点）$T$。 流我们记 $f(u,v)$ 表示 $u$ 到 $v$ 的流量。对于网络中的一个路径，满足以下两个条件则为流。 $1.$ 容量限制：对于路径上的每条边，流经该边的流量不能超过其容量，即 $f(u,v)\le c(u,v)$。感性理解为水管粗细有限，只能接受一定量的水流。$2.$ 流量守恒：除了源点 $S$ 与汇点 $T$，路径上的每个点流入流量等于流出流量，即 $\sum_vf(u,v) ...

字符串 DP 【题意】 给定一个长度为 $n\le 1000$ 的字符串，再给定一个长度相等的目标串和非负整数 $k\le 10^5$，请问是否可以使用正好 $k$ 次操作，将原串变成目标串。 每一次操作选择一个位置 $p\in[1,n)$，然后将字符串变成 $[p+1,n]+[1,p]$。其中 $+$ 表示连接。 求操作方案数，取模。两个方案不同当且仅当至少有一步 $p$ 的选择不同。 【解析】 猜一个非常重要的结论：如果一次操作不行的话，那一定不行。 感性理解一下，字符之间的相对位置大体不变，一次不行的话多次也不行。 推广一下，也就是说做任意多次操作以后只需要做 $1$ 次操作就可以变成想要的样子。 所以我们可以先暴力求出一次操作能满足条件的方案数，记为 $\text{cnt}$。 则考虑 DP，设 $f_i$ 表示第 $i$ 步变成目标串的方案数，$g_i$ 表示第 $i$ 步没变成目标串的方案数。 推出转移方程 $f_i=cnt\times g_{i-1}+(cnt-1)\times f_{i-1}$。表示有 $\text{cnt}$ 种方式从上一个的任意非目标串 ...

0-1 Trie大家都知道，$\text{trie}$ 很有用，具体可以见我的 字符串笔记，而 $\text{0-1 trie}$ 就是字符集只有 ${0,1}$ 的 $\text{trie}$，可以维护各种带修的异或问题。 那默认大家都会 $\text{trie}$ 了，我们直接讲点 $\text{0-1 trie}$ 的应用。 应用 1 维护异或极值P4551 最长异或路径 对于此题，我们先预处理出根节点到每个点的异或值，记作 $a_u$，此时一条路径 $(u,v)$ 就转化为 $(root,u)\oplus(root,v)$，异或值就是 $a_u\oplus a_v$。 正确性在于，异或两个相同数时会变成 $0$，所以从 $lca(u,v)$ 往上的重复部分都被抵消了。 此时我们把问题转化为在一个数列中找异或值最大的两个数。 所以我们以每个 $a_i$ 的二进制从高位到低位建一棵 $\text{0-1 trie}$。对于每个 $a_i$，尝试每一位都在树上寻找与这一位不同的另一个方向，这样异或以后该位为 $1$。 如果有就统计上答案，否则先跟着走。因为二进制高位更大则一定更大，所 ...

校内模拟-2024-4-28前言第一次 AK 校内比赛 qwq。 D 的 $\text{trick}$ 见过类似的才侥幸做出来。 A简单题但是毒瘤题。 搜索 【题意】 给定矩阵，找值相等的八连通块，满足其八联通方向没有值更大/更小。 分别求这两种连通块的个数。要做到 $O(n^2)$。 【解析】 搜索即可。开两个标记，表示是山峰/山谷。 记得特判全相等的情况。 但不知道为什么，$\text{dfs}$ 在 LOJ 上会 MLE。 所以改成了 $\text{bfs}$ 卡空间，把所有能开在外面的开外面，卡了 $10$ 发才过。 幸亏没有罚时。 【代码】 #include<bits/stdc++.h>using namespace std;#define ll long long#define endl '\n'#define F(i,x,y) for(int i=(x);i<=(y);++i)#define Fo(i,x,y) for(int i=(x);i>=(y);--i)const int N=1001;int n ...

字符串入门DFADFA，即确定有限状态自动机。用于判断输入的字符串是否符合要求。所有的字符串算法都是构造 DFA，结构有点像图灵机。 先给点定义： 状态集 $Q$（有限）：若将自动机看成图，那么状态是顶点。 字符集 $\sum$：满足自动机要求的字符集。 可接受状态集 $F\subseteq Q$：是满足要求的状态。 初始状态 $q_0\in Q$：是初始空状态。 转移函数 $\delta$：$\delta\times \sum\rightarrow Q$ 是转移函数。 整个算法流程就是，从初始状态 $q_0$ 出发，每次输入字符 $c$，并通过转移函数 $\delta$ 转移。最后若状态为 $F$，那么字符串符合要求。 例题1：构造判断二进制数奇偶的 DFA因为二进制数的奇偶性只与最后一位数是 $0$ 还是 $1$ 有关。所以这里构造的 DFA 用 $q$ 表示当前二进制数的奇偶性，每次输入的字符判断，如果是与当前 $q$ 相同就不变，否则转移到另一个。 字符串哈希简单来说，就是通过一个函数（即 $\text{Hash}$）把字符串映射到整数，用来快速判断字符串相等。 其实我 ...

CF161D点分/长链剖分/dsu 随便过。 但注意到数据范围不强，考虑 $O(nk)$ 的复杂度，可以树形DP。设 $f_{u,i}$ 表示以 $u$ 为根，子树中离 $u$ 路径长度为 $i$ 的点数。 统计答案时考虑每个的贡献是 $f_{u,j}\times f_{v,k-i-j}$（$0\le j<k$）。然后再转移 $f_{u,j+1}=\sum_{v\in u}f_{v,j}$。 这样的正确性在于，每次统计答案时都是新的和当前的统计，再把新的更新，不重不漏，有点像枚举两点时 $j$ 从 $i+1$ 开始枚举。第一遍没过就是这里没考虑好，shaber 了。 void dfs(int u,int fa){ f[u][0]=1; for(int v:e[u]){ if(v==fa) continue; dfs(v,u); for(int i=0;i<k;++i) ans+=(f[u][i]*f[v][k-i-1]); for(int i=0;i< ...

校内模拟-2024-3-28A原题链接 【题意】 求树上距离（无边权）为 $k$ 的无序点对数。 $1\le n\le 5\times 10^4,1\le k\le 500$。 【解析】 这题我做过（惊恐）于是场上秒了。 可以左转我的题解。 我的做法是 DP，复杂度 $O(nk)$。 B原题链接 【题意】 给定一棵无边权的树，树上有 $m$ 个关键点，你要选择其中一个出发，到达其余所有关键点，路径（显然）可重复。费用定义为经过边的总数，求最小费用和对应的出发点（多个费用相同的点取最小）。 【解析】 容易发现，答案一定是一些走两遍的路径和一些走一遍的路径组成的，所以为了最小化答案，走一遍的路径就是直径。答案就是 （要经过的点数 $-1$）$\times 2$ $-$ 直径。 猜到这个结论就好想了，考虑如果要经过一个点，当且仅当其子树内有关键点，所以从直径开始 dfs 即可。 别忘了特判只有一个点的情况。 #include<bits/stdc++.h>using namespace std;#define ll long long#define db double#define ...

斜率优化 斜率优化，一般是在转移方程中当前为 $i$，枚举决策点 $j$，然后化简式子出现同时与 $i$ 和 $j$ 有关的项（如果没有可以单调队列）。这样的话有点像一次函数，形如 $y=kx+b$，那么这里的 $kx$ 就是与$i$ 和 $j$ 有关的项（具体题目具体分析）。问题变成查询最有决策点。 如果式子中的 $x$ 与 $y$ 都有单调性，可以使用单调队列线性维护。否则有两种做法：维护凸壳并二分或李超树（也可以平衡树或 cdq 分治，但我不会，就不弄巧成拙了）。这些做法是带一个 log 的。 经典套路： $1.$ 写出朴素转移方程。 $2.$ 化简并设出 $x,y,k,b$，根据所求决定维护上凸还是下凸（最大值还是最小值）。 $3.$ 看单调性决定维护方式。 单调队列维护例题1 P3195 [HNOI2008] 玩具装箱【题意】 给定一个序列，要求将其划分成若干段，一段划分为 $[i,j]$ 的费用为 $(j-i+\sum_{k=i}^jC_k-L)^2$（这里的 $C_k$ 为给定数组，$L$ 为给定常量）。最小化划分序列的费用和。 【解析】 朴素的 ...

CF631E Product Sum 斜率优化DP 传送门 闲话模拟赛 D 题。感觉是个斜优的比较板的题。 开始写了一发错误的贪心，Wa on 9，后来改成 DP 才过。 场上过了 $5$ 个，拜谢 AK 爷 @Helloworld_wuyuze @RailgunZzzz @秦屎皇。 题意给定一个长度为 $n$ 的序列，序列的价值定义为 $\sum_{i=1}^na_i\times i$。允许至多一次操作，把一个元素移动到任意一个序列中的位置，求最大的序列价值。 $2\le n\le 2\times 10^5，|a_i|\le 10^6$。 解析先考虑 naive 做法。对于每个 $a_i$，枚举其移动到的位置位置 $j$，每次计算贡献的变化，时间复杂度 $O(n^2)$。 具体地，分两种情况讨论。对于向前移动，即 $j<i$，从 $i$ 移到 $j$ 后面，会使位于 $[j+1,i-1]$ 的元素贡献多一次，然后 $i$ 的贡献转化到了 $j+1$。 也就是 $s_{i-1}-s_{j}-(i-(j+1))\times a_i$。这里的 $s_i$ 表示 $a_i$ ...

闲话DP 太菜了，刷 AT 经典 DP，前面的比较简单，从 J 开始吧 qwq AT_dp_J 期望 DP 传送门 注意到 $a_i\leq3$，所以状态应该跟 $a_i$ 有关。考虑设 $f_{a,b,c,d}$ 表示有 $a$ 种剩余 $3$ 个的寿司，$b$ 种剩余 $2$ 个的寿司…… $$f_{a,b,c,d}=1+\frac{a}{n}f_{a-1,b+1,c,d}+\frac{b}{n}f_{a,b-1,c+1,d}+\frac{c}{n}f_{a,b,c-1,d+1}+\frac{d}{n}f_{a,b,c,d}$$整理并可得$$f_{a,b,c,d}=\frac{n}{n-d}+\frac{a}{n-d}f_{a-1,b+1,c,d}+\frac{b}{n-d}f_{a,b-1,c+1,d}+\frac{c}{n-d}f_{a,b,c-1,d+1}$$ 这样是四维的，发现 $d=n-(a+b+c)$，于是变成 $3$ 维，可以 $O(n^3)$ 的 DP，得到最终方程 $$f_{a,b,c}=\frac{n}{a+b+c}+ ...