This is xingyu.

预计网站会更新的 更改一切相关域名 预计要写的 Markdown语法汇总 更新内容 注：该板块从2023/2/1开始统计。 2023/4/16：四月天 2023/2/12：步入初三下的感想 2023/2/1：随笔，RGB常用颜色对照表

作为一个学生，总有一些事，居于学习之上，却又被我们忽略了吧......

简介 动态规划常用于最优化或计数问题，通常要满足最优子结构（一个问题的答案可以由其子问题答案算出），无后效性（可以按某种顺序求解），子问题的重叠性（递归时可能会走到相同子问题）。 使用递归实现就是记忆化搜索，而如果我们能确定转移顺序那么我们就可以按顺序转移。 这一类问题通常考察思维，所以极其令我厌恶，通常是先设计一个状态，再想状态之间的转移，然后再优化。 背包 通常的问题形式是： 有 nnn 类物品，物品有体积 vvv，有价值 www，需要满足一定限制的条件下选择物品是的价值和最大。大多数题目的限制都是提及综合不超过 mmm。 01 背包 这个背包的特殊之处在于每类物品只有一个。 为了防止一个物品多次选择，我们采用 从大到小枚举容积 的方式做。 转移方程明显为 fi,j←max⁡(fi−1,j−v[i]+w)f_{i,j}\leftarrow \max (f_{i-1,j-v[i]}+w)fi,j​←max(fi−1,j−v[i]​+w)，可滚。 完全背包 这种背包每类物品有无限个，这样就不用关心一个物品是否多次重复选择，我们容许多次选择，那么可以 从小到大枚举容积。 转移方程不变 ...

最大流 求解方法 有两种，第一种是 EK 算法，就是每一找到一条增广路径然后加上这条边的贡献。 EK，傻逼算法！ —— uob&yny 相关法律规定，网络A流题随便卡 EK，因为它的时间复杂度是 O(VE2)O(VE^2)O(VE2) 的，效率过于低下。 所以就诞生了另一种增广路算法：Dinic 算法。 Dinic 算法类似于 EK 的多路增广版本，但是有一个非常关键的优化：当前弧优化。这个优化针对多路增广时重复遍历到某一个节点时，因为我们已经知道走某一些边已经不能再增广了，所以可以记录一下当前走到那个边了，然后从这个边进行增广即可。 时间复杂度为 O(V2E)O(V^2E)O(V2E)，在某些图上有更优的复杂度，如二分图上有 O(EV)O(E\sqrt V)O(EV​) 的优秀复杂度。 目前较好的一种实现，容易写假的地方会标出。 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465 ...

普通莫队 本质 假设有两个区间 [l1,r1],[l2,r2][l_1,r_1],[l_2,r_2][l1​,r1​],[l2​,r2​]，我们已知 [l1,r1][l_1,r_1][l1​,r1​] 的答案，如果我们能 O(x)O(x)O(x) 转移到 [l+1,r],[l−1,r],[l,r+1],[l,r−1][l+1,r],[l-1,r],[l,r+1],[l,r-1][l+1,r],[l−1,r],[l,r+1],[l,r−1]，那么就没有比较暴力 O(n)O(n)O(n) 计算下一个区间的答案，我们有期望更优的 O(x×(∣l1−l2∣+∣r1−r2∣))O(x\times(|l_1-l_2|+|r_1-r_2|))O(x×(∣l1​−l2​∣+∣r1​−r2​∣))。 观察这个式子其实不难发现，莫队的本质就是一个二维扫描线，即可以在 (x,y)(x,y)(x,y) 两轴上任意滑动。而我们的询问就是平面上的单点。 最优解是 NPC 问题，但是莫队算法已经给出了一个比较好的解，即对序列分块，然后对询问按块排序（左端点块为第一关键字，右端点位置为第二关键字）。 可以证明复杂度为 ...

