2019-2020 ICPC Asia Hong Kong Regional Contest

发表于 分类于

比赛链接

CF链接

题目

A. Axis of Symmetry

显然，对称轴最多只有4条。且这四条可以很容易算出来。

如何判断是否轴对称？只需要将在重合的边删掉就可以了。

B. Binary Tree

一棵满二叉树的节点个数定为奇数。

因此节点总数为偶数的情况必定会转移至奇数，反之亦然。

于是判断奇偶性即可。

C. Constructing Ranches

题意

一棵树，带点权。求有多少条路径，满足以路径中所有点权作为长度的线段，能在平面内形成一个多边形。

$n\le 2\times 10^5,value_i\le 10^9$。

题解

一堆数能形成多边形的充要条件是 $\sum a_i > 2\max{a_i}$。

点分治，用容斥的方法统计答案。

按照最大值从小到大排序，枚举一条路径 $a$，然后看有多少个在这个之前的 $b$ 满足 $len_a+len_b>2max_a$。

这个可以离散化后二分+树状数组查询。

时间复杂度 $O(n\log ^2n)$。

代码

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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
#include <bits/stdc++.h>
using namespace std;
#define FO(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout)
#define fo(i,j,k) for(int i=(j),end_i=(k);i<=end_i;i++)
#define ff(i,j,k) for(int i=(j),end_i=(k);i< end_i;i++)
#define fd(i,j,k) for(int i=(j),end_i=(k);i>=end_i;i--)
#define DEBUG(x) cerr<<#x<<"="<<x<<endl
#define all(x) (x).begin(),(x).end()
#define cle(x) memset(x,0,sizeof(x))
#define lowbit(x) ((x)&-(x))
#define ll long long
#define ull unsigned ll
#define db double
#define lb long db
#define pb push_back
#define mp make_pair
#define fi first
#define se second
inline int read()
{
	int x=0; char ch=getchar(); bool f=0;
	for(;ch<'0'||ch>'9';ch=getchar()) if(ch=='-') f=1;
	for(;ch>='0'&&ch<='9';ch=getchar()) x=(x<<3)+(x<<1)+(ch^48);
	return f?-x:x;
}
#define CASET fo(___,1,read())

const int N=200010;

namespace BIT{
	int n,tim;
	int t[N],b[N];
	inline void add(int x)
	{
		x++;
		for(;x;x-=lowbit(x))
			if(t[x]!=tim) t[x]=tim,b[x]=1;
			else b[x]++;
	}
	inline int ask(int x)
	{
		x++;
		int s=0;
		for(;x<=n;x+=lowbit(x))
			if(t[x]==tim)
				s+=b[x];
		return s;
	}
}
using BIT::ask;
using BIT::add;

vector<int> adj[N];
int siz[N],mx[N],val[N];
bool vis[N];
int rt;

void getroot(int u,int S,int pre)
{
	siz[u]=1; mx[u]=0;
	for(auto v:adj[u])
		if(!vis[v]&&v!=pre)
		{
			getroot(v,S,u);
			siz[u]+=siz[v];
			mx[u]=max(mx[u],siz[v]);
		}
	mx[u]=max(mx[u],S-siz[u]);
	if(mx[rt]>mx[u]) rt=u;
}
ll ans;
struct line{
	int mx; ll d;
	friend inline bool operator<(const line &A,const line &B)
	{
		return A.mx<B.mx;
	}
};
vector<line> vec;
vector<ll> num;
void dfs(int u,ll s,int mx,int pre)
{
	vec.pb((line){mx,s});
	for(auto v:adj[u])
		if(!vis[v]&&v!=pre)
			dfs(v,s+val[v],max(mx,val[v]),u);
}
void solve(int u,ll s,int mx,int opt)
{
	ll sum=0;
	vec.clear(); num.clear();
	dfs(u,val[u],max(mx,val[u]),0);
	sort(all(vec));
	for(auto v:vec) num.pb(v.d);
	sort(all(num));
	num.resize(unique(all(num))-num.begin());
	BIT::tim++; BIT::n=num.size();
	for(auto v:vec)
	{
		sum+=ask(upper_bound(all(num),2ll*v.mx-v.d-s)-num.begin());
		add(lower_bound(all(num),v.d)-num.begin());
	}
	ans+=sum*opt;
}

