普及模拟3
\(T1\) 最大生成树 \(100pts\)
- 简化题意:给定一个 \(n(1 \le n \le 1 \times 10^5)\) 个点的完全图,给定各点的点权 \(a_i(1 \le i \le n)\) ,两点间的边权为 \(|a_i-a_j|\) ,求该图的最大生成树。
- 正解:贪心,考虑到一个点对答案产生的贡献为 \(\max(a_i-\min\limits_{j=1}^{n} a_j,\max\limits_{j=1}^{n} a_j-a_i)\) ,又因为是完全图,易证得连边后一定是符合题意的解。
ll a[100001];//十年OI一场空,不开long long见祖宗 int main() { ll n,i,ans=0; cin>>n; for(i=1;i<=n;i++) { cin>>a[i]; } sort(a+1,a+1+n); for(i=1;i<=n-1;i++)//只需要n-1条边 { ans+=max(a[n]-a[i],a[i]-a[1]); } cout<<ans<<endl; return 0; }
\(T2\) 红黑树 \(80pts\)
- 简化题意:给定一棵 \(n(1 \le n \le 1 \times 10^5)\) 个点的有根树, \(1\) 为根节点,初始每个点都是红色,有 \(n\) 次操作,每次操作会把 \(p_i\) 变成黑色,保证操作序列 \(p\) 是一个排列,即每次操作的点都不相同。每次操作完成后,你需要输出有多少个子树是红黑子树,即子树内既包含黑点又包含红点。
- 部分分:
- \(20pts\) :对链的情况特判。
- \(80pts\)(在线做法) :一遍 \(DFS\) 处理出以 \(i(1 \le i \le n)\) 为根的子树大小,每次修改暴力跳父亲直到根节点,卡在了链的测试点上,复杂度为 \(O(n^2)\) ,代码。
- 正解(离线做法):
- 前置知识:红黑子树的产生与消失都是由改变颜色的这个点造成的。
- 例如,把节点 \(x\) 变成黑色后,对于所有包含 \(x\) 的子树 \(T\) ,如果 \(x\) 是该子树内第一个变成黑色的点,那么 \(x\) 会让 \(T\) 变成红黑子树;如果 \(x\) 是该子树内最后一个红色的点,那么 \(x\) 会让 \(T\) 变成非红黑子树。
- 记录下这棵子树中黑点最先出现和最后一个红点变成黑点的时候。
- 做法一:暴力跳父亲时跳到某个点时,若这个点既不是以这个点的父亲节点为根的子树内最先出现的黑点,也不是最后一个变成黑点的红点时就没有必要跳了,因为不会对答案产生贡献了(这里可能有些绕口,自己可以画图模拟一下)。
- 复杂度貌似很神奇,官方题解写的是 \(O(n)\) 。
struct node { int nxt,to; }e[200001]; int head[200001],minn[200001],maxx[200001],p[200001],id[200001],fa[200001],cnt=0;//minn表示(····)最早出现,maxx表示最后一个(····)消失 void add(int u,int v) { cnt++; e[cnt].nxt=head[u]; e[cnt].to=v; head[u]=cnt; } void dfs(int x) { minn[x]=maxx[x]=id[x]; for(int i=head[x];i!=0;i=e[i].nxt) { dfs(e[i].to); minn[x]=min(minn[x],minn[e[i].to]); maxx[x]=max(maxx[x],maxx[e[i].to]); } } int main() { int n,i,j,u,v,ans=0,flag; cin>>n; for(i=1;i<=n-1;i++) { cin>>u; v=i+1; fa[v]=u; add(u,v); } for(i=1;i<=n;i++) { cin>>p[i]; id[p[i]]=i; } dfs(1); for(i=1;i<=n;i++) { for(j=p[i];j!=0;j=fa[j])//暴力跳父亲 { flag=0; if(minn[j]==id[p[i]]) { ans++; flag=1; } if(maxx[j]==id[p[i]]) { ans--; flag=1; } if(flag==0) { break; } } cout<<ans<<" "; } return 0; }
- 做法二:进行差分维护一下。————隔壁@xrlong的做法
- 树状数组的区间修改单点查询操作:
struct node { int nxt,to; }e[200001]; int head[200001],minn[200001],maxx[200001],p[200001],id[200001],c[400001],cnt=0; int lowbit(int x) { return (x&(-x)); } void add(int u,int v) { cnt++; e[cnt].nxt=head[u]; e[cnt].to=v; head[u]=cnt; } void dfs(int x) { minn[x]=maxx[x]=id[x]; for(int i=head[x];i!=0;i=e[i].nxt) { dfs(e[i].to); minn[x]=min(minn[x],minn[e[i].to]); maxx[x]=max(maxx[x],maxx[e[i].to]); } } void update(int n,int x,int key) { for(int i=x;i<=n;i+=lowbit(i)) { c[i]+=key; } } int getsum(int x) { int ans=0; for(int i=x;i>0;i-=lowbit(i)) { ans+=c[i]; } return ans; } int main() { int n,i,j,u,v,ans=0,flag; cin>>n; for(i=1;i<=n-1;i++) { cin>>u; v=i+1; add(u,v); } for(i=1;i<=n;i++) { cin>>p[i]; id[p[i]]=i; } dfs(1); for(i=1;i<=n;i++) { update(n,minn[i],1); update(n,maxx[i]-1+1,-1); } for(i=1;i<=n;i++) { cout<<getsum(i)<<" "; } return 0; }
- 差分:
struct node { int nxt,to; }e[200001]; int head[200001],minn[200001],maxx[200001],p[200001],id[200001],sum[400001],cnt=0; void add(int u,int v) { cnt++; e[cnt].nxt=head[u]; e[cnt].to=v; head[u]=cnt; } void dfs(int x) { minn[x]=maxx[x]=id[x]; for(int i=head[x];i!=0;i=e[i].nxt) { dfs(e[i].to); minn[x]=min(minn[x],minn[e[i].to]); maxx[x]=max(maxx[x],maxx[e[i].to]); } } int main() { int n,i,j,u,v,ans=0; cin>>n; for(i=1;i<=n-1;i++) { cin>>u; v=i+1; add(u,v); } for(i=1;i<=n;i++) { cin>>p[i]; id[p[i]]=i; } dfs(1); for(i=1;i<=n;i++) { sum[minn[i]]++; sum[maxx[i]-1+1]--; } for(i=1;i<=n-1;i++) { ans+=sum[i]; cout<<ans<<" "; } cout<<"0"; return 0; }
- 做法一:暴力跳父亲时跳到某个点时,若这个点既不是以这个点的父亲节点为根的子树内最先出现的黑点,也不是最后一个变成黑点的红点时就没有必要跳了,因为不会对答案产生贡献了(这里可能有些绕口,自己可以画图模拟一下)。
- 前置知识:红黑子树的产生与消失都是由改变颜色的这个点造成的。
\(T3\) 校门外的树 \(30pts\)
- 简化题意:给定一个长度为 \(n(1 \le n \le 5 \times 10^5)\) 的序列 \(h\) ,有 \(m(1 \le m \le 5 \times 10^5)\) 次操作,每次操作前对于每一个 \(i(1 \le i \le n)\) 均有 \(h_i\) 增加 \(v_i\),操作如下(对 \(2^{64}\) 取模):
- 操作一:将 \([l,r]\) 内的 \(v_i(l \le i \le r)\) 增加 \(v\) 。
- 操作二:求 \(\sum\limits_{i=l}^{r} h_i\) 。
- 部分分:
- \(30pts\) :\(n^2\) 暴力枚举。
- \((30+20=50)pts\) :考虑到没有修改操作,维护一下即可。
- 正解:建一棵线段树,
\(T4\) 种树 \(0pts\)
- 简化题意:给定一个长度为 \(n(1 \le n \le 5 \times 10^5)\) 的线段,要求在这个线段上种树,对于每个 \(i(1 \le i \le n)\) 最多只能种一次树,有 \(m\) 组互相独立的计划,内容是第 \(x\) 个位置不能种树,\(|a_i-a_j| \ge k(1 \le i,j \le n,i \ne j)\) ,输出每个计划的方案数对 \(998244353\) 取模的结果。
总结
- \(T1、T3、T4\)打到 \(8:30\) ,\(9:30\) 打完 \(T2\) 后就去打高斯消元了,导致没有看见 \(T3\) 的对 \(2^{64}\) 取模(打成了 \(2^{60}\) )。
- \(T3\) 觉得线段树可做,但不想打了。
- \(T4\) 没有再多想想,没骗到计数类型的 \(DP\) 分。