首页 > 其他分享 >Solution Set - 矩阵加速

Solution Set - 矩阵加速

时间：2023-06-02 20:12:16浏览次数：31  
标签：Set return int mid 矩阵 Solution tp son query

A[洛谷P4719]一棵树，点有权，单点修改，求最大权独立集。
B[洛谷P6021]一棵树，点有权，单点修改，求在某棵子树中选出一些点，使得所有叶子与根不连通的最小权值和。
C[洛谷P5024]一棵树，点有权，给定某两个点的选择状况，求最小权覆盖集。

动态DP：（通常在树上）用矩阵刻画DP转移。做树链剖分，然后对每个点记录轻儿子的转移矩阵之积。修改时从一个点向上跳，修改每条轻边的贡献；询问是把1所在重链的矩阵相乘。

ABC都是模板。C要注意撤销修改时的顺序。

点击查看A题代码 
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5,INF=1e9;
int n,m,a[N],f[N][2];
int head[N],nxt[N<<1],ver[N<<1],tot;
void add(int u,int v){ver[++tot]=v;nxt[tot]=head[u];head[u]=tot;}
int fa[N],top[N],L[N],dfn,R[N],siz[N],son[N],id[N];
struct Matrix{
	int a[2][2];
	Matrix (){memset(a,0,sizeof(a));}
	Matrix operator *(const Matrix &b)const{
		Matrix c;
		for(int i=0;i<2;i++)
			for(int j=0;j<2;j++)
				for(int k=0;k<2;k++)
					c.a[i][j]=max(c.a[i][j],a[i][k]+b.a[k][j]);
		return c;
	}
}g[N];
struct SegmentTree{
	Matrix a[N<<2];
	#define ls p<<1
	#define rs p<<1|1
	#define mid (l+r>>1)
	void build(int p,int l,int r){
		if(l==r){a[p]=g[id[l]];return;}
		build(ls,l,mid);
		build(rs,mid+1,r);
		a[p]=a[ls]*a[rs];
	}
	Matrix query(int p,int l,int r,int L,int R){
		if(l>=L&&r<=R)return a[p];
		if(R<=mid)return query(ls,l,mid,L,R);
		if(L>mid)return query(rs,mid+1,r,L,R);
		return query(ls,l,mid,L,R)*query(rs,mid+1,r,L,R);
	}
	void modify(int p,int l,int r,int x){
		if(l==r){a[p]=g[id[l]];return;}
		if(x<=mid)modify(ls,l,mid,x);
		else modify(rs,mid+1,r,x);
		a[p]=a[ls]*a[rs];
	}
	#undef ls
	#undef rs
	#undef mid
}seg;
void dfs(int u){
	f[u][1]=a[u];siz[u]=1;
	for(int i=head[u],v;i;i=nxt[i])
		if((v=ver[i])!=fa[u]){
			fa[v]=u;
			dfs(v);siz[u]+=siz[v];
			if(siz[v]>siz[son[u]])son[u]=v;
			f[u][0]+=max(f[v][0],f[v][1]);
			f[u][1]+=f[v][0];
		}
}
void rdfs(int u,int tp){
	g[u].a[1][0]=a[u];g[u].a[1][1]=-INF;
	L[u]=R[u]=++dfn;R[tp]=dfn;id[dfn]=u;top[u]=tp;
	if(son[u])rdfs(son[u],tp);
	for(int i=head[u],v;i;i=nxt[i])
		if((v=ver[i])!=fa[u]&&v!=son[u]){
			rdfs(v,v);
			g[u].a[0][0]+=max(f[v][0],f[v][1]);
			g[u].a[1][0]+=f[v][0];
		}
	g[u].a[0][1]=g[u].a[0][0];
}
void update(int u,int val){
	g[u].a[1][0]+=val-a[u];a[u]=val;
	while(u){
		Matrix lst=seg.query(1,1,n,L[top[u]],R[top[u]]);
		seg.modify(1,1,n,L[u]);
		Matrix now=seg.query(1,1,n,L[top[u]],R[top[u]]);
		u=fa[top[u]];
		g[u].a[0][0]+=max(now.a[0][0],now.a[1][0])-max(lst.a[0][0],lst.a[1][0]);
		g[u].a[1][0]+=now.a[0][0]-lst.a[0][0];
		g[u].a[0][1]=g[u].a[0][0];
	}
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)scanf("%d",a+i);
	for(int i=1,u,v;i<n;i++){
		scanf("%d%d",&u,&v);
		add(u,v);add(v,u);
	}
	dfs(1);rdfs(1,1);seg.build(1,1,n);
	for(int i=1,u,val;i<=m;i++){
		scanf("%d%d",&u,&val);
		update(u,val);
		Matrix ans=seg.query(1,1,n,1,R[1]);
		printf("%d\n",max(ans.a[0][0],ans.a[1][0]));
	}
	return 0;
}
点击查看B题代码 
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+5,INF=1e9+7;
int n,m;ll a[N],f[N];char op;
int head[N],nxt[N<<1],ver[N<<1],tot;
void add(int u,int v){ver[++tot]=v;nxt[tot]=head[u];head[u]=tot;}
struct Matrix{
	ll a[2][2];
	Matrix (){memset(a,0x3f,sizeof(a));}
	Matrix operator *(const Matrix&b)const{
		Matrix c;
		for(int i=0;i<2;i++)
			for(int j=0;j<2;j++)
				for(int k=0;k<2;k++)
					c.a[i][j]=min(c.a[i][j],a[i][k]+b.a[k][j]);
		return c;
	}
}g[N];
int fa[N],siz[N],top[N],L[N],dfn,R[N],son[N],id[N];
void dfs(int u){
	siz[u]=1;
	for(int i=head[u],v;i;i=nxt[i])
		if((v=ver[i])!=fa[u]){
			fa[v]=u;dfs(v);siz[u]+=siz[v];
			if(siz[v]>siz[son[u]])son[u]=v;
			f[u]+=min(f[v],a[v]);
		}
	if(!nxt[head[u]])f[u]=INF;
}
void rdfs(int u,int tp){
	g[u].a[0][1]=a[u];g[u].a[0][0]=g[u].a[1][1]=0;
	L[u]=++dfn;id[dfn]=u;R[tp]=dfn;top[u]=tp;
	if(son[u])rdfs(son[u],tp);
	else g[u].a[0][0]=INF;
	for(int i=head[u],v;i;i=nxt[i])
		if((v=ver[i])!=fa[u]&&v!=son[u]){
			rdfs(v,v);
			g[u].a[0][0]+=min(f[v],a[v]);
		}
}
struct SegmentTree{
	Matrix a[N<<2];
	#define ls p<<1
	#define rs p<<1|1
	#define mid (l+r>>1)
	void build(int p,int l,int r){
		if(l==r){a[p]=g[id[l]];return;}
		build(ls,l,mid);
		build(rs,mid+1,r);
		a[p]=a[ls]*a[rs];
	}
	Matrix query(int p,int l,int r,int L,int R){
		if(l>=L&&r<=R)return a[p];
		if(R<=mid)return query(ls,l,mid,L,R);
		if(L>mid)return query(rs,mid+1,r,L,R);
		return query(ls,l,mid,L,R)*query(rs,mid+1,r,L,R);
	}
	void modify(int p,int l,int r,int x){
		if(l==r){a[p]=g[id[l]];return;}
		if(x<=mid)modify(ls,l,mid,x);
		else modify(rs,mid+1,r,x);
		a[p]=a[ls]*a[rs];
	}
	#undef ls
	#undef rs
	#undef mid
}seg;
void update(int u,int val){
	g[u].a[0][1]+=val;a[u]+=val;
	while(u){
		Matrix lst=seg.query(1,1,n,L[top[u]],R[top[u]]);
		seg.modify(1,1,n,L[u]);
		Matrix now=seg.query(1,1,n,L[top[u]],R[top[u]]);
		u=fa[top[u]];
		g[u].a[0][0]+=min(now.a[0][0],now.a[0][1])-min(lst.a[0][0],lst.a[0][1]);
	}
}
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++)scanf("%lld",a+i);
	for(int i=1,u,v;i<n;i++){
		scanf("%d%d",&u,&v);
		add(u,v);add(v,u);
	}
	dfs(1);rdfs(1,1);seg.build(1,1,n);
	scanf("%d",&m);
	for(int i=1,u,val;i<=n;i++){
		while(op=getchar(),op!='Q'&&op!='C');
		scanf("%d",&u);
		if(op=='Q'){
			Matrix ans=seg.query(1,1,n,L[u],R[top[u]]);
			printf("%lld\n",min(ans.a[0][0],ans.a[0][1]));
		}
		else{scanf("%d",&val);update(u,val);}
	}
	return 0;
}
点击查看C题代码 
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+5;const ll INF=1e18;
int n,m,p[N];ll f[N][2];char type[5];
int head[N],nxt[N<<1],ver[N<<1],tot;
void add(int u,int v){ver[++tot]=v;nxt[tot]=head[u];head[u]=tot;}
struct Matrix{
	ll a[2][2];
	Matrix (){a[0][0]=a[0][1]=a[1][0]=a[1][1]=INF;}
	Matrix operator *(const Matrix&b)const{
		Matrix c;
		c.a[0][0]=min(a[0][0]+b.a[0][0],a[0][1]+b.a[1][0]);
		c.a[1][0]=min(a[1][0]+b.a[0][0],a[1][1]+b.a[1][0]);
		c.a[0][1]=min(a[0][0]+b.a[0][1],a[0][1]+b.a[1][1]);
		c.a[1][1]=min(a[1][0]+b.a[0][1],a[1][1]+b.a[1][1]);
		return c;
	}
}g[N];
int fa[N],top[N],siz[N],L[N],dfn,R[N],son[N],id[N];
void dfs(int u){
	f[u][1]=p[u];siz[u]=1;
	for(int i=head[u],v;i;i=nxt[i])
		if((v=ver[i])!=fa[u]){
			fa[v]=u;dfs(v);siz[u]+=siz[v];
			if(siz[v]>siz[son[u]])son[u]=v;
			f[u][0]+=f[v][1];
			f[u][1]+=min(f[v][0],f[v][1]);
		}
}
void rdfs(int u,int tp){
	g[u].a[0][0]=p[u];g[u].a[1][0]=0;
	L[u]=++dfn;id[dfn]=u;top[u]=tp;R[tp]=dfn;
	if(son[u])rdfs(son[u],tp);
	for(int i=head[u],v;i;i=nxt[i])
		if((v=ver[i])!=fa[u]&&v!=son[u]){
			rdfs(v,v);
			g[u].a[0][0]+=min(f[v][0],f[v][1]);
			g[u].a[1][0]+=f[v][1];
		}
	g[u].a[0][1]=g[u].a[0][0];
}
struct SegmentTree{
	Matrix a[N<<2];
	#define mid (l+r>>1)
	void build(int p,int l,int r){
		if(l==r){a[p]=g[id[l]];return;}
		build(p<<1,l,mid);
		build(p<<1|1,mid+1,r);
		a[p]=a[p<<1]*a[p<<1|1];
	}
	void modify(int p,int l,int r,int x){
		if(l==r){a[p]=g[id[l]];return;}
		if(x<=mid)modify(p<<1,l,mid,x);
		else modify(p<<1|1,mid+1,r,x);
		a[p]=a[p<<1]*a[p<<1|1];
	}
	Matrix query(int p,int l,int r,int L,int R){
		if(l>=L&&r<=R)return a[p];
		if(R<=mid)return query(p<<1,l,mid,L,R);
		if(L>mid)return query(p<<1|1,mid+1,r,L,R);
		return query(p<<1,l,mid,L,R)*query(p<<1|1,mid+1,r,L,R);
	}
	#undef mid
}seg;
void update(int u,int op,Matrix c){
	if(op==1)g[u].a[1][0]=INF;
	else if(op==2)g[u]=c;
	else g[u].a[0][0]=g[u].a[0][1]=INF;
	while(u){
		Matrix lst=seg.query(1,1,n,L[top[u]],R[top[u]]);
		seg.modify(1,1,n,L[u]);
		Matrix now=seg.query(1,1,n,L[top[u]],R[top[u]]);
		u=fa[top[u]];
		g[u].a[0][0]+=min(now.a[0][0],now.a[1][0])-min(lst.a[0][0],lst.a[1][0]);
		g[u].a[1][0]+=now.a[0][0]-lst.a[0][0];g[u].a[0][1]=g[u].a[0][0];
	}
}
int main(){
//	freopen("defense.in","r",stdin);
//	freopen("defense.out","w",stdout);
	scanf("%d%d",&n,&m);scanf("%s",type);
	for(int i=1;i<=n;i++)scanf("%d",p+i);
	for(int i=1,u,v;i<n;i++){
		scanf("%d%d",&u,&v);
		add(u,v);add(v,u);
	}
	dfs(1);rdfs(1,1);seg.build(1,1,n);
	for(int i=1,a,x,b,y;i<=m;i++){
		scanf("%d%d%d%d",&a,&x,&b,&y);
		Matrix tmpa=g[a];update(a,x,tmpa);
		Matrix tmpb=g[b];update(b,y,tmpb);
		Matrix ans=seg.query(1,1,n,1,R[1]);
		ll res=min(ans.a[0][0],ans.a[1][0]);
		printf("%lld\n",res>1e15?-1:res);
		update(b,2,tmpb);update(a,2,tmpa);
	}
	return 0;
}

