noip模拟48

本文主要是介绍noip模拟48，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

A. Lighthouse

很明显的容斥题，组合式与上上场 \(t2\) 一模一样
注意判环时长度为 \(n\) 的环是合法的

B. Miner

题意实际上是要求偶拉路
对于一个有多个奇数点的联通块，直接 \(dfs\) 是不对的，可能搜索是来的不是一条路径
可以把个数大于 \(2\) 的联通块先强制奇数点两两连边，再跑两个奇数点的偶拉路
直接跑会 \(t\)，可以加入类似当前弧优化，注意每次 \(dfs\) 回溯时也要更新边为当前弧

void dfs(int u){
	for(int i=hd[u];i;){
		hd[u]=edge[i].nxt;
		if(!vis[i>>1]){
			int v=edge[i].to;
			deg[u]--;
			deg[v]--;
			vis[i>>1]=true;
			dfs(v);
			sta1[++tp1]=make_pair(edge[i].val,v);
			i=hd[u];
		}
		else i=edge[i].nxt;
	}
	return ;
}

C. Lyk Love painting

这 \(m\) 幅画居然不能重叠……

首先肯定二分，然后 \(dp\) 验证
设 \(f[i][j]\) 表示第一行选到第 \(i\) 列总共选了 \(j\) 幅画第二行最远选到第几幅画
转移需要双指针预处理第一行，第二行，以及两行从每一列出发最远能到达的距离

D. Revive

先把平方拆开，分为两部分：

对于每条边，其平方计算了经过这条边的路径数次，为 \(siz_u(n-siz_u)\)
对于每两条边，其乘机的二倍计算了同时经过这两条边的路径次数
可以分三类讨论：
\(v\) 在 \(u\) 子树内，为 \(2(n-siz[u]) * val[u] * siz[v] * val[v]\)
\(v\) 在 \(u\) 到根节点路径上，为 \(2siz[u] * val[u] * (n-siz[v]) * val[v]\)
\(v\) 和 \(u\) 的 \(lca\) 不是两点中的任意一个，为 \(2siz[u] * val[u] * siz[v] * val[v]\)

发现和 \(v\) 有关的式子都是 \(siz[v] * val[v]\)，那么用线段树维护这个值即可
由于需要维护到根节点路径的值，可以另开一棵记录每个点到根节点的前缀和，这样转化成每次区间修改单点查询，避免了多次跳链的 \(log\)
子树内权值和可以用树状数组维护以卡常

代码实现

