2022杭电多校第六场题解

2022杭电多校第六场

Maex（树形DP）

题意
给定一棵以1为根的有根树，树上的每个点都有一个权重，顶点$i$的权重是$a_i$，$a_i$不是给定的，并且$a_i$互不相同。定义 b u = M E X { x ∣ ∃ v ∈ subtree ⁡ ( u ) , x = a v } b_u=M E X\left\{x \mid \exists v \in \operatorname{subtree}(u), x=a_v\right\} bu​=MEX{x∣∃v∈subtree(u),x=av​}，求${\sum }_{i=1}^n{b}_i$的最大值。其中集合$MEX$表示集合中最小的未出现的非负的元素。

分析
由于权值各不相同，对于一点$u$，$b_u$的最大值是$size(u)$，并且同一个父结点的若干个子树只有一棵子树的$MEX$值不为0，$b_u$不为0的点形成了根向下走的一条路径。考虑用树形DP求最值，状态转移方程为：
$$f[u]=sz[u]+max(f[v])(v\in subtree(u))$$
时间复杂度$O(n)$

AC代码

typedef long long ll;
const int N=5e5+10;
vector<int> v[N];
ll f[N],sz[N];

void dfs(int x,int p)
{
	ll mx=0;
	sz[x]=1;
	for(auto y:v[x])
	{
		if(y==p) continue;
		dfs(y,x);
		sz[x]+=sz[y];
		mx=max(mx,f[y]);
	}
	f[x]=sz[x]+mx;
}

