noip模拟46

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

A. 数数

排好序从两头贪心即可

B. 数树

首先很容易想到容斥
如果选择的边集的相关点集有点的度数大于 \(1\) 是不合法的
也就是说一定形成若干条长度不一的链
要给这些链上的点安排排列中的数，方案数其实就是 \((n-k)!\)
因为一条链开头的值确定了整条链的值就确定了

发现暴力算是 \(2^n\)，考虑选择边集数量一定时贡献是否可以一起算
树形背包即可，算出以 \(1\) 为根的子树内选 \(k\) 条边的方案数
由于入度出度不超过 \(1\) 的限制，\(dp\) 加两维 \(0/1\) 表示有没有出/入边

代码实现

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=5005;
const int maxm=10005;
const int mod=998244353;
int n,hd[maxn],cnt,f[maxn][maxn][2][2],ans,fa[maxn],x,y,frac[maxn],siz[maxn],g[maxn][2][2];
int 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{
	int nxt,to,val;
}edge[maxm];
void add(int u,int v,int w){
	edge[++cnt].nxt=hd[u];
	edge[cnt].to=v;
	edge[cnt].val=w;
	hd[u]=cnt;
	return ;
}
void dfs(int u){
	siz[u]=1;
	f[u][0][0][0]=1;
	for(int i=hd[u];i;i=edge[i].nxt){
		int v=edge[i].to;
		if(v==fa[u])continue;
		fa[v]=u;
		dfs(v);
//		memset(g,0,sizeof g);
		for(int j=siz[u];j>=0;j--){
			for(int k=siz[v];k>=0;k--){
				int sum=(f[v][k][0][0]+f[v][k][0][1]+f[v][k][1][0]+f[v][k][1][1])%mod;
				for(int l=0;l<2;l++){
					for(int r=0;r<2;r++){
						g[j+k][l][r]=(g[j+k][l][r]+f[u][j][l][r]*sum%mod)%mod;
					}
				}
				if(edge[i].val){
					g[j+k+1][1][0]=(g[j+k+1][1][0]+f[u][j][0][0]*(f[v][k][0][0]+f[v][k][1][0])%mod)%mod;
					g[j+k+1][1][1]=(g[j+k+1][1][1]+f[u][j][0][1]*(f[v][k][0][0]+f[v][k][1][0])%mod)%mod;
				}
				else{
					g[j+k+1][0][1]=(g[j+k+1][0][1]+f[u][j][0][0]*(f[v][k][0][0]+f[v][k][0][1])%mod)%mod;
					g[j+k+1][1][1]=(g[j+k+1][1][1]+f[u][j][1][0]*(f[v][k][0][0]+f[v][k][0][1])%mod)%mod;
				}
			}
		}
		siz[u]+=siz[v];
		for(int j=0;j<=siz[u];j++){
			for(int l=0;l<2;l++){
				for(int r=0;r<2;r++){
					f[u][j][l][r]=g[j][l][r];
					g[j][l][r]=0;
				}
			}
		}
	}
	return ;
}
signed main(){
	n=read();
	for(int i=1;i<=n-1;i++){
		x=read();
		y=read();
		add(x,y,0);
		add(y,x,1);
	}
	dfs(1);
	frac[0]=1;
	for(int i=1;i<=n;i++)frac[i]=frac[i-1]*i%mod;
	int op=1;
	for(int i=0;i<=n-1;i++){
		int sum=0;
		for(int j=0;j<=1;j++){
			for(int k=0;k<=1;k++){
//				cout<<f[1][i][j][k]<<" ";
				sum=(sum+f[1][i][j][k])%mod;
			}
		}
//		cout<<endl;
//		cout<<sum<<endl;
		ans=(ans+op*sum*frac[n-i]%mod)%mod;
		ans=(ans+mod)%mod;
		op=-op;
	}
	cout<<ans;
	return 0;
}

C. 鼠树

发现单个白点的权值由其归属点的累加可以得出，子树和操作是子树内黑点总和以及一部分白点由其归属点得出
所以只需要维护黑点信息即可
记录每个黑点的权值，管辖点的个数，以及二者的乘积
当加入一个黑点的时候，其管辖点大小由子树内大小之和推出，权值设为归属点权值，并相应地更改归属点大小
当删除一个黑点的时候，由于要保留贡献，所以直接对这棵子树做区间加，并做一次 \(4\) 操作把子树内其他黑点多算的部分减掉
最后是动态维护归属点的问题：可以树剖并在每条重链上开 \(set\) 维护黑点深度，查询时在重链上二分即可
整个算法时间复杂度 \(nlogn\)

