BzhH

动态 DP NOIP居然会考这种东西，所以不得不来学一下 结合着上面这道题，可以看出，动态DP就是一个动态规划问题加上了修改操作， 如果每一次修改我们都去跑一遍动态规划，时间复杂度直接起飞，所以这时候就要想办法优化。 首先看一下这道题如果不带修改操作该怎么做 令 fi,0/1f_{i,0/1}fi,0/1​ 表示以 iii 为子树不选/选 iii 的最大点权独立集 那么状态转移方程就为 {fu,0=∑max⁡(fv,0,fv,1)fu,1=au+∑fv,0\begin{cases}f_{u,0}=\sum\max(f_{v,0},f_{v,1})\\f_{u,1}=a_u+\sum f_{v,0}\end{cases}{fu,0​=∑max(fv,0​,fv,1​)fu,1​=au​+∑fv,0​​ 一个简单的树上DP,可以看出,每个结点只会对他的父亲结点造成影响. 这时候如果我们修改了其中一个结点,那么他只会对在他这条链上的祖先结点造成影响, 如果这条树的高度比较平均,那么就只需要 log(n)log(n)log(n) 次,可惜如果这棵树退化成链,那么一次修改就需要 nnn次, 显然 ...

在做一道题的时候遇到了就顺手学了 罗马游戏 刚开始打的线段树合并,结果空间直接炸裂,然后尝试玄学得了60分 后面看标签才知道要用左偏树. 左偏树满足下面几个性质 1.根节点的 valvalval 小于儿子节点的 valvalval 2.左儿子到叶子结点的 disdisdis 大于等于右儿子的 disdisdis 3.根节点的 disdisdis 等于右儿子的 dis+1dis + 1dis+1 以及一些其他关于树的大小的证明 然后是左偏树的一些操作 合并操作 int merge(int x, int y){ if (!x || !y) return x + y; if (tr[x].v > tr[y].v) swap(x, y); rs = merge(rs, y); if (tr[ls].dis < tr[rs].dis) swap(ls, rs); tr[ls].rt = tr[rs].rt = tr[x].rt = x; tr[x].dis = tr[rs].dis + 1; return x;} 让 xxx 作为根节点, yyy 连到 xx ...

感觉是一道很好的单调队列优化DP 首先 O(n3)O(n^3)O(n3) 的朴素DP很好想 令 fif_ifi​ 表示前 iii 获得金币的最大值,不难的出状态转移方程 fi=max⁡1≤j≤p(fi−k−costi−k+vali−k−>i)f_i=\max\limits_{1\le j\le p}(f_{i-k}-cost_{i-k}+val_{i-k->i}) fi​=1≤j≤pmax​(fi−k​−costi−k​+vali−k−>i​) valvalval 的求法可以通过维护一个对角线上的前缀和,我们先将道路的权值转化为点的权值, 即转化到道路终点上,为了方便,我们让工厂的编号从0开始,这样就可以通过取模直接表述出走之前的点 这样就可以写出朴素版的DP for (int i = 1; i <= m; i++) for (int j = 0; j < n; j++) for (int k = 1; k <= min(p, i); k++) f[i] = max(f[i - k] + sum[i][j ...

算是NOIP中比较麻烦的题了,看题解感觉处理的很巧妙 题意就不再赘述了，刚开始的想法是遍历枚举每一条路径，但是无论如何这样做的复杂度最坏都有O(nm) 所以尝试换一种方法,从观察员下手,对于每一个观察员,我们只需要找到每一条路径带给他的贡献 那这个贡献怎么求呢? 对于每一条路径(u,v),我们都可以将它拆为 u->lca 与 lca ->v 假设观察员的位置p在 u-> lca 上,当depth[u]+w[p]=depth[p]时才会有贡献 而当p在 lca->v 上时,只有dist(u,v)-(depth[v]-depth[p])=w[p],即dist(u,v)-depth[v]=w[p]-depth[p]时才有贡献 然后是统计贡献,如果我们在统计贡献时也一个一个去计算,那么复杂度就又上去了,所以这个时候可以用一个桶来处理, 这也是这道题比较巧妙的一点, 先看u->lca,对于点x,我们将它贡献的答案存在cnt[depth[x]]里,对于这条路径上的点p,更新答案就只需要加上cnt[depth[p]+w[p]] 对于lca->v,我们就将答案贡献存 ...

【模板】莫队二次离线（第十四分块(前体)） 题意就不再赘述了,二次离线莫队相比于其他莫队,算是细节最多的一种莫队了 思路 首先只考虑增加一个数 若两个数 i,ji,ji,j 的异或和的二进制表示有 kkk 个一,我们称之为一个配对 显然,增加一个数对答案的影响为 [L,R][L,R][L,R] 与 wR+1w_{R+1}wR+1​ 配对的数的个数 显然,可以用前缀和思想,令 SiS_iSi​ 表示前 iii 个数与 wR+1w_{R+1}wR+1​ 配对的数量 那么区间 [L,R][L,R][L,R] 的配对数量就为 SR−SL−1S_R-S_{L-1}SR​−SL−1​ 然后这个前缀和怎么求? 不妨令 f(i)f(i)f(i) 表示前 w1−wiw_1-w_iw1​−wi​ 中与 wi+1w_{i+1}wi+1​ 配对的个数 g(x)g(x)g(x) 表示前 iii 个数中与 xxx 配对的数量 f(i)=g(wi+1)f(i)=g(w_{i+1})f(i)=g(wi+1​) 考虑 g(x)g(x)g(x) 怎么求 因为 0≤k≤140\le k\le140≤k≤14,那么二进制表 ...

暴力出奇迹,n2n^2n2 过百万 普通莫队 [SDOI2009]HH的项链 虽然这道题 nnn 有 10610^6106 但卡一卡还能过 首先考虑最暴力的暴力,直接枚举就行了 然后莫队是怎样去优化这个暴力的? 先定义两个指针 l,rl,rl,r 表示当前已经求出区间 [l,r][l,r][l,r] 的答案,对于询问 [L,R][L,R][L,R], 实际上只需要移动 l,rl,rl,r 即可,如果有一种办法能够使移动的次数最小,时间复杂度会不会降下来呢? 莫队正是利用了这一点,考虑离线处理所有询问,对区间左端点分块,对于左端点在同一块中的两个询问, 按照右端点编号排序,否则,按照左端点编号排序,这里有一个优化,奇偶性排序,就是奇数块升序排,偶数块降序排, 对于一些大数据可能会有用.那么这么排为什么会快? 先考虑左端点,左端点只会有两种移动方式,在块内移动与再两个块间移动 块内移动的距离显然是不超过块的大小的,这里定义块的大小为 n\sqrt{n}n​,一共 mmm 此询问,那么时间复杂度就是 O(mn)O(m\sqrt{n})O(mn​) 在两个块之间移动,考虑最远距离 2n2\sq ...

反演+矩阵树 首先题目要求的是 ∑T∑i=1n−1wei×gcd(we1,...,wen−1)\sum\limits_{T}\sum\limits_{i=1}^{n-1}w_{e_{i}}\times gcd(w_{e_1},...,w_{e_{n-1}})T∑​i=1∑n−1​wei​​×gcd(we1​​,...,wen−1​​) 很明显的可以用反演,也可以直接套 ϕ∗1=id\phi*1=idϕ∗1=id 那么就可以得出 ∑d=1max(w)ϕ(d)∑Td∣(gcd(we∈T))∑i=1n−1wei\sum\limits_{d=1}^{max(w)}\phi(d)\sum\limits_{T}^{d|(gcd(w_{e\in T}))}\sum\limits_{i=1}^{n-1}w_{e_i}d=1∑max(w)​ϕ(d)T∑d∣(gcd(we∈T​))​i=1∑n−1​wei​​ 后面部分需要用到矩阵树定理,但矩阵树求得是 ∑T∏i=1n−1wei\sum\limits_T\prod\limits_{i=1}^{n-1}w_{e_i}T∑​i=1∏n−1​wei​​,和上面的 ...

矩阵树定理就是把图的生成树个数与矩阵行列式联系起来的一个定理 前置知识矩阵行列式 定义 假设有一个无向图 G=(V,E)G=(V,E)G=(V,E) 有 ppp 个顶点 qqq 条边 对于 GGG 中每一条边,我们任意指定一个方向,这样我们就可以定义 GGG 的关联矩阵 M(G)M(G)M(G), 它是一个 p×qp\times qp×q 的矩阵 Mij={−1vi是ei的起点1vi是ei的终点0otherwiseM_{ij}=\begin{cases}-1&v_i是e_i的起点\\1&v_i是e_i的终点\\0&otherwise\end{cases} Mij​=⎩⎨⎧​−110​vi​是ei​的起点vi​是ei​的终点otherwise​ 然后定义基尔霍夫矩阵 L(G)L(G)L(G), 它是一个 p×pp\times pp×p 的矩阵 Lij={−miji≠j,vi与vj之间有mij条边d(vi)i=jL_{ij}=\begin{cases}-m_{ij}&i\ne j,v_i与v_j之间有m_{ij}条边\\d(v_i)&i=j\end{ ...

矩阵树定理+容斥 题意 给定 n−1n-1n−1 个集合 SSS,第 iii 个集合里包含 mim_imi​ 条边,你需要从这 n−1n-1n−1 个集合里各选一条边,构成一棵树,问一共有多少种方案 题解 很明显题目所求的方案个数就是生成树个数，那么就可以用矩阵树定理来做 但题目又给了限制，即每个集合里只能选一条边,这个用矩阵树定理就没法做了 考虑容斥,令 f(A)f(A)f(A) 表示集合 AAA 中的边能够构成的生成树数量, g(i)g(i)g(i) 表示从集合 SSS 中任意 iii 个不同集合的并集 那么答案就等于 ∑i=0n−1(−1)if(g(n−1−i))\sum\limits_{i=0}^{n-1}(-1)^if(g(n-1-i))i=0∑n−1​(−1)if(g(n−1−i)) 说人话就是 n−1n-1n−1 个集合构成的无向图的生成树数量 −(n−2)- (n-2)−(n−2) 个集合构成的生成树数量 +(n−3)+(n-3)+(n−3) 个集合构成的生成树数量 … 考虑 nnn 比较小,直接搜索就行 代码 #include<iostream>#incl ...

矩阵是什么 定义 由 m×nm\times nm×n 个数按一定的次序排成的 mmm 行 nnn 列的矩形数表称为 m×nm\times nm×n 的矩阵,简称矩阵 (a1 1a1 2⋯a1 n⋮⋮⋱⋮am 1am 2⋯am n)\begin{pmatrix}a_{1~1}&a_{1~2}&\cdots&a_{1~n}\\\vdots&\vdots&\ddots&\vdots\\a_{m~1}&a_{m~2}&\cdots&a_{m~n}\end{pmatrix} ​a1 1​⋮am 1​​a1 2​⋮am 2​​⋯⋱⋯​a1 n​⋮am n​​​ 横的各排称为矩阵的行,竖的各排称为矩阵的列。 ai ja_{i~j}ai j​ 称为矩阵第 iii 行第 jjj 列的元素 表示 矩阵通常用大写字母A,B,C表示,如 A=(a1 1a1 2⋯a1 n⋮⋮⋱⋮am 1am 2⋯am n)A=\begin{pmatrix}a_{1~1}&a_{1~2}&\cdots&a_{1~n}\\\vdots ...