基于 WIDA XCPC
模板，在此基础上对其补充和优化
图论
LCA 最近公共祖先
倍增 LCA
1234567891011121314151617181920212223242526272829303132333435vector<int> dep(n + 1), p(n + 1);auto dfs1 = [&](auto&& self, int fa, int u) ->void { dep[u] = dep[fa] + 1; p[u] = fa; for(int v : gra[u]) if(v != fa) { self(self, u, v); }};dfs1(dfs1, 0, S);int MX = __lg(2*n - 1);vector<vector<int>> st(n + 1, vector<int>(MX + 1));for(int i=1; i<=n; i++) st[i][0] = p[i];for(int j=1; j ...
牛客寒假集训营 4
D-数字积木 题解
题意
给定 n 个节点的树，点权构成一个 [0, n) 的排列，求所有连通块的 mex
权值和
思路
将 mex 权值和 转化为 连通块计数。具体来说，分别统计包括 {0}，{0, 1} …
{0,…,n-1} 的连通块个数，求这些个数之和就等价于求所有连通块的 mex
权值和。
举个例子，若我们有一个 mex=4 的连通块 S，包括 {0, 1, 2, 3, (mex=4),
…} 这些数字。当我们统计包括 {0} 的连通块的个数时，S 会贡献 1，然后是统计
{0, 1}，{0, 1, 2}，{0, 1, 2, 3}，S 也都会贡献 1，一共贡献了 4，正好和其
mex 权值相同
dp 进行连通块计数
令 dp[i] 为 i 必选，i
的子树的连通块个数，每个子节点可选可不选，转移方程为
更新集合贡献
若上一次的必选集合是 {0, 1, 2 … x}，贡献是 lst
现在我们要将 x+1 加入集合，我们从 x+1
开始，不断的向上直到遇到已经必选的点，更新贡献
这样就将经过的点都变成了必选点，之 ...
XCPC
未读前言
刷刷某大佬整理的区域赛铜牌题题单
(十分之感谢!)
记录一下知识，顺便梳理思路
BA - BZ
BA - The Only Way to the
Destination
难度: 2.5
问，任意两方块是否有唯一的简单路径。
思路
首先特判 n = 1 的情况，一定满足，一开始忘判了
n >= 2，发现存在 2 × 2
的方格就不能满足条件，而由于墙的列数不会很多(k ≤ 1e5)，所以 m ≤ 1e9 其实是诈骗，m >
3k
就肯定会有并列的两个空行，一定无法满足条件。此外，可以想象，若存在某个墙组成的连通块不和边界相连，则一定是因为某个路径将其包围，形成了一个环，这种情况一定不满足。
若合法，则一定有 m < 3k，于是我们可以枚举列，判断是否存在
2 × 2
的情况。判断墙是否和边界连通，可以对墙建图后 dfs
整体感觉不是很好写，比较考验码力
另外还要注意，墙是 8 连通而不是 4 连通
MYCODE
12345678910111213141516171819202122232425262728293031323 ...
为文章封面添加加载动画
把白板换成了一个可爱的加载动画，如下图
难点在我终于找到监测 pjax 换页的方法，使用
history.pushState 就可以
在 themes/anzhiyu/source/js 里新建
cover_loading.js，加入下面代码
1234567891011121314151617181920212223// 自定义事件 , 监测 url 改变 (pjax)(function() { const _pushState = history.pushState; history.pushState = function(...args) { _pushState.apply(this, args); window.dispatchEvent(new Event('urlchange')); };})();const loadingImg = 'https://cdn.amiracle.site/loading.gif';function setloadingImg() { c ...
差分约束系统
n 个未知量 x1, x2 ⋯ xn，m 个不等式条件
这样的一组不等式就是一个差分约束系统，差分约束系统的求解可以巧妙的转化为最短路问题
和最短路的关系
先移项，得到
，可以发现和最短路中的三角不等式非常相似，。因而可以转化成最短路问题，具体来说，先对不等式建图，每个不等式都可看成边，让
j 向 i 连一条权为 c 的边，此图上跑最短路，得到的 disi
就是一组满足条件的解。
转化的充要性证明
限制条件转化为有向边，跑最短路得到的 dis 满足
，把 disu, disv
看成 xu, xv
的话，也就是
，因而当最短路有解，也就是没有负环，原不等式就有解，且解就为
dis，必要性成立
思考一下变量关系，若是关系无环比如说是一条链，容易想到，此时的不等式和最短路都是有解的。若是变量关系成环，设存在一个有向环
，对应的边权依次为 ，，，。
由每条边对应的约束，有 将上述不等式逐项代入相消可得 若不等式组有解，则必有
否则会出现矛盾，而这也意味着图中不存在负环，所以此时最短路也是有解的，充分性成立
因此，不等式组有解等价于图中 ...
今日一言 : Now or Never.
前言
换根 dp，用于解决根不固定的问题。所谓换根
dp，就是先求出一个根的答案，然后让子为根，将贡献由父转移到子，这样就能快速计算
n 个点分别为根时的答案
换根 dp 分为三步 :
先把树拎(ling)起来，找一点为根
计算每个子树的贡献
从根开始，由父节点向子节点传递贡献
洛谷 P3478
题意
找一个点，使其到所有节点的距离之和最大
解析
若选定一根，我们能 O(n)
求出距离之和，但每个节点都要算一次，那岂不是要 O(n2)
换根 dp 的思想可以轻松解决这个问题
先固定一个点为根，令 :
siz[u]
为子树的大小
ans[u]
为所有点到 u 的距离之和
我们可以先计算出根节点的答案，然后换根，若 u → v
进行转移，则转移方程为：
每次转移的时间复杂度 O(1)，从根开始，向子转移，O(n)
即可计算出所有点为根时的 ans，最后求 max 即可
MYCODE
123456789101112131415161718192021222324252 ...
前言
建站之后，很难没有统计网站访问人数的想法，本篇在 hexo 框架 + anzhiyu
主题环境下，利用 umami 0
成本实现网站流量统计，并实现统计模块。顺便说一下模块开发历程吧
(真是一波三折啊)
umami 统计工具感觉很 nice 啊，首先是 0 成本，然后你还能直接用它的
Umami Cloud 而不用部署自己的数据库，展示的数据也很全面，网页的 GUI
看着也是蛮舒服的
GUI 参考
写 umami 模块的过程也是挺坎坷的，遇到了很多坑。
准备工作
为了使用
umami，要先得到三样东西，website id，tracking code
和 api key，简单带过
首先在 umami 官网
注册账号，之后到控制台新增网站，然后打开右侧设置页面
可以看到 Website ID 和 Tracking code
为了统计网站数据，我们需要将 <script>
代码片段插入到网页的 <head>
里面，当有人访问网站时，该脚本会自动向 umami 发送数据以进行统计。在
anzhiyu 主题，主题 ...
可持久化线段树是动态开点的权值线段树，同时维护了历史信息
对于一个普通的权值线段树，当我们让 cntv + +
时，影响的节点个数是 logn，可持久化线段树的插入操作就是基于此。也就是，当我们插入新值时只需要动态的新建
logn
个节点即可，其他节点都可以复用上个版本。这样我们就可以在较小的时空复杂度维护所有的历史记录，然后利用前缀和的思想维护区间信息。
简单应用区间第 k 大
我们将 ai 依次插入，用
cnt
维护某值域值的个数。若要查 [l, r] 的第 k 大，因为维护了插入了 a[1, l − 1] 和 a[1, r] 时的所有的 cnt
信息，就可以利用前缀和思想算出，只插入 a[l, r] 的 cnt 信息。
具体来说，若有节点 p，其对应值域 [x, y]，在插入 a[1, l − 1] 后值的数量为
cntu，在插入
a[1, r] 后为 cntv，则
cntv − cntu
就是 i ∈ [l, r], ai ∈ [x, y]
的值的个数。
这就相当于对于一个区间 [l, r]，知道了每个值域段的
cnt
信息，之后就可以类似于 ...
前言：
FWT, FMT 金牌知识点, 现在没必要学来着, 但题看都看了, 就顺便学了吧,
反正是个板子类的东西
( 目前大概都是当板子用了, 只能写写应用, 具体原理是一点不懂得,
我太蒟蒻l )
知识点
FFT - 快速傅里叶变换
多项式 F(x) = a0 + a1x1 + a2x2⋯，
令 fi
为 i 次项系数, 也就是 ai
多项式乘法：
说白了 fft 就是优化普通卷积, 也就是优化多项式乘法的工具
时间复杂度 O(nm) → O(nlog)
luogu - FFT
模板
MYCODE
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394959697989910010110210310410510610710810 ...
Fujian CCPC 2025 - invitational
& Fujian CPC
2025/08/20
本场难度
Eazy：M 致谢
Easy-medium：G 炒股高手、J
构造大师CFJ、K VERTeX
Medium：C 中位数、E
卡牌游戏、H 难以控制的火箭滑板、I 割 点
Medium-hard：D 二叉树、L 众数、B XCPC、F
帕累托前沿
Hard：A we are watching you!
赛时做题
M, K, J, L
补题
H, G, E, C
尝试/未补出
B 已会未写
UPD : B 题已 AC, 解析详见二阶差分
历程
一开始看 B 题，放弃后不知道为什么一直以为这是
G(某签题)，就导致比赛结束都没写这道签。H 题，吃饭快点就过了 ( 。C
题二分看不出来，虽然补了之后发现真的简单。
Shenyang ICPC 2024 -
regional
2025/08/22
本场难度
Easy：J
Medium-Easy：B、D、E、M(+)
Medium：A(+)、G( ...