int main()
{
	int T;
	cin>>T;
	while(T--)
	{
		int n;
		cin>>n;
		for(int i=1;i<=n;i++) f[i]=sz[i]=0;
		for(int i=1;i<=n;i++) v[i].clear();
		for(int i=1;i<n;i++)
		{
			int x,y;
			cin>>x>>y;
			v[x].push_back(y);
			v[y].push_back(x);
		}
		dfs(1,-1);
		cout<<f[1]<<endl;
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

Shinobu loves trip（数论）

题意
有$P$($P$是质数)个国家，下标从0开始编号。当Shinobu在第$i$个国家时，她下一个要访问的国家是$(i\ast a)modP$，从一个国家到另一个国家需要1天的时间。现在给出$n$种旅行方案，每个旅行方案包括起始国家$s_i$和旅行天数$d_i$。有$q$次询问，对于每个询问输出有多少种旅行方案经过$x_i$。

分析
对于给定的$x$，判断当前方案是否经过$x$，只需判断是否$\exists k(0\le k\le d_i)$使得$(s_i\ast a^k)\%P=x$，其中$a$是确定的，可以预处理$a$的幂和$s_i$的逆元。由于$P$是质数，可以计算出$a^k$的值，再判断是否有满足条件的$k$。时间复杂度$O\left(T\ast \left(\max \left(d_i\right)+n\log (P)+nq\right)\right)$。

AC代码

typedef long long ll;
const int N=1010;
int s[N],d[N],inv[N];
int P,a,n,q;

int ksm(int a,int b)
{
	int ans=1%P;
	for(;b;b>>=1)
	{
		if(b&1) ans=(ll)ans*a%P;
		a=(ll)a*a%P;
	}
	return ans;
}

int main()
{
	int T;
	cin>>T;
	while(T--)
	{
		cin>>P>>a>>n>>q;
		int mx=0;
		for(int i=1;i<=n;i++) cin>>s[i]>>d[i],mx=max(mx,d[i]);
		for(int i=1;i<=n;i++) if(s[i]) inv[i]=ksm(s[i],P-2);
		unordered_map<int,int> mp;
		mp[1]=0;
		ll y=a;
		for(int i=1;i<=min(mx,P-2);i++)
		{
			if(!mp.count(y)) mp[y]=i;
			y=y*a%P;
		}
		while(q--)
		{
			int x;
			cin>>x;
			int ans=0;
			if(x==0)
			{
				for(int i=1;i<=n;i++) if(s[i]==0) ans++;
			}
			else
			{
				for(int i=1;i<=n;i++)
				{
					if(s[i]==0)
					{
						if(x==0) ans++;
					}
					else
					{
						ll z=(ll)x*inv[i]%P;
						if(mp.count(z)&&mp[z]<=d[i]) ans++;
					}
				}
			}
			cout<<ans<<endl;
		}
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63

注意
如果不预处理$s_i$的逆元，时间复杂度会多一个$log$，不能通过本题。

Map（计算几何）

题意
Sakuyalove有一张大的世界地图$M$和一张小的世界地图$m$，地图是长方形的，并且小地图由大地图压缩而来，小地图放在大地图的内部(包括边界)。Sakuyalove发现总是存在一点$P$满足这个点在两个地图中指示的位置相同。现在给出两个地图的坐标，求$P$点的坐标。

分析
最开始的想法是由两点坐标求直线的一般式，设出$P$点坐标，再根据点到直线的距离公式$\frac{|A{x}_0+B{y}_0+C|}{\sqrt{A^2+B^2}}$联立两个方程求解，但点到直线距离公式带有绝对值，无法直接计算。后来想到用叉积代替点到直线距离方程，通过面积的比值联立方程，赛时使用的这种方法AC，编码较为复杂。在严格鸽的题解中使用了复数进行求解，方法简便并且代码很短，详见https://zhuanlan.zhihu.com/p/549964144。

题解给出了代数和几何两种方法。

AC代码

#include 
#define endl '\n'
using namespace std;
typedef long long ll;
complex<double> a[5],b[5],r,t,ans,z;

int main()
{
	int T;
	scanf("%d",&T);
	while(T--)
	{
		for(int i=1;i<=4;i++)
		{
			double x,y;
			scanf("%lf %lf",&x,&y);
			a[i]={x,y};
		}
		for(int i=1;i<=4;i++)
		{
			double x,y;
			scanf("%lf %lf",&x,&y);
			b[i]={x,y};
		}
		t=(b[1]*a[2]-b[2]*a[1])/(a[2]-a[1]);
		r=(b[1]-t)/a[1];
		z={1,0};
		ans=-t/(r-z);
		printf("%.6f %.6f\n",ans.real(),ans.imag());
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

Planar graph（图论 最小生成树）

题意
如果一个无向图存在一种在平面的绘制方法，保证任意两条边除了端点之外没有交点，那么就说这个无向图是平面图，下图所示是一个平面图。

下图所示是一张非平面图，可以证明无论怎样画这张图，一定存在两条边有非端点的交点。

对于一张平面图，它有很多区域被边分割，下面这张图有4个区域，其中区域1是无穷大的。

给定一个含有$n$个顶点和$m$条边的平面图，平面图上的每个区域建立一个国家。你是设计师，并且你可以在两个区域的交界处建立隧道，两个城市之间只能通过隧道相互到达。下图所示是一种建立隧道的方式。

输出所需建设隧道数量的最小值，使得所有城市都连通。如果有多种方案，输出需要建隧道的边的编号字典序最小的方案。给定的图保证是平面图，但可能含有重边、自环，图也可能不连通。

分析
一个自然的想法是将每个区域看做点，如果两个区域相邻就连边，建图之后跑最小生成树，但是这种思路很难实现。换一种思路，建隧道的过程就是在原图上删边的过程，所有区域连通等价于原图中不存在环。在原图上跑最小生成树就可以得到要保留的边，由于题目要求字典序最小，倒序枚举每条边即可。

AC代码

const int N=2e5+10;
int pa[N];
struct node {
	int x,y;
}p[N];

int find(int x)
{
	return pa[x]==x?pa[x]:pa[x]=find(pa[x]);
}

int main()
{
	int T;
	cin>>T;
	while(T--)
	{
		int n,m;
		cin>>n>>m;
		for(int i=1;i<=n;i++) pa[i]=i;
		for(int i=1;i<=m;i++) cin>>p[i].x>>p[i].y;
		vector<int> ans;
		for(int i=m;i>=1;i--)
		{
			int u=find(p[i].x),v=find(p[i].y);
			if(u==v) ans.push_back(i);
			else pa[u]=v;
		}
		reverse(ans.begin(),ans.end());
		cout<<ans.size()<<endl;
		for(auto x:ans) cout<<x<<" ";
		cout<<endl;
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

注意

Loop（单调栈 优先队列）

题意
给定一个长度为$n$的数组，下面要进行$k$次如下操作：

• 选择一个区间$[l,r]$
• 将区间$[l,r]$内的元素循环左移一个位置

求 $k$ 次操作后数组字典序最大的结果。

分析
每次操作实质上是将一个数放到它后面的某个位置，贪心的从前往后找到第一个满足$a_i<a_{i+1}$的 $a_i$，将 $a_i$ 放到后面会使答案更优，这样的 $a_i$ 最多可以选择 $k$ 个。先不考虑 $a_i$ 放的位置，从前到后处理过的序列一定是非递增的，可以用单调栈维护。为了使字典序最大，可以将选择的 $k$ 个数放到优先队列中，从前往后处理一遍后，再将剩余元素和优先队列的元素归并，得到最终结果。时间复杂度$O(nlog(n))$。

AC代码

const int N=3e5+10;
int a[N],b[N],stk[N];
int top;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	int T;
	cin>>T;
	while(T--)
	{
		int n,k;
		cin>>n>>k;
		for(int i=1;i<=n;i++) cin>>a[i];
		priority_queue<int> q;
		top=0;
		for(int i=1;i<=n;i++)
		{
			while(top&&k&&stk[top]<a[i])
			{
				q.push(stk[top]);
				top--;
				k--;
			}
			stk[++top]=a[i];
		}
		for(int i=1,j=1;i<=n;i++)
		{
			if(j>top)
			{
				b[i]=q.top();
				q.pop();
			}
			else if(!q.size())
			{
				b[i]=stk[j++];
			}
			else
			{
				if(q.top()>stk[j])
				{
					b[i]=q.top();
					q.pop();
				}
				else
				{
					b[i]=stk[j++];
				}
			}
		}
		for(int i=1;i<=n;i++)
		{
			if(i>1) cout<<" ";
			cout<<b[i];
		}
		cout<<endl;
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60

注意
Don’t have spaces at the end of the line