#include<bits/stdc++.h>
using namespace std;
#define in long long
#define int long long
const int maxn=1e5+5;
const int maxm=1e5+5;
const int mod=1e9+7;
const int stan=1e15;
in n,m,fa[maxn],x,siz[maxn],re[maxn],dfn[maxn],hd[maxn],cnt,num;
int ans,w,val[maxn],sum[maxn],sum1[maxn],sumtot,c[maxn];
in read(){
	int x=0,f=1;
	char ch=getchar();
	while(!isdigit(ch)){
		if(ch=='-')f=-1;
		ch=getchar();
	}
	while(isdigit(ch)){
		x=x*10+ch-48;
		ch=getchar();
	}
	return x*f;
}
struct Edge{
	in nxt,to;
}edge[maxm];
void add(in u,in v){
	edge[++cnt].nxt=hd[u];
	edge[cnt].to=v;
	hd[u]=cnt;
	return ;
}
void change1(int x,int w){
	for(;x<=n;x+=x&-x)c[x]=(c[x]+w)%mod;
	return ;
}
int ask3(int x){
	int ans=0;
	for(;x;x-=x&-x)ans=(ans+c[x])%mod;
	return ans;
}
void modadd(int &x,int y){
	x=(x+y)%mod;
	if(x<0)x=(x+mod)%mod;
}
void dfs(in u){
	siz[u]=1;
	for(in i=hd[u];i;i=edge[i].nxt){
		in v=edge[i].to;
		dfs(v);
		siz[u]+=siz[v];
	}
	return ;
}
void dfs1(in u){
	sum[u]=(sum[fa[u]]+siz[u]*val[u]%mod)%mod;
	sum1[u]=(sum1[fa[u]]+val[u])%mod;
//	cout<<"ppp "<<sum1[u]<<endl;
	dfn[u]=++num;
	re[num]=u;
	for(in i=hd[u];i;i=edge[i].nxt){
		in v=edge[i].to;
		dfs1(v);
	}
	return ;
}
struct Seg{
	in l,r;
	int sum,lazy,sum1,lazy1,sum2,lazy2;
}t[maxn*4];
void update(in p){
	t[p].sum=t[p<<1].sum+t[p<<1|1].sum;
	t[p].sum1=t[p<<1].sum1+t[p<<1|1].sum1;
//	if(t[p].sum>stan)t[p].sum%=mod;
//	if(t[p].sum1>stan)t[p].sum1%=mod;
//	t[p].sum2=t[p<<1].sum2+t[p<<1|1].sum2;
	return ;
}
void build(in p,in l,in r){
	t[p].l=l;
	t[p].r=r;
	if(l==r){
		t[p].sum=sum[re[l]];
		t[p].sum1=sum1[re[l]];
//		t[p].sum2=siz[re[l]]*val[re[l]]%mod;
		return ;
	}
	in mid=l+r>>1;
	build(p<<1,l,mid);
	build(p<<1|1,mid+1,r);
	update(p);
	return ;
}
void tospread(in p,int w1,int w2){
	t[p].lazy=t[p].lazy+w1;
	t[p].lazy1=t[p].lazy1+w2;
	
	t[p].sum=t[p].sum+w1;
	t[p].sum1=t[p].sum1+w2;
	
	return ;
}
//void tospread1(in p,int w){
//	t[p].lazy2=t[p].lazy2+w;
//	t[p].sum2=t[p].sum2+w;
//	return ;
//}
void spread(in p){
	tospread(p<<1,t[p].lazy,t[p].lazy1);
	tospread(p<<1|1,t[p].lazy,t[p].lazy1);
	t[p].lazy=t[p].lazy1=0;
	return ;
}
//void spread1(in p){
//	tospread1(p<<1,t[p].lazy2);
//	tospread1(p<<1|1,t[p].lazy2);
//	t[p].lazy2=0;
//	return ;
//}
void change(in p,in l,in r,int w1,int w2){
	if(l>r)return ;
	if(t[p].l>=l&&t[p].r<=r){
		tospread(p,w1,w2);
		return ;
	}
	if(t[p].lazy||t[p].lazy1)spread(p);
//	if(t[p].lazy2)spread1(p);
	in mid=t[p].l+t[p].r>>1;
	if(l<=mid)change(p<<1,l,r,w1,w2);
	if(r>mid)change(p<<1|1,l,r,w1,w2);
	update(p);
	return ;
}
//void change1(in p,in l,in r,int w){
//	if(l>r)return ;
//	if(t[p].l>=l&&t[p].r<=r){
//		tospread1(p,w);
//		return ;
//	}
//	if(t[p].lazy||t[p].lazy1)spread(p);
//	if(t[p].lazy2)spread1(p);
//	in mid=t[p].l+t[p].r>>1;
//	if(l<=mid)change1(p<<1,l,r,w);
//	if(r>mid)change1(p<<1|1,l,r,w);
//	update(p);
//	return ;
//}
int ask(in p,in l,in r){
//	cout<<t[p].l<<" "<<t[p].r<<"   "<<l<<" "<<r<<endl;
	if(l>r)return 0;
	if(t[p].l>=l&&t[p].r<=r)return t[p].sum;
	int mid=t[p].l+t[p].r>>1,ans=0;
	if(t[p].lazy||t[p].lazy1)spread(p);
//	if(t[p].lazy2)spread1(p);
	if(l<=mid)ans=ask(p<<1,l,r);
	if(r>mid)ans=ans+ask(p<<1|1,l,r);
	if(ans>stan)ans%=mod;
	return ans;
}
int ask1(in p,in l,in r){
	if(l>r)return 0;
	if(t[p].l>=l&&t[p].r<=r)return t[p].sum1;
	in mid=t[p].l+t[p].r>>1,ans=0;
	if(t[p].lazy||t[p].lazy1)spread(p);
//	if(t[p].lazy2)spread1(p);
	if(l<=mid)ans=ask1(p<<1,l,r);
	if(r>mid)ans=ans+ask1(p<<1|1,l,r);
	if(ans>stan)ans%=mod;
	return ans;
}
int ask2(in p,in l,in r){
	if(l>r)return 0;
	if(t[p].l>=l&&t[p].r<=r)return t[p].sum2;
	in mid=t[p].l+t[p].r>>1,ans=0;
	if(t[p].lazy||t[p].lazy1)spread(p);
//	if(t[p].lazy2)spread1(p);
	if(l<=mid)ans=ask2(p<<1,l,r);
	if(r>mid)ans=ans+ask2(p<<1|1,l,r);
	if(ans>stan)ans%=mod;
	return ans;
}
int solve(in u,int w,in op){
	int res=0;
	int sumz=0;
	if(siz[u]>1)sumz=ask3(dfn[u]+siz[u]-1)-ask3(dfn[u]);
//	int sumz=ask2(1,dfn[u]+1,dfn[u]+siz[u]-1);
//	cout<<"hhh "<<u<<" "<<sumz<<endl;
//	cout<<ask(1,dfn[u]+1,dfn[u]+siz[u]-1)<<" "<<ask(1,dfn[u],dfn[u])<<endl;
	//cout<<"hhh"<<endl;
	int suml=ask(1,dfn[fa[u]],dfn[fa[u]])%mod;
//	cout<<" "<<ask1(1,dfn[fa[u]],dfn[fa[u]])<<endl;
	modadd(res,ask1(1,dfn[fa[u]],dfn[fa[u]])%mod*n%mod-suml);
//	cout<<res<<endl;
//	cout<<sumtot<<" "<<suml<<" "<<sumz<<endl;
	modadd(res,sumtot-suml-siz[u]*val[u]%mod-sumz);
//	cout<<res<<endl;
	res=2*res*siz[u]%mod*w%mod;
//	cout<<res<<endl;
	modadd(res,2*w*(n-siz[u])%mod*sumz%mod);
//	cout<<"hhh "<<res<<endl;
//	cout<<res<<endl;
	if(op){
		change(1,dfn[u],dfn[u]+siz[u]-1,w*siz[u]%mod,w);
		change1(dfn[u],w*siz[u]%mod);
//		change1(1,dfn[u],dfn[u],w*siz[u]);
		modadd(sumtot,w*siz[u]%mod);
	}
	return res;
}
int po(int a,int b=mod-2){
	int ans=1;
	while(b){
		if(b&1)ans=ans*a%mod;
		a=a*a%mod;
		b>>=1;
	}
	return ans;
}
signed main(){
//	freopen("revive3.in","r",stdin);
//	freopen("shuju.in","r",stdin);
//	freopen("my.out","w",stdout);
	n=read();
	n=read(),m=read();
	for(int i=2;i<=n;i++){
		fa[i]=read();
		val[i]=read();
		add(fa[i],i);
	}
	dfs(1);
	dfs1(1);
	build(1,1,n);
	for(int i=1;i<=n;i++)change1(dfn[i],siz[i]*val[i]%mod);
	for(int i=1;i<=n;i++)modadd(sumtot,val[i]*siz[i]%mod);
	for(int i=2;i<=n;i++){
//		cout<<"id: "<<i<<endl;
//		cout<<solve(i,val[i],0)<<" ";
		ans=(ans+solve(i,val[i],0))%mod;
	}
	ans=ans*po(2)%mod;
//	cout<<ans<<endl;
	for(int i=2;i<=n;i++){
		ans=(ans+val[i]*val[i]%mod*siz[i]%mod*(n-siz[i])%mod)%mod;
	}
	cout<<ans<<endl;
	for(int i=1;i<=m;i++){
		x=read();
		w=read();
		ans=(ans-val[x]*val[x]%mod*siz[x]%mod*(n-siz[x])%mod)%mod;
		ans=(ans+mod)%mod;
		ans=(ans+solve(x,w,1))%mod;
		val[x]+=w;
		val[x]%=mod;
		ans=(ans+val[x]*val[x]%mod*siz[x]%mod*(n-siz[x])%mod)%mod;
		printf("%lld\n",ans);
	}
	return 0;
}

这篇关于noip模拟48的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！

Java教程

noip模拟48

A. Lighthouse

B. Miner

C. Lyk Love painting

D. Revive

前端开发

后端开发

移动端开发

数据库

服务器运维

人工智能

区块链

游戏开发

网站运营

大数据/云计算

软件工程

软件/开发工具使用

资讯