void divide(int u,int S)
{
	vis[u]=1;
	solve(u,-val[u],0,1);
	for(auto v:adj[u])
		if(!vis[v])
			solve(v,val[u],val[u],-1);
	for(auto v:adj[u])
		if(!vis[v])
		{
			int si=siz[v]>siz[u]?S-siz[u]:siz[v];
			rt=0;
			getroot(v,si,0);
			divide(rt,si);
		}
}
inline void add(int x,int y)
{
	adj[x].pb(y); adj[y].pb(x);
}
int n;
int main()
{
	CASET
	{
		n=read(); ans=0;
		fo(i,1,n) vis[i]=siz[i]=mx[i]=0,adj[i].clear();
		fo(i,1,n) val[i]=read();
		fo(i,2,n) add(read(),read());
		mx[0]=1e9; rt=0;
		getroot(1,n,0); divide(rt,n);
		printf("%lld\n",ans);
	}
	return 0;
}

D. Defining Labels

签到题。转换进制就可以了。

E. Erasing Numbers

题意

给定一长度为奇数的排列，每次能在相邻三个数中删去三个数中的最大与最小值。

对于每个 $i$，问能否通过某种删除方式使得最后剩下的数在原数组中下标为 $i$。

题解

枚举第 $i$ 个数，将小于 $i$ 的看成 0，大于 $i$ 个的看成 1，自己看成 X。

对于 X 处，不能含有两个 1 或 0。

假设在 X 处删完后，还将剩下若干个 1 或若干个 0。

于是大胆猜测能剩下 X 的当且仅当存在一种方法使得删一些东西后 1 和 0 个数相同。

显然连续三个相同的可以满足。

但可以发现，00100 这样也是可以的。

于是，对于一个连续的序列，|0 的个数 - 1 的个数| 大于等于 $3$ 时，可以让差值减少 $2$。

用 X 将序列分成两半，分开处理，用类似求最大子段和的形式去做即可。

时间复杂度 $O(n^2)$。

显然可以做到 $O(n)$。

G. Game Design

题意

对于一棵有根树，每个叶子结点中一个怪物。每个点 $i$ 可以设置一个塔，价格为 $a_i$，覆盖 $i$ 中子树的所有怪物。

一种方案为某种设置塔的方案，使得覆盖所有怪物。方案的价值为塔的价值之和。

构造出一棵树，使得取到最小价值的方案数恰为 $k$。

$k\le 10^9$

题解

设 $f(T)$ 表示树 $T$ 的最小价值，$g(T)$ 表示树 $T$ 取得最小价值的方案数。

那么将 $T_1,T_2$ 合并，得到一个方案数为 $g(T_1)\times g(T_2)$ 的操作是：建立一个新的根节点，权值为 $f(T_1)+f(T_2)+1$，根节点连向 $T_1,T_2$。

但是，仅有乘法操作是不够的，考虑加法操作：新建一个根节点，权值为 $f(T)$，将根节点与 $T$ 的根节点相连，就得到了一个方案数为 $g(T)+1$ 的树。

记录 $f(T)$ 的值，传下当前需要的 $g(T)$ 值，分治处理。

时间复杂度 $O(\log k)$。

I. Incoming Asteroids

鸽巢原理，如果最终要变为 $0$，那么至少有其中一个要得到 $\lceil \frac{y}{k}\rceil$。

开若干个 set 记录当前的值。每次若有成员满足超过了 $\lceil \frac{y}{k}\rceil$，$y$ 至少变成原来的 $\frac{2}{3}$。

时间复杂度 $O(m\log n\log y)$。

J. Junior Mathematician

数位DP模板。。

K. Key Project

贪心，模拟费用流，时间复杂度 $O(nm)$。