FrankWkd

“爱我所爱，行我所行，无问西东。” “个性签名是什么就缺什么。” “你必须跳下悬崖，在坠落中生出翅膀。” “终有若水济沧海，再无相思寄巫山。” “The night is young, the song is loud. ———— 《Here With You》” “夜未央，曲未殇” “Nothing is pure.But solitude.” “没有什么是纯真的，除了孤独。” “We are far from perfect. But we are worth it.” “此身天地一虚舟，何处江山不自由。” 12345678910111213Flowers do not wither花无凋谢之日Meaning no transmission意无传达之时Love everlasting爱情亘古不变Violet forever紫罗兰永世长存

真是个让人头疼的算法，学一次忘一次（尴尬 写篇笔记记录一下防止忘了（嘻嘻 前言：这里将以 OI-Wiki 的内容为主，对 OI-Wiki 部分较难的内容进行解释和补充。补充的内容均为笔者补充。 特别感谢 OI-Wiki、AC自动机-Author: iamtwz, Marcythm, 383494, abc1763613206, aofall, Chrogeek, CoelacanthusHex, Dafenghh, DanJoshua, Enter-tainer, GavinZhengOI, Gesrua, Henry-ZHR, Ir1d, kenlig, ksyx, lyccrius, Menci, opsiff, orzAtalod, ouuan, partychicken, Persdre, qq2964, Ruakker, shuzhouliu, sshwy, StudyingFather, szdytom, Tiphereth-A, Xeonacid, ZXyaang, rickyxrc, XuYueming520 概述 AC（Aho–Corasick）自动机是 以 T...