标签：Set,return,int,mid,矩阵,Solution,tp,son,query
From： https://www.cnblogs.com/by-chance/p/17452810.html

相关文章

  • C# Newtonsoft.Json JsonSerializerSettings配置序列化操作
    @@newtonsoft.json序列化  JsonSerializerSettings常用配置整理忽略某些属性默认值的处理空值的处理支持非公共成员日期处理（DateFormatHandling）自定义序列化的字段名称动态决定属性是否序列化枚举值的自定义格式化问题自定义类型转换全局序列化设置指定序列化时......
  • 动态规划基础之矩阵取数问题 51nod1083
    题目地址：https://www.51nod.com/onlineJudge/questionCode.html#!problemId=1083题目：1083 矩阵取数问题基准时间限制：1 秒空间限制：131072 KB分值: 5 难度：1级算法题例如：3*3的方格。133213221......
  • ACM暑假训练 中石油oj 3737: 礼物（矩阵快速幂）
    3737:礼物时间限制:5Sec  内存限制:512MB提交:46  解决:12[提交][状态][讨论版]题目描述热情好客的小猴请森林中的朋友们吃饭，他的朋友被编号为1∼N，每个到来的朋友都会带给他一些礼物：香蕉。其中，第一个朋友会带给他1个香蕉，之后，每一个朋友到来以后，都会带给他之前所有......
  • 最大子矩阵和问题 动态规划 51nod1051
    1051 最大子矩阵和基准时间限制：2 秒空间限制：131072 KB分值: 40 难度：4级算法题例如：3*3的矩阵：-13-12-13-312和最大的子矩阵是：3-1-1312Input......
  • lucene底层数据结构——底层filter bitset原理，时间序列数据压缩将同一时间数据压缩为
    如何联合索引查询？所以给定查询过滤条件age=18的过程就是先从termindex找到18在termdictionary的大概位置，然后再从termdictionary里精确地找到18这个term，然后得到一个postinglist或者一个指向postinglist位置的指针。然后再查询gender=女的过程也是类似的。最后得出age=18......
  • frame framset 的页面显示不了 空白
    frameframset的页面显示不了空白 例如php文件输出这样，<!DOCTYPEhtmlPUBLIC"-//W3C//DTDXHTML1.0Transitional//EN""http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"><htmlxmlns="http://www.w3.org/1999/xhtml"><he......
  • URI is not registered (Settings | Languages & Frameworks | Schemas and DTDs)
    问题描述：如下图，在.xml配置文件中配置报错：URIisnotregistered(Settings|Languages&Frameworks|SchemasandDTDs) 解决办法：工具栏：file-->settings:找到SchemasandDTDs中加入对应的地址即可 ......
  • unordered_map、unordered_set使用
    unordered_map头文件#include<iostream>#include<unordered_map>usingnamespacestd;增删查改unordered_map底层实现为哈希表，增删效率与查找效率都是O(1)增加元素emplace(key,value)insert(pair<T,T>p)数组修改法//unordered_map三种增加元素的方式// insert(......
  • 好用的bitset——暴力的好帮手
    会持续更新的。bitsetC++的bitset在bitset头文件中，它是一种类似数组的结构，它的每一个元素只能是０或１，每个元素仅用１bit空间。bitset的原理大概是将很多数压成一个，从而节省空间和时间,一般来说bitset会让你的算法复杂度/32构造bitset一般有下五种：#include<bits/stdc++.......
  • 一图归纳三大种类矩阵范数：诱导范数，元素范数，Schatten范数，涵盖谱范数，2范数
    转载自：https://blog.csdn.net/qq_27261889/article/details/87902480......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99