多校A层冲刺NOIP2024模拟赛26
\(T1\) A. 随机游走 \(100pts/100pts\)
-
在树上做临项交换即可。
点击查看代码
struct node { ll nxt,to,w; }e[500010]; ll head[500010],v[500010],siz[500010],sum[500010],cnt=0,ans=0,tim=0; struct quality { ll sumt,siz,to,w; }; vector<quality>E[500010]; bool cmp(quality a,quality b) { return a.sumt*b.siz<b.sumt*a.siz; } void add(ll u,ll v,ll w) { cnt++; e[cnt].nxt=head[u]; e[cnt].to=v; e[cnt].w=w; head[u]=cnt; } void dfs1(ll x) { siz[x]=v[x]; for(ll i=head[x];i!=0;i=e[i].nxt) { dfs1(e[i].to); siz[x]+=siz[e[i].to]; sum[x]+=sum[e[i].to]+e[i].w; E[x].push_back((quality){e[i].w+sum[e[i].to],siz[e[i].to],e[i].to,e[i].w}); } sort(E[x].begin(),E[x].end(),cmp); } void dfs2(ll x) { for(ll i=0;i<E[x].size();i++) { tim+=E[x][i].w; ans+=tim*v[E[x][i].to]; dfs2(E[x][i].to); } } int main() { freopen("walk.in","r",stdin); freopen("walk.out","w",stdout); ll n,u,w,i; scanf("%lld",&n); for(i=2;i<=n;i++) { scanf("%lld%lld",&u,&w); add(u,i,w); } for(i=1;i<=n;i++) { cin>>v[i]; } dfs1(1); dfs2(1); printf("%lld\n",ans); return 0; }
\(T2\) B. 分发奖励 \(68pts/68pts\)
-
部分分
- \(68pts\)
-
先通过 \(DFS\) 序将树上问题转化为序列问题，然后线段树分治套一个支持区间推平的数据结构即可。
-
赛时犯唐直接写了 \(O(\log n)\) 棵珂朵莉树暴力复制父亲节点信息，且还在好奇为什么改成线段树后 \(n \le 3000\) 的数据点都跑不过去。
点击查看代码
struct node { int nxt,to; }e[500010]; int head[500010],dfn[500010],out[500010],pos[500010],ans[500010],tot=0,cnt=0; pair<int,int>val,val1,val2; void add(int u,int v) { cnt++; e[cnt].nxt=head[u]; e[cnt].to=v; head[u]=cnt; } void dfs(int x) { tot++; dfn[x]=tot; pos[tot]=x; for(int i=head[x];i!=0;i=e[i].nxt) { dfs(e[i].to); } out[x]=tot; } struct ODT { struct node { int l,r; mutable int col; bool operator < (const node &another) const { return l<another.l; } }; int ans; set<node>s; void init(int n) { ans=0; s.insert((node){1,n,0}); } set<node>::iterator split(int pos) { set<node>::iterator it=s.lower_bound((node){pos,0,0}); if(it!=s.end()&&it->l==pos) { return it; } it--; if(it->r<pos) { return s.end(); } int l=it->l,r=it->r,col=it->col; s.erase(it); s.insert((node){l,pos-1,col}); return s.insert((node){pos,r,col}).first; } void assign(int l,int r,int col) { set<node>::iterator itr=split(r+1),itl=split(l); for(set<node>::iterator it=itl;it!=itr;it++) { ans-=(it->col)*(it->r-it->l+1); } ans+=r-l+1; s.erase(itl,itr); s.insert((node){l,r,col}); } }O[25]; struct SMT { struct SegmentTree { vector<pair<int,int> >info; }tree[2000010]; #define lson(rt) (rt<<1) #define rson(rt) (rt<<1|1) void update1(int rt,int l,int r,int x,int y) { if(x<=l&&r<=y) { tree[rt].info.push_back(val); return; } int mid=(l+r)/2; if(x<=mid) { update1(lson(rt),l,mid,x,y); } if(y>mid) { update1(rson(rt),mid+1,r,x,y); } } void update2(int rt,int l,int r,int x,int y) { if(x<=l&&r<=y) { tree[rt].info.push_back(val1); tree[rt].info.push_back(val2); return; } int mid=(l+r)/2; if(x<=mid) { update2(lson(rt),l,mid,x,y); } if(y>mid) { update2(rson(rt),mid+1,r,x,y); } } void solve(int rt,int l,int r,int dep) { for(int i=0;i<tree[rt].info.size();i++) { O[dep].assign(tree[rt].info[i].first,tree[rt].info[i].second,1); } if(l==r) { ans[pos[l]]=max(O[dep].ans-1,0); return; } else { int mid=(l+r)/2; O[dep+1]=O[dep]; solve(lson(rt),l,mid,dep+1); O[dep+1]=O[dep]; solve(rson(rt),mid+1,r,dep+1); } } }T; int main() { freopen("reward.in","r",stdin); freopen("reward.out","w",stdout); int n,m,u,a,b,i; scanf("%d%d",&n,&m); for(i=2;i<=n;i++) { scanf("%d",&u); add(u,i); } dfs(1); for(i=1;i<=m;i++) { scanf("%d%d",&a,&b); if(a==b) { val=make_pair(dfn[a],out[a]); T.update1(1,1,n,dfn[a],out[a]); } else { val1=make_pair(dfn[a],out[a]); val2=make_pair(dfn[b],out[b]); T.update2(1,1,n,dfn[a],out[a]); T.update2(1,1,n,dfn[b],out[b]); } } O[1].init(n); T.solve(1,1,n,1); for(i=1;i<=n;i++) { printf("%d ",ans[i]); } return 0; }
-
- \(68pts\)
-
正解
- 转化为序列问题再套线段树分治是不必要的，因为完全可以在原树上再 \(DFS\) 一遍得到相同结果。
- 可撤销数据结构可以用可持久化平衡树实现珂朵莉树或主席树或线段树维护最小值及最小值出现次数（可以证明最小值不会 \(<0\) ）。
点击查看代码
struct node { int nxt,to; }e[500010]; int head[500010],dfn[500010],out[500010],ans[500010],tot=0,cnt=0,n; vector<int>q[500010]; void add(int u,int v) { cnt++; e[cnt].nxt=head[u]; e[cnt].to=v; head[u]=cnt; } void dfs(int x) { tot++; dfn[x]=tot; for(int i=head[x];i!=0;i=e[i].nxt) { dfs(e[i].to); } out[x]=tot; } struct PDS_SMT { int root[500010],rt_sum; struct SegmentTree { int ls,rs,lazy,sum; }tree[500010<<7]; #define lson(rt) (tree[rt].ls) #define rson(rt) (tree[rt].rs) int build_rt() { rt_sum++; lson(rt_sum)=rson(rt_sum)=tree[rt_sum].lazy=tree[rt_sum].sum=0; return rt_sum; } void pushup(int rt) { tree[rt].sum=tree[lson(rt)].sum+tree[rson(rt)].sum; } void update(int pre,int &rt,int l,int r,int x,int y) { rt=build_rt(); tree[rt]=tree[pre]; if(tree[rt].lazy==1||(x<=l&&r<=y)) { tree[rt].lazy=1; tree[rt].sum=r-l+1; return; } int mid=(l+r)/2; if(x<=mid) { update(lson(pre),lson(rt),l,mid,x,y); } if(y>mid) { update(rson(pre),rson(rt),mid+1,r,x,y); } pushup(rt); } }T; void solve(int x,int fa) { T.root[x]=T.root[fa]; for(int i=0;i<q[x].size();i++) { T.update(T.root[x],T.root[x],1,n,dfn[q[x][i]],out[q[x][i]]); } ans[x]=max(T.tree[T.root[x]].sum-1,0); for(int i=head[x];i!=0;i=e[i].nxt) { solve(e[i].to,x); } } int main() { freopen("reward.in","r",stdin); freopen("reward.out","w",stdout); int m,u,a,b,i; scanf("%d%d",&n,&m); for(i=2;i<=n;i++) { scanf("%d",&u); add(u,i); } dfs(1); for(i=1;i<=m;i++) { scanf("%d%d",&a,&b); q[a].push_back(a); q[a].push_back(b); q[b].push_back(a); q[b].push_back(b); } solve(1,0); for(i=1;i<=n;i++) { printf("%d ",ans[i]); } return 0; }
\(T3\) C. 卡路里 \(0pts/0pts\)
-
部分分
- 测试点 \(1 \sim 5\) ：特殊性质加状压 \(DP\) 。
点击查看代码
ll a[5010][210],d[5010],sum[5010],f[10][(1<<10)+10]; int main() { freopen("calorie.in","r",stdin); freopen("calorie.out","w",stdout); ll n,m,ans=-0x3f3f3f3f,flag=1,num,i,j,k,h,v; scanf("%lld%lld",&n,&m); for(i=2;i<=m;i++) { scanf("%lld",&d[i]); sum[i]=sum[i-1]+d[i]; } for(i=1;i<=m;i++) { for(j=1;j<=n;j++) { scanf("%lld",&a[i][j]); } for(j=2;j<=n;j++) { flag&=(a[i][j]==a[i][j-1]); } } if(n>=8) { ans=0; if(flag==1) { for(i=1;i<=m;i++) { ans=max(ans,a[i][1]*n); } } else { for(i=1;i<=n;i++) { ans+=a[1][i]; } } } else { memset(f,-0x3f,sizeof(f)); f[0][0]=0; for(i=1;i<=m;i++) { for(v=0;v<=i-1;v++) { for(j=0;j<=(1<<n)-1;j++) { for(k=j;k!=0;k=j&(k-1)) { num=0; for(h=0;h<=n-1;h++) { num+=((k>>h)&1)*a[i][h+1]; } f[i][j]=max(f[i][j],f[v][j^k]+num-(v!=0)*(sum[i]-sum[v])); } } } ans=max(ans,f[i][(1<<n)-1]); } } printf("%lld\n",ans); return 0; } -
正解
- 观察到最优情况一定形如选择一段区间 \([l,r]\) 然后从某一个端点走到另一个端点，每款奶茶选择区间内卡路里最大的店购买。
- 不妨钦定从左往右走，并在卡路里相同时选择最靠左的店买奶茶。
- 单调栈处理出每款奶茶所能覆盖的区间，然后就得到了每款奶茶对于询问区间的贡献。
- 先对二维平面加差分后再做二维前缀和即可。
点击查看代码
ll a[5010][210],d[5010],sum[5010][5010],l[5010],r[5010]; stack<ll>s; int main() { freopen("calorie.in","r",stdin); freopen("calorie.out","w",stdout); ll n,m,ans=-0x7f7f7f7f,i,j; scanf("%lld%lld",&n,&m); for(i=2;i<=m;i++) { scanf("%lld",&d[i]); d[i]+=d[i-1]; } for(i=1;i<=m;i++) { for(j=1;j<=n;j++) { scanf("%lld",&a[i][j]); } } for(j=1;j<=n;j++) { while(s.empty()==0) { s.pop(); } for(i=1;i<=m;i++) { while(s.empty()==0&&a[s.top()][j]<=a[i][j]) { s.pop(); } l[i]=(s.empty()==0)?s.top()+1:1; s.push(i); } while(s.empty()==0) { s.pop(); } for(i=m;i>=1;i--) { while(s.empty()==0&&a[s.top()][j]<a[i][j]) { s.pop(); } r[i]=(s.empty()==0)?s.top()-1:m; s.push(i); } for(i=1;i<=m;i++) { sum[l[i]][i]+=a[i][j]; sum[i+1][r[i]+1]+=a[i][j]; sum[i+1][i]-=a[i][j]; sum[l[i]][r[i]+1]-=a[i][j]; } } for(i=1;i<=m;i++) { for(j=1;j<=m;j++) { sum[i][j]+=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]; if(j>=i) { ans=max(ans,sum[i][j]+d[i]-d[j]); } } } printf("%lld\n",ans); return 0; }
\(T4\) D. 传话游戏 \(4pts/4pts\)
总结
- 赛时后两个半小时基本全在写 \(T3\) 的 \(O(m^{2}3^{n}n)\) 的部分分，最后半个小时才想起来补 \(T3\) 的两个特殊性质和 \(T4\) 的一个特殊性质。
- \(T3\) 炸
int了，挂了 \(25pts\) 。
后记
- \(T2\)
- 下发的 \(PDF\) 上写的时限为 \(1s\) ，但在 \(OJ\) 上改成了 \(4s\) 。
- 数据中没有造 \(a_{i}=b_{i}\) 的特殊性质。