Upd 2025-07-30 修复公式错误，修复文章内链接错误，补充题目和模板公式 不是很难的算法，思路也不算难～ 定义 区间类动态规划是线性动态规划的扩展，它在分阶段地划分问题时，与阶段中元素出现的顺序和由前一阶段的哪些元素合并而来有很大的关系。 令状态 f(i,j)f(i,j)f(i,j) 表示将下标位置 iii 到 jjj 的所有元素合并能获得的价值的最大值，那么 f(i,j)=max⁡{f(i,k)+f(k+1,j)+cost}f(i,j)=\max\{f(i,k)+f(k+1,j)+cost\}f(i,j)=max{f(i,k)+f(k+1,j)+cost}，costcostcost 为将这两组元素合并起来的价值。 性质 区间 DP 有以下特点： 合并：即将两个或多个部分进行整合，当然也可以反过来； 特征：能将问题分解为能两两合并的形式； 求解：对整个问题设最优值，枚举合并点，将问题分解为左右两个部分，最后合并两个部分的最优值得到原问题的最优值。 一般的区间 DP 题目的状态转移方程： dpi,j=max{dpi,k+dpk+1,j+<decision...

字符串哈希学习笔记 OP：哇 好难懂 谁发明了这恶心的算法。。。 字符串哈希 1.字符串哈希作用 将字符串计算为一个整数。 要求： 不同的字符串映射为不同的值，同一个字符串映射为相同的值。 2.如何计算字符串的哈希值 将字符串视为P进制的数字，经验上 P=131、13331P=131、13331P=131、13331 . 如果字符串仅包含大写、小写、数字字符其中之一，比如：a...za...za...z，将其映射为 1..261..261..26。 一定不能将字符映射为 000 。 3.计算出来的结果太大，将结果 %h。(h=264)\%h。(h=2^{64})%h。(h=264) %h 的方法：将计算结果直接赋值给 unsigned long longunsigned\ long\ longunsigned long long . 4.如何计算区间哈希值：利用滚动(前缀)哈希值，计算区间哈希值。 前缀哈希值：h[i]=h[i−1]∗P+(s[i]−′a′+1)h[i]=h[i-1]*P+(s[i]-'a'+1)h[i]=h[i−1]∗P...

RMQ学习笔记 前言:这个算法无论是从适配性还是长度来说都很有实力…💦 关于 RMQ RMQ 是英文 Range Maximum/Minimum Query 的缩写，表示区间最大（最小）值。 详细信息 求 l−rl-rl−r 区间内的最大/最小数. 区间构造 本质是DP.设 f[i][j]f[i][j]f[i][j] 为 i∼i+2j−1i\sim i+2^{j-1}i∼i+2j−1 的区间最大值.特别地,f[i][0]=a[i]f[i][0]=a[i]f[i][0]=a[i].(一个数的最大值是它本身). 状态转移方程: f[i][j]=max(f[i][j−1],f[i+2j−1][j−1])f[i][j]=max(f[i][j-1],f[i+2^{j-1}][j-1])f[i][j]=max(f[i][j−1],f[i+2j−1][j−1]). 区间查询 设要查询的区间为 [L,R][L,R][L,R] (包括LR) k=log2(R−L+1)k = log2(R-L+1) k=log2(R−L+1) res[L][R]=max(f[L][K],f[R−2k+...

LCA学习笔记 LCA指最长公共子序列,可以使用倍增的方法求解(复杂度较优) 步骤 (1) 预处理 a. 求深度: 对于每个结点 dfsdfsdfs 预处理出结点深度; b. 求倍增祖先: 计算出每个结点向父元素跳 20,21,22,...,2k2^0,2^1,2^2,...,2^k20,21,22,...,2k 步所到达的点( 2k2^k2k 指大于整棵树的最大深度) (备注)a. f[x][k]:xf[x][k]: xf[x][k]:x 上跳 222 步能到达的祖先,如对应结点不存在 f[x][k]=0f[x][k]=0f[x][k]=0 . (备注)b. 将路径长度 2k2^k2k 分为两半, xxx 跳 2k2^k2k 次到的祖先 =x=x=x 跳 2k−22^{k-2}2k−2 次到的祖先再次跳 2k−22^{k-2}2k−2 次.因此可得: f[x][k]=f[f[x][k−1]][k−1]f[x][k]=f[f[x][k-1]][k-1]f[x][k]=f[f[x][k−1]][k−1]. c. 预处理时间复杂度为 O(nlog2n)O(nlog_2n)...

Upd 2025-07-30: 补充注释和文字内容 前言：这把高端局 关于KMP 时间复杂度为 O(n+m)O(n+m)O(n+m) 的优秀字符串查找算法。 适用于在句子/文章中查找一段文字（词语）。 KMP实现 关于共同前后缀数组（PMT） 说人话就是 nextnextnext 数组。 是什么？ nextinext_inexti​ 表示下标从 111 到 iii 的子串（后文中叫做 OrginOrginOrgin 串）中既是 OrginOrginOrgin 的前缀串又是 OrginOrginOrgin 的后缀串的字符串的最长长度。 举例说明：开始时候的串为：abcab 那 next5=2next_5=2next5​=2 ，因为存在串 ababab 既是 OrginOrginOrgin 的前缀又是 OrginOrginOrgin 的后缀，而且在所有满足条件的串中，它是最长的。所以把 next5next_5next5​ 设为它的长度—— 222. 构建 PMTPMTPMT 的详细步骤 初始化：设模式串为 PPP，长度为 mmm，创建一个长度为 mmm...

前言：阅读理解+剪枝+头脑风暴 ##### Designed By FrankWkd **遵循GNU GPL2.0开源协议。** ## 该代码可以通过[T148457 生日蛋糕加强版](https://www.luogu.com.cn/problem/T148457) 和 [P1731 [NOI1999] 生日蛋糕](https://www.luogu.com.cn/problem/P1731).  ---- # P1731 [NOI1999] 生日蛋糕 ## 题目背景 [数据加强版 link](https://www.luogu.com.cn/problem/T148457) ## 题目描述 7 月 17 日是 Mr.W 的生日，ACM-THU 为此要制作一个体积为 $N\pi$ 的 $M$ 层生日蛋糕，每层都是一个圆柱体。 设从下往上数第 $i$（$1 \leq i \leq M$...

树上差分 点的差分 求路径 u−vu-vu−v 上的点被经过的次数. cnt[x]cnt[x]cnt[x] 表示点 xxx 被经过的次数. 核心代码: 1234cnt[u]++;cnt[v]++;cnt[lca(u,v)]--;cnt[father[lca(u,v)]]--; 边的差分 求 u−vu-vu−v 路径上每条边的经过次数 cnt[x]cnt[x]cnt[x] :代表 xxx 向上的边经过的次数. 核心代码: 123cnt[u]++;cnt[v]++;cnt[lca(u,v)]-=2; A. 运输压力 解法 树上查分板子题啊 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475#include <bits/stdc++.h>using namespace std;const int N = 5e4 + 20, L = 20...

前言：在这个毒瘤算法上，比起证明，我更喜欢背模板。Awa 树状数组 树状数组是一个查询和修改复杂度都为 log2nlog_2nlog2​n 的数据结构。主要用于：单点修改，区间求和。 树状数组的管理区间： tr[i]:i−lowbit(i)+1∼itr[i]: i-lowbit(i)+1\sim itr[i]:i−lowbit(i)+1∼i tr[i]tr[i]tr[i] 的特点： a·除根外，结点 xxx 的父结点 =x+lowbit(x)=x+lowbit(x)=x+lowbit(x) b.除根外，结点 xxx 的前一个“结点” $ =x - lowbit(x)$ c.树的深度 =log2n=log_2n=log2​n 单点修改 在 aaa 数组下标为 xxx 的位置 +v+v+v 123void update(int x,int v){ for(int i = x;i <= n;i += lowbit(i)) tr[i] += v;} 前缀和 trtrtr 求 [1,x][1,x][1,x] 所有数的和 1234int qu...