Codeforces Round #551 (Div. 2) D、E题解

发表于 | 分类于 |

D:一棵树有n(2≤n≤3e5)个节点，其中有k个叶子节点，叶子节点的值是1~k的任意一个排列(自己定)，非叶子节点的值是它所有儿子的最大值或者最小值。求根节点(1号)可以拥有的最大值。
自底向上树形dp。如果一个节点为max节点，那么不妨只保留一个儿子作为结果的最大值，而令其他儿子的子孙叶子节点尽可能小。这相当于删去了其他儿子，并把这个节点的度变为1。显然，度为1的max节点和min节点是等价的。所以经过若干次操作，这棵树只剩下min节点，所以答案就是剩下的叶子节点的最小值，即(k-w+1)，其中w为剩下的叶子节点数。(1,2,…,k-w在max节点中被”比下去”了，也就相当于被删除了)所以，为了让w尽量大，我们总是希望删除尽量多的叶子节点。因此，统计每个节点的子孙叶子节点数量，max节点只保留拥有最少的子孙叶子节点的儿子，同时还要累记被删掉的节点数量。 

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
#include <bits/stdc++.h>
using namespace std;
struct node{
	int fa,sh;//,nleaf;
	vector<int>son;
}st[400000];
int k=1,a[400000];
void dfs(const int&now){
	if(st[now].son.size()){
		int minm=INT_MAX,sum=0;
		for(auto&x:st[now].son){
			dfs(x);
			minm=min(minm,st[x].sh);
			sum+=st[x].sh;
		}
		if(a[now]){
			st[now].sh=minm;
			k+=sum-minm;
		}
		else st[now].sh=sum;
	}
	else{
		st[now].sh=1;
	}
}

int main (/*int argc, char const* argv[]*/){
	std::ios::sync_with_stdio(false);
	std::cin.tie(0);
	int n;cin>>n;
	for(int i=1;i<=n;i+=1){
		cin>>a[i];
	}
	for(int i=2;i<=n;i+=1){
		int f;cin>>f;
		st[i].fa=f;
		st[f].son.push_back(i);
	}
	dfs(1);
	cout<<k<<endl;
	return 0;
}

E题难受了……本来可以做出来，结果前面太磨蹭，然后还搞错了结束时间，结果莫名其妙提前放弃了……最后5分钟还在纳闷怎么还没结束……
不过赛后还是AC了(彩笔人生第一道交互题)。思路很简单：如果某个矩形包含了蛇的头或者蛇的尾中的一个，那么回答是奇数；否则是偶数。由于有2019次询问机会，而n不超过1000，因此可以询问n个1×n的矩形和n个n×1的矩形，找奇数的回答，就是头或者尾所在的坐标。如果头和尾既不在同一行也不在同一列，那么头和尾的坐标也都确定下来了，对4种可能的点分别询问一下即可。如果头和尾在同一行，那么通过之前的询问只能知道头和尾分别在哪一列，因此还要用二分查找确定在它们在哪一行。头和尾在同一列同理。
本题虽然思路简单，但实现比较繁琐，因此AC代码不贴了。
以上。