普及模拟3

HZOI - Isaac / 2023-08-22 / 原文

普及模拟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\) 分。