招商网站大全新网站大量收录好不好

招商网站大全,新网站大量收录好不好,焦作黄河交通学院,中国的科技成就歉#xff1a;作者是在打代码之前就完成了文字部分#xff0c;转移方程的锅代码中修了#xff0c;文字部分没修#xff0c;在此致歉。【模板】动态 DP 加强版 题解该篇为题解。总文章#xff08;动态 dp 学习笔记#xff09;同步发表于 cnblogs。总文章#xff08;动态 …歉作者是在打代码之前就完成了文字部分转移方程的锅代码中修了文字部分没修在此致歉。【模板】动态 DP 加强版 题解该篇为题解。总文章动态 dp 学习笔记同步发表于 cnblogs。总文章动态 dp 学习笔记同步发表于 luogu。前置知识简单 dp树链剖分矩阵乘法和广义矩阵乘法P4719 【模板】动态 DP本文着重讲下修改的具体过程以及代码实现蒟蒻花了好长时间才明白。鏖战一天终于通过了板子题啊啊啊不带修简单树上 dp。考虑不带修改就是一个平凡的树上最大权独立集问题简单树上 dp 即可求解。设表示以为根子树中选不选所得到的树上最大权独立集的大小。转移是容易的带修了但是丧心病狂的出题人加上了修改点权考虑动态维护这个问题。发现树剖有一个性质跳重链至多次。设为的重儿子。为点所在重链的链头节点。为的父亲节点。然后修正我们的 dp 为表示以为根子树选不选的答案。表示以为根子树不选以重儿子为根子树中包括重儿子任何一个点时选不选的答案。设为点的儿子节点那么有转移转移改为使用广义矩阵乘法直接定义广义矩阵乘法。本文并不在广义矩阵乘这里深入展开具体可参考其他博客。作者还没完全搞懂。具体可参考 https://www.cnblogs.com/qkhm/p/19055513/ddp。当然如果你不会证明你也可以直接设三个矩阵然后暴力手算验证该新定义的矩阵是否满足结合律也是可行的。发现这个新的矩乘还是满足结合律不满足交换律单位矩阵是主对角线上是其他全都是。本题单位矩阵为设原树上点的答案矩阵为那么我们需要求出每个点的转移矩阵设为。定义完所有所需矩阵之后转移可以写为设写出完整矩阵转移的柿子为由待定系数法得出点的转移矩阵为那么转移可以写成那么一条重链上某一点的答案矩阵值可以用矩阵连乘计算链尾节点没有所以。手算发现乘之前的那个矩阵提出第一列构成一个矩阵后恰好是乘之后的答案矩阵。所以我们不用真正乘矩阵直接提取第一列即可。初始化那么我们就可以在线段树上维护区间矩阵连乘积了。注意矩阵乘法不满足交换律我的做法在合并区间时需要左右。具体实现时比较复杂。先两次 dfs 进行树链剖分。我们需要额外记录一个表示一条以为链首的那条重链的链底。再来一次 dfs 跑一遍树上 dp 初始化和数组。在 dfn 序上建线段树每个叶子节点记录它代表的树上点的转移矩阵。对于非叶子节点记录的矩阵为左儿子矩阵乘右儿子矩阵。查询答案时我们需要查询以根为链首的矩阵值可以通过线段树区间查询该重链的矩阵乘积得到。解决修改问题着重讲下修改的具体过程以及代码实现蒟蒻花了好长时间才明白。注意下文对的修改改的是矩阵里的值而不是数组的值。设我们要将树上点的权值改为。设原先点权为。首先开一个全局临时矩阵令。然后修改矩阵中的值也就是矩阵的第二行第一列那个位置的值。容易发现点对的贡献由原先的变为变化量为所以我们在矩阵中更改即可。然后我们考察的实际意义为一个点轻儿子的贡献。考虑有几个点的值需要更新。发现是点和跳链过程中每条链链顶的父亲其他点均不需要修改。由于每次查询根链最多跳条重链所以对应的转移矩阵只会有个得到修改加上线段树的复杂度就是的。复杂度得到证明。然后现在节点为开始跳链操作。先线段树区间查询所在重链的乘积为矩阵的第一列即为修改之前链顶的答案矩阵的值值。然后线段树单点修改点的转移矩阵将其变为。再线段树区间查询所在重链的乘积为矩阵的第一列即为修改之后链顶的答案矩阵的值值。设然后令意为令跳到所在重链链首的父亲。再次线段树单点查询出点所对应的转移矩阵令。考察对的贡献为。那么矩阵里的所有变化量即为。将和加上变化量即可。考察对的贡献为。那么矩阵里的所有变化量即为。将加上变化量即可。矩阵中仍为。重复执行上述过程直至时结束。即可完成修改。实现细节矩阵可以用的二维数组存储。矩阵乘可以循环展开。线段树上非叶子节点存储的矩阵为左儿子矩阵右儿子矩阵。Code#includebits/stdc.h#define int long long#define lp (p1)#define rp ((p1)|1)using namespace std;inline int read(){int x0,cgetchar(),f0;for(;c9||c0;fc-,cgetchar());for(;c0c9;cgetchar())x(x1)(x3)(c^48);return f?-x:x;}inline void write(int x){if(x0) x-x,putchar(-);if(x9) write(x/10);putchar(x%100);}#ifndef ONLINE_JUDGE#define ONLINE_JUDGE#endifconst int N1e65;int n,m;int a[N];int fa[N];int tail[N];int siz[N];int son[N];int dfn[N];int tod[N];int top[N];int id[N];int tot;vectorint E[N];const int inf1e12;struct Martix{int a[2][2]{};}I,t[N2];Martix nw;int f[N][2],g[N][2];int tid[N2];inline int max(int x,int y) { return xy?x:y; }Martix operator*(const Martix x,const Martix y){Martix ans;ans.a[0][0]max(x.a[0][0]y.a[0][0],x.a[0][1]y.a[1][0]);ans.a[0][1]max(x.a[0][0]y.a[0][1],x.a[0][1]y.a[1][1]);ans.a[1][0]max(x.a[1][0]y.a[0][0],x.a[1][1]y.a[1][0]);ans.a[1][1]max(x.a[1][0]y.a[0][1],x.a[1][1]y.a[1][1]);return ans;}Martix ksm(Martix x,int p){Martix ansI;while(p){if(p1) ansans*x;xx*x;p1;}return ans;}void dfs1(int p,int f){fa[p]f;siz[p]1;for(int to:E[p]){if(tof) continue;dfs1(to,p);siz[p]siz[to];if(siz[to]siz[son[p]]) son[p]to;}}void dfs2(int p,int tp){dfn[p]tot;id[tot]p;top[p]tp;tail[tp]p;if(son[p]) dfs2(son[p],tp);for(int to:E[p])if(!dfn[to]) dfs2(to,to);}void dfs3(int p,int fa){g[p][1]a[p];for(int to:E[p]){if(tofa) continue;dfs3(to,p);if(toson[p]) continue;g[p][1]f[to][0];g[p][0]max(f[to][0],f[to][1]);}f[p][0]g[p][0]max(f[son[p]][0],f[son[p]][1]);f[p][1]g[p][1]f[son[p]][0];}void pushup(int p){t[p]t[lp]*t[rp];}void build(int l,int r,int p){if(lr){tid[id[l]]p;t[p].a[0][0]t[p].a[0][1]g[id[l]][0];t[p].a[1][0]g[id[l]][1];t[p].a[1][1]-inf;return;}int mid(lr)1;build(l,mid,lp);build(mid1,r,rp);pushup(p);}Martix query(int l,int r,int sl,int sr,int p){if(p0) exit(0);if(sllrsr) return t[p];int mid(lr)1;Martix qlI,qrI;if(slmid) qlquery(l,mid,sl,sr,lp);if(srmid) qrquery(mid1,r,sl,sr,rp);return ql*qr;}void change(int l,int r,int x,int p,const Martix nw){if(lr){t[p]nw;return;}int mid(lr)1;if(xmid) change(l,mid,x,lp,nw);else change(mid1,r,x,rp,nw);pushup(p);}void change(int x,int y){nwt[tid[x]];nw.a[1][0]y-a[x];