线段树&平衡树 FHQ-Treap 其实就是一个通过笛卡尔树的微妙性质实现的平衡树。 不谈复杂度，只需要分析分裂合并都该如何实现就行了。 分裂： 就是将一棵树分裂成一个权值小于等于 aaa 和大于 aaa 两部分。分裂途中遍历到当前节点，如果该节点权值小于等于 aaa，那么将左子树全部合并到左边的 Treap，反之亦然。 123456789void split(int now,int k,int &x,int &y){//返回x,y：是分裂出两棵 Treap 的根,now初始值为rt if(!now)x=y=0; else{ if(val[now]<=k)x=now,split(ch[now][1],k,ch[now][1],y); else y=now,split(ch[now][0],k,x,ch[now][0]); pushup(now); } return;} 合并： 这个操作就是对于根为 xxx 和 yyy 的两棵树合并起来，其中要保 ...

基础 不写了。 优化建图 线段树优化建图 点 →\to→ 区间：直接线段树查询。 区间 →\to→ 区间：建虚点再连虚点。 CF786B & P6348 就是基本的两棵线段树优化建图，注意区间连点时线段树方向向上，点连区间时线段树方向向下。用两棵线段树时下面的子节点要逐一相连，因为他们本质是一样的。 例题：P3588 考虑建出线段树，对于每个给定区间，用他给的数分割这些区间，建立虚点连向这些被分割的区间，边权为 000，然后将给定的点连向虚点，边权为 111，然后拓扑排序模拟差分约束即可。 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394959697989910010110210310410510610710810911011111211311411511611711811 ...

字符串哈希 定义一个字符串到整数的映射 fff，称为 Hash 函数。Hash 的核心思想是将输入的字符串转化为整数方便比较。 哈希方式 通用的方法是把字符串看成一个 basebasebase 进制的数，即 fi=fi−1×base+sif_i=f_{i-1}\times base+s_ifi​=fi−1​×base+si​。 这种哈希方法需要对大质数取模或者使用自然溢出。 不难发现这种方法存在类通项公式： fi=s1×basei−1+s2×basei−2+⋯+si×base0f_i=s_1\times base^{i-1}+s_2\times base^{i-2}+\cdots+s_i\times base^0 fi​=s1​×basei−1+s2​×basei−2+⋯+si​×base0 不难发现区间 [l,r][l,r][l,r] 所形成的子串的哈希值是 fr−fl−1×baser−l+1f_r-f_{l-1}\times base^{r-l+1}fr​−fl−1​×baser−l+1。预处理 basebasebase 的幂可以做到 O(1)O(1)O(1) 处理子串哈希值。 哈 ...

可能是非官方的 floj 更新日志。 2023.11.4前 配置好基本功能。网站基本可以运作。外网暂不能访问。

二分 分为二分序列，二分数据结构，和二分答案。 需要满足有单调性才能二分。如果是一个凸壳可以三分。 二分答案 例题：P6069 注意这题对于方差何时最小是不能贪心处理的。 首先要排序，然后二分剩下的人数 kkk，枚举各个长为 kkk 的区间内的方差即可。需要推一下方差式子，时间复杂度 O(nlog⁡n)O(n\log n)O(nlogn)。 可以尺取做到 O(n)O(n)O(n)。 排序是为了选取的数连续，因为一些不连续的数向序列中连续的数转移一定不劣。 123456789101112131415161718192021222324252627282930313233343536373839// Problem: P6069 『MdOI R1』Group// Contest: Luogu// URL: https://www.luogu.com.cn/problem/P6069// Memory Limit: 125 MB// Time Limit: 1000 ms// // Powered by CP Editor (https://cpeditor.org)#include< ...

鲜花 从树论赶来的，感觉这个东西没什么用啊…QwQ 欧几里得 欧几里得算法 也称辗转相除法。 就是一个简单的式子： gcd⁡(a,b)=gcd⁡(b,a mod b)\gcd(a,b)=\gcd(b,a \bmod b) gcd(a,b)=gcd(b,amodb) 证明如下： 令 b=ka+r , gcd(a,b)=d则有 d ∣ a , d ∣ br=b−ka⇒bd−kad=rd由于左边显然为整数∴r 和 a 的公约数相等∴r 和 a 的最大公约数相等\text{令 } b=ka+r\ ,\ gcd(a,b)=d\\ \text{则有 } d\ \vert\ a\ ,\ d\ \vert\ b\\ r=b-ka\Rightarrow \frac{b}{d} - \frac{ka}{d}=\frac{r}{d}\\ \text{由于左边显然为整数}\\ \therefore r\ \text{和 } a \text{ 的公约数相等}\\ \therefore r\ \text{和 } a \text{ 的最大公约数相等} 令 b=ka+r , gcd(a,b)=d则有 d ∣ a ,  ...

DFS 和 BFS 就不写了。 记忆化搜索 就是加个 unordered_map。 例题：P8658 实际上可能是个错题，但是记忆化搜索是能过原数据的。 考虑加记忆化之后判断一下 LO*，L*L，*OL 等情况，然后再判断一下没有 * 的情况即可。 只用一个小剪枝：当检测到一次必胜的走法直接返回。 注意这道题是 000，111 存的，所以记忆化的值要加上或减去一个常量。 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162// Problem: P8658 [蓝桥杯 2017 国 A] 填字母游戏// Contest: Luogu// URL: https://www.luogu.com.cn/problem/P8658// Memory Limit: 255 MB// Time Limit: 1000 ms// // Powered by CP Editor (https://cpeditor.org)#in ...

由于联考考到了树上莫队，然后我预处理和正解一样，就是单纯打不出来树上莫队，于是来写一发学习笔记。 '树’上莫队 应该没有人直接写在树上莫队的吧，都是把树转化成欧拉序的吧。 欧拉序好像就是括号序，但是记录的是节点编号，不是点权或者点上颜色。（考试时的误区，导致没有手胡出来代码） 然后再通过节点编号定位获取相应信息。 如果节点编号出现两次，那么就无视这个点。 欧拉序举例： 这个树按重链剖分来说的欧拉序是 [0,1,4,6,6,7,7,8,8,4,3,3,1,2,9,9,5,5,2,0][0,1,4,6,6,7,7,8,8,4,3,3,1,2,9,9,5,5,2,0][0,1,4,6,6,7,7,8,8,4,3,3,1,2,9,9,5,5,2,0]。 我们可以从中发现一些规律。 令 st[a]st[a]st[a] 为编号 aaa 第一次出现的位置，ed[a]ed[a]ed[a] 为编号 aaa 第二次出现的位置。 如果此时我们要询问路径 7→27\to 27→2，发现 dfn7<dfn2dfn_7<dfn_2dfn7​<dfn2​，那么取 [ed[7],st[2]][ed ...

CF212E IT Restaurants 标签：01 背包，dfs 题意 给定一个 nnn，表示有 nnn 个节点（1∼n1\sim n1∼n）以及接下来 n−1n-1n−1 条边的树，现用两种颜色（红，蓝）对这颗树的节点染色，染色规则是，每个节点有三种状态，要么染成红色，要么染成蓝色，要么不染色，并且规定用一条边连接的两个节点要么染成颜色相同，要么一个染色一个不染色。 问在保证染色节点最多的条件下，红色与蓝色的个数的情况。（要求是至少有一个节点被染成红色，至少一个节点被染成蓝色）。 解法 结论容易看出来，只可能有一个无色格子，剩下两部分要么是红色要么是蓝色。 对于每个节点把每个子树的大小记录下来，然后对这些数进行 01 背包，来计算这些数的组合有哪些，再把答案数组对当前记录哪些数能取到的数组进行每位与。 AC 记录

鲜花 听 Mea 讲树论，但是还是脱不了修锅的命运（ 注：本文中，dfs 序 等同于 dfn 序。 树的基础 树的直径 定义就是树上的最长路径，非常好理解。 求法 对于所有树 对于所有树，均可以使用树形 DP 的方式求解，但是带负权的树据 Mea 说非常抽象，不怎么考，所以没什么用（ 记录最长路和次长路即可。 参考代码（现场写的）： 123456789101112131415161718int d1[N],d2[N],len;void dfs(int now,int fa){ d1[now]=d2[now]=0; for(int i=head[now];i;i=E[i].link){ if(E[i].to==fa)continue; dfs(E[i].to,now); int temp=d1[E[i].to]+E[i].v; if(d1[now]<temp){ d2[now]=d1[now]; d1[now]=temp;//d1与d2 ...

鲜花 lxs 的歌好好听！ 下载lxs.mp3 考试 lxs contest #1(184-re)那场属于是放水了，看到不会 T2 直接不做了，赛时的时候甚至去调了一道根号分治，如如题，结果是 rrr 和 lll 写反了。 lxs contest #2(188-re)挂了 20 分，因为没开 long long，如如！直接沦为暴力分。T2 写莫队乱搞过去（但是挂了 20）了，这还是我第一次考试写莫队，但是没想到可以用前缀和 O(1)O(1)O(1) 解决。T1 不会是首次，但是 T3 不知道怎么算期望，T4 看不懂，直接放弃（ 以下是在 #188 赛后未评讲时看懂了的题的简要思路： #184 T1：模拟，略。 #184 T2：考虑一个结论，段数不超过 222，那么直接 dp 求最大单调上升子序列即可。 #188 T2：先双指针求出以每个点为起点的最短满足条件的子段，然后推式子+前缀和即可，当然，莫队这种方法对于无脑求解是很管用的，毕竟这比出题人的目标复杂度（O(nlog⁡2n)O(n \log^2n)O(nlog2n)）快多了。 做题 为什么国庆不讲课？ 为什么国庆不讲课？ 为什么国庆 ...

20230924周总结 该文同步发布到我的个人博客上。（什么？你说你不知道我的个人博客在哪里？很好！） What I’ve Learned 对于dp，除了树形dp一窍不通。讲dp优化那天全程掉线。 图写的非常顺手，Tarjan基本已掌握，就是判断题目中对于求哪些连通分量还需加强。 之前我一遇到树或者图就不想写，现在除了树或者图或者计算几何其他都只想着找规律了。 在0922（周五）那天自己把费用流的所有算法写了一遍，主要是想比较一下各种算法的效率，然后感觉现在费用流比最大流都还好写。 About Exams 这周只考了一场。 T1简单规律题，但是CF评级2600，笑死。 T2毒瘤计算几何，谁知道多边形的重心怎么求啊，差评。 T3，T4不会，跳了。 罚坐30min。 Things going to do 写费用流题解（幸亏没关题解区 狂肝dp。 没了 <br> <br> <br> <br> <br> <br> <br> <br> <br> <br> < ...

前言 从这里开始，信竞的路就开始向未来延伸了 之前觉得信息竞赛不过是打打电脑，敲敲代码，从来没想到这其实是对思维的一种锻炼。 信息竞赛的终端是NOI，也就是国赛，那场比赛会让一部分人极度高兴，也会让一部分人迷惘，无奈，最后退役，除这两者之外，也会有一些人陷入沉思—— 无数高二的OIer，他们两年，三年，甚至五年，六年的OI生涯，就在走出NOI赛场的那一刻，彻底终结。 原文链接：link（经过2d左右的寻找终于找到了） … 让我们开始吧… 什么是Splay？ 用一个经典问题引入： 你需要维护一些数，其中需要提供以下操作： 插入 xxx 数 删除 xxx 数(若有多个相同的数，应只删除一个) 查询 xxx 数的排名(排名定义为比当前数小的数的个数 +1+1+1 ) 查询排名为 xxx 的数 求 xxx 的前驱(前驱定义为小于 xxx，且最大的数) 求 xxx 的后继(后继定义为大于 xxx，且最小的数) 1≤n≤1051\leq n \leq 10^51≤n≤105 因为有操作2，这道题暴力的时间复杂度是 O(n2)O(n^2)O(n2) 的。 那么，二叉搜索树就出现了—— 二叉搜 ...

双倍经验：P6406P6406P6406 题目描述 给定一个序列$ a_i,\cdots,a_n $，求： ∑i=1n∑j=in(j−i+1)min⁡(ai,ai+1,⋯ ,aj)max⁡(ai,ai+1,⋯ ,aj)\sum_{i=1}^{n} \sum_{j=i}^{n} (j-i+1) \min(a_i,a_{i+1},\cdots,a_j) \max(a_i,a_{i+1},\cdots,a_j) i=1∑n​j=i∑n​(j−i+1)min(ai​,ai+1​,⋯,aj​)max(ai​,ai+1​,⋯,aj​) 分析 根据 $ n \leq 5\times10^5 ，，，O(n^3)$ 的暴力肯定要炸，于是考虑分治，即把序列分成左区间与右区间，分别计算以下三种情况： 区间左右端点均落在左区间。 区间左右端点均落在右区间。 区间左端点落在左区间，区间右端点落在右区间。 其中第 111，222 种情况用分治递归解决就行了，于是来着重解决如何求第 333 种情况的问题。 首先，暴力枚举求第 333 种情况的时间复杂度显然是 O(n2)O(n^2)O(n2)，总时 ...

题目描述 给定 $ n $ 个点 (xi,yi)(x_i,y_i)(xi​,yi​)，求半径最小的圆使该圆能覆盖所有的点。 所以这是一道最小覆盖圆的板子题，双倍经验：P1742 实现 使用随机增量法： 很容易我们能证明，若第 $ i $ 个点不在前 $ i-1 $ 个点的最小覆盖圆上，那么第 $ i $ 个点在前 $ i $ 个点的最小覆盖圆上。 这个时候，就要求前 $ i $ 个点的最小覆盖圆了。在初始化时，把圆心设为第 $ i $ 个点的坐标，半径设为 $ 0 $，强制使这个点在圆上。然后枚举就行了，如果当前这个点在当前这个圆外时就去求第 $ i $ 个点与该点在圆上时的最小覆盖圆，这个时候就要枚举除这两个点以外的第三个点（三点定圆）。枚举结束后就能求出前 $ i $ 个点的最小覆盖圆。 注意循环不用从 $ 1 $ 到 $ n $ 全部枚一遍，这样会造成重复枚举。 12345678910111213for(int i=1;i<=n;i++) if(!is_po_in_circle(a[i],c)){ c=get_circ(0,a[i]); ...