noip模拟46
2021/8/24 6:35:34
本文主要是介绍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的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！
- 2024-05-0601-电商商品中心解密：仅凭SKU真的足够吗？
- 2024-05-01为什么公共事业机构会偏爱 TiDB ：TiDB 数据库在某省妇幼健康管理系统的应用
- 2024-04-26敏捷开发：想要快速交付就必须舍弃产品质量？
- 2024-04-26静态代码分析的这些好处，我竟然都不知道？
- 2024-04-26你在测试金字塔的哪一层？（下）
- 2024-04-26快刀斩乱麻，DevOps让代码评审也自动起来
- 2024-04-262024年最好用的10款ER图神器！
- 2024-04-2203-为啥大模型LLM还没能完全替代你？
- 2024-04-2101-大语言模型发展
- 2024-04-17基于SpringWeb MultipartFile文件上传、下载功能
