差分约束系统
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
信息,之后就可以类似于 ...
基于 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 ...
前言:
FWT, FMT 金牌知识点, 现在没必要学来着, 但题看都看了, 就顺便学了吧,
反正是个板子类的东西
( 目前大概都是当板子用了, 只能写写应用, 具体原理是一点不懂得,
我太蒟蒻l )
知识点
FFT - 快速傅里叶变换
多项式 F(x) = a0 + a1x1 + a2x2⋯,
令 fi
为 i 次项系数, 也就是 ai
多项式乘法:
说白了 fft 就是优化普通卷积, 也就是优化多项式乘法的工具
时间复杂度 O(nm) → O(nlog)
luogu - FFT
模板
MYCODE
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394959697989910010110210310410510610710810 ...
B.Blocks
题意:
平面上有 n 个方块,
给出左上右下角坐标, (x1, y1), (x2, y2)
不断重复以下操作
随机选任意一个 (可能重复选同一个)
将该方块涂黑
一直操作直到 [0, 0] × [W, H]
的区域被完全涂黑
求操作期望次数
(n ≤ 10, x, y, W, H ≤ 1e9)
解析:
n 很小, 容易想到状压 dp
定义 dpS →
从状态 S 到完全染黑的期望次数,S 中的 1 代表该矩形选过
期望 dp 方程化简
若染色已经完成, 则期望步数为 0, dpS = 0
选到已选过的矩形, 概率 , 形成环,
移项即可解决
令 S 为当前的状态, x 为
S 中 1 的个数
判断已经全部染黑
提供两种方法
1. 二维离散+二维差分:
不难发现大部分区域都是无用的, 对 x, y 轴分别离散即可
离散后大概只有 21 行/列
现在想要 [x1, y1] × [x2, y2]
的矩形区域 +1
离散后范围较小, 可以直接暴力对矩形区域 +1
之后暴力 ...
XCPC
未读HDU
25春季联赛 - 0 - 1007
题意:
给定长度 n 的数组 a,
定义 [l, r] 价值为
⨁i = lrai ⋅ (r − l + 1),
定义 f(a) 为数组
a 划分后的最大价值和,
求
(n ≤ 2e5, 0 ≤ ai < 1024)
解析:
很容易想到 n2
dp
pre
为前缀异或数组
定义 dpi
→ 用前 i 个元素能得到的最大价值
转移方程:
复杂度不可接受, 尝试优化
我们拆开式子:
1.先考虑一个更简单的式子: 观察左侧部分: dpj − (prei ⊕ prej) ⋅ j
当我们在 j 时, 未知量只有
prei
定义 g(x) → max{dpj − (x ⊕ prej) ⋅ j}
我们遍历到 j 时, 对所有可能的
x 的值进行预处理
转移方程:
由 ai < 1024
可知 x < 1024
预处理时间复杂度 O(1024)
转移复杂度 O(1)
总时间复杂度 O(1024 ⋅ n)
2.让我们回到原式 类似地
定义 g( ...
XCPC
未读CF1887D
题意:
定义一个数组是好的,仅当其可分割成两个非空数组,使得左边元素都小于右边元素
即满足 max(al…ak) ≤ min(ak + 1…ar)
给定排列,q次查询,问 [l, r] 的子数组是否是好的
(n, q ≤ 3e5)
解析:
固定 l,r,若枚举 k,左右两侧都是单增,因此整体不存在单调性
法 1:
二维离线
从值考虑
我们考虑左侧区间中的最大值,
若 ai
成为最大值,我们记 i 左侧第一个大于 ai 的元素位置为
l1,则有限制 l1 < L ≤ i
我们记 i 右侧第一个大于 ai 的元素位置为
r1,记 r1 右侧第一个小于 ai 的元素位置为
r2,则有限制 r1 ≤ R < r2
这样的 [L, R] 就是左侧以 ai
为最大值的好区间
( i 左右找 > ai
的第一个位置是很典的问题,可以用单调队列,笛卡尔树,按值枚举甚至还可以用
set )
也就是,以 ai
为最大的合法情况落在矩阵 L ∈ [l1 + 1, i], R ∈ [r1, r2 − 1 ...
前置知识 - 状压 dp:
(220 ≈ 1e6,317 ≈ 1e8)
1. SOS DP - 子集和 dp:
每个集合有一个权值f(S),我们想求集合 S 所有子集的权值和 dpS,即
(注意:每个子集有且仅有一次贡献)
若暴力求解,枚举S,然后枚举sub,时间复杂度 O(3n)
SOS dp:先枚举位,让所有集合逐位转移,时间复杂度 O(n ⋅ 2n)
[理解参考]
参考代码
123456789// f(S) 权值数组已知dp = f; // 赋初值for(int p=0; p<20; p++){ // 先枚举位 for(int S=1; S<=full; S++){ // 再枚举所有集合 if(S >> p & 1){ dp[S] += dp[S ^ (1 << p)]; } }}
2. 子集划分 dp
时间复杂度 O(3n)
大致操作是枚举 mask,然后枚举子集 S,和补集 T
然后 merge(S, T)
和区间 dp 一 ...