代码实现

#include<bits/stdc++.h>
using namespace std;
#define int unsigned int
const int maxn=3e5+5;
const int maxm=3e5+5;
int n,m,fa[maxn],hd[maxn],cnt,son[maxn],siz[maxn],id[maxn],re[maxn],tp[maxn],tot,x,y,w,op,dep[maxn],c[maxn],c1[maxn];
bool col[maxn];
set<int>s[maxn];
int 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{
	int nxt,to;
}edge[maxm];
void add_edge(int u,int v){
	edge[++cnt].nxt=hd[u];
	edge[cnt].to=v;
	hd[u]=cnt;
	return ;
}
void dfs(int u){
	siz[u]=1;
	for(int i=hd[u];i;i=edge[i].nxt){
		int v=edge[i].to;
		if(v==fa[u])continue;
		dep[v]=dep[u]+1;
		fa[v]=u;
		dfs(v);
		siz[u]+=siz[v];
		if(siz[v]>siz[son[u]])son[u]=v;
	}
	return ;
}
void dfs1(int u,int top){
	tp[u]=top;
	id[u]=++tot;
	re[tot]=u;
	if(son[u])dfs1(son[u],top);
	for(int i=hd[u];i;i=edge[i].nxt){
		int v=edge[i].to;
		if(v==son[u]||v==fa[u])continue;
		dfs1(v,v);
	}
	return ;
}
void add(int x,int w){
	for(;x<=n;x+=x&-x)c[x]+=w;
}
void add1(int x,int w){
	for(;x<=n;x+=x&-x)c1[x]+=w;
}
int ask(int x){
	int ans=0;
	for(;x;x-=x&-x)ans+=c[x];
	return ans;
}
int ask1(int x){
	int ans=0;
	for(;x;x-=x&-x)ans+=c1[x];
	return ans;
}
void change(int l,int r,int w){
	add(l,w);
	add(r+1,-w);
	add1(l,w*(1-l));
	add1(r+1,w*(l-1));
	add1(r+1,w*(r-l+1));
	return ;
}
int query(int l,int r){
	return ask(r)*r+ask1(r)-ask(l-1)*(l-1)-ask1(l-1);
}
int get_t(int x){
	while(1){
		if(!s[tp[x]].empty()){
			if(*s[tp[x]].begin()<=dep[x]){
				set<int>::iterator it=s[tp[x]].upper_bound(dep[x]);
				it--;
				return re[id[x]-(dep[x]-(*it))];
			}
		}
		x=fa[tp[x]];
	}
	return 0;
}
struct seg{
	int l,r,siz,val,sum,lazy;
}t[maxn*4];
void build(int p,int l,int r){
	t[p].l=l;
	t[p].r=r;
	if(l==r)return ;
	int mid=l+r>>1;
	build(p<<1,l,mid);
	build(p<<1|1,mid+1,r);
	return ;
}
void update(int p){
	t[p].siz=t[p<<1].siz+t[p<<1|1].siz;
	t[p].val=t[p<<1].val+t[p<<1|1].val;
	t[p].sum=t[p<<1].sum+t[p<<1|1].sum;
	return ;
}
void dospread(int p,int w){
	t[p].val+=w;
	t[p].sum+=w*t[p].siz;
	t[p].lazy+=w;
	return ;
}
void spread(int p){
	dospread(p<<1,t[p].lazy);
	dospread(p<<1|1,t[p].lazy);
	t[p].lazy=0;
	return ;
}
void change_val(int p,int l,int r,int w){
	if(l>r)return ;
	if(t[p].l>=l&&t[p].r<=r){
		dospread(p,w);
		return ;
	}
	if(t[p].lazy)spread(p);
	int mid=t[p].l+t[p].r>>1;
	if(l<=mid)change_val(p<<1,l,r,w);
	if(r>mid)change_val(p<<1|1,l,r,w);
	update(p);
	return ;
}
void change_siz(int p,int pos,int w){
	if(t[p].l==t[p].r&&t[p].l==pos){
		t[p].siz+=w;
		t[p].sum+=w*t[p].val;
		return ;
	}
	if(t[p].lazy)spread(p);
	int mid=t[p].l+t[p].r>>1;
	if(pos<=mid)change_siz(p<<1,pos,w);
	else change_siz(p<<1|1,pos,w);
	update(p);
	return ;
}
int ask_val(int p,int pos){
	if(t[p].l==t[p].r&&t[p].l==pos){
		return t[p].val;
	}
	if(t[p].lazy)spread(p);
	int mid=t[p].l+t[p].r>>1;
	if(pos<=mid)return ask_val(p<<1,pos);
	return ask_val(p<<1|1,pos);
}
int ask_siz(int p,int l,int r){
	if(l>r)return 0;
	if(t[p].l>=l&&t[p].r<=r)return t[p].siz;
	if(t[p].lazy)spread(p);
	int mid=t[p].l+t[p].r>>1,ans=0;
	if(l<=mid)ans=ask_siz(p<<1,l,r);
	if(r>mid)ans+=ask_siz(p<<1|1,l,r);
	return ans;
}
int ask_sum(int p,int l,int r){
	if(l>r)return 0;
	if(t[p].l>=l&&t[p].r<=r)return t[p].sum;
	if(t[p].lazy)spread(p);
	int mid=t[p].l+t[p].r>>1,ans=0;
	if(l<=mid)ans=ask_sum(p<<1,l,r);
	if(r>mid)ans+=ask_sum(p<<1|1,l,r);
	return ans;
}
void cover(int p,int pos,int w){
	if(t[p].l==t[p].r&&t[p].l==pos){
		t[p].val=w;
		t[p].sum=w*t[p].siz;
		return ;
	}
	if(t[p].lazy)spread(p);
	int mid=t[p].l+t[p].r>>1;
	if(pos<=mid)cover(p<<1,pos,w);
	else cover(p<<1|1,pos,w);
	update(p);
	return ;
}
void rev(int x){
	if(col[x]){
		col[x]=false;
		int cnt=siz[x]-ask_siz(1,id[x]+1,id[x]+siz[x]-1);
		int y=get_t(fa[x]);
		s[tp[x]].erase(dep[x]);
		int val1=ask_val(1,id[x]);
		int val2=ask_val(1,id[y]);
		change_siz(1,id[x],-cnt);
		cover(1,id[x],0);
		change_siz(1,id[y],cnt);
		change(id[x],id[x]+siz[x]-1,val1-val2);
		change_val(1,id[x],id[x]+siz[x]-1,val2-val1);
	}
	else{
		col[x]=true;
		int cnt=siz[x]-ask_siz(1,id[x]+1,id[x]+siz[x]-1);
		int y=get_t(x);
		s[tp[x]].insert(dep[x]);
		int val2=ask_val(1,id[y]);
		change_siz(1,id[x],cnt);
		change_siz(1,id[y],-cnt);
		cover(1,id[x],val2);
	}
	return ;
}
signed main(){
	n=read();
	m=read();
	for(int i=2;i<=n;i++){
		fa[i]=read();
		add_edge(fa[i],i);
	}
	dep[1]=1;
	dfs(1);
	dfs1(1,1);
	build(1,1,n);
	col[1]=true;
	change_siz(1,id[1],siz[1]);
	s[1].insert(1);
	while(m--){
		op=read(),x=read();
		if(op==1){
			printf("%u\n",ask_val(1,id[get_t(x)])+query(id[x],id[x]));
		}
		if(op==2){
			w=read();
			change_val(1,id[x],id[x],w);
		}
		if(op==3){
			int ans=ask_val(1,id[get_t(x)])*(siz[x]-ask_siz(1,id[x]+1,id[x]+siz[x]-1));
			ans+=query(id[x],id[x]+siz[x]-1);
			ans+=ask_sum(1,id[x]+1,id[x]+siz[x]-1);
			printf("%u\n",ans);
		}
		if(op==4){
			w=read();
			change_val(1,id[x],id[x]+siz[x]-1,w);
		}
		if(op==5||op==6){
			rev(x);
		}
	}
	return 0;
}

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

Java教程

noip模拟46

A. 数数

B. 数树

C. 鼠树

前端开发

后端开发

移动端开发

数据库

服务器运维

人工智能

区块链

游戏开发

网站运营

大数据/云计算

软件工程

软件/开发工具使用

资讯