2019-2020 ICPC Asia Hong Kong Regional Contest¶
| 排名 | 当场过题数 | 至今过题数 | 总题数 |
|---|---|---|---|
| 9/341 | 8 | 10 | 11 |
A¶
solved by 2sozx Bazoka13
题意¶
给定二维平面 \(n\) 个矩形，平行于坐标轴，寻找对称轴。\(n\le 10^5\)
题解¶
显然对称轴只有平行于坐标轴与 \(k = \pm1\) 两种情况。
将每个矩形的关键点抠出，即出现奇数次的点，存入 \(map\) 中，就可以 \(log\) 查询。
平行于坐标轴时考虑 \(max_x,max_y,min_x,min_y\) 即可。
\(k = 1\) 时可以考虑最右上和最上右的点的中垂线即为唯一又可能的对称轴，之后枚举关键点看对称过去是否有点即可。\(k = -1\) 同理
C¶
solved by JJLeo
题意¶
给定一颗 \(n\) 个点的树，每个点有点权 \(a_i\)，问有多少条路径其上面所有点对应权值的边能构成多边形。(\(1 \le n \le 2 \times 10^5\)，\(1 \le a_i \le 10^9\))
题解¶
\(a_1,a_2,\cdots,a_n\) 能构成多边形的充要条件是 \(\sum \limits _{i=1}^n a_i - \max \limits _{i=1} ^n a_i > \max \limits _{i=1} ^n a_i\)。
考虑点分治，对于一个分治中心，将所有路径拿出来算方案数，再分别减去每个子树内部的路径算方案数。对于给定的路径可以使用如下方法算方案数，将每个路径按路径上最大值从小到大排序，再将每个路径上权值和进行离散化，对于每个路径来说，可以和它组合的路径是最大值比他小且路径上权值和处于一个区间的所有其它路径，扫一遍利用树状数组统计方案数。总时间复杂度为 \(O(n \log ^2 n)\)。
E¶
solved by Bazoka13
题意¶
\(n\) 个不同的数，\(n\) 为奇数，每次可以选择连续的三个数，保留其中位数，问每个数最后能不能被留下。(\(1 \le n \le 5000\))
题解¶
考虑枚举每个数，判断彳亍不彳亍。
将比它小的数设为 \(0\)，比它大的数设为 \(1\)，最终必须 \(01\) 相等，此时不断找又有 \(0\) 又有 \(1\) 的连续段选择就可以。
每 \(3\) 个连续的 \(0\) 或 \(1\) 可以删掉两个对应的数，因此判断下能不能把多的那个数字删到和少的一样就可以。
时间复杂度为 \(O(n^2)\)。
F¶
upsolved by
题意¶
恶心人几何爬
题解¶
G¶
solved by Bazoka13
题意¶
构造一颗 \(n\) 个节点的树，每个节点有权值 \(a_i\)，选择一些点使得每个点到根节点至少有一个点被选中，最小化所选点权值之和。要求有 \(k\) 种不同的最优方案。(\(1 \leq k \leq 10^9\)，\(1 \le n \le 10^5\)，\(1 \le a_i \le 10^9\))
题解¶
考虑构造二叉树，令一个节点的权值为左右子树最优方案权值之和的和，那么方案数就是左右子树方案乘积 \(+1\)。
若 \(k\) 是偶数，递归构造 \(k-1\) 和 \(1\)；否则递归构造两个 \(\dfrac{k-1}{2}\)。
递归边界为叶子节点，将其权值赋为 \(1\) 即可。
H¶
upsolved by JJLeo
题意¶
初始为空的长度为 \(n\) 的序列，需要支持 \(m\) 次以下两种操作之一：
- 在一个位置加一个数 \(a_i\)。
- 给定数 \(b_i\)，求该数在给定区间 \([l_i, r_i]\) 前驱后继。
保证每个位置最多被加一个数，不强制在线。(\(1 \le n \le 5 \times 10^5\)，\(1 \le m \le 10^6\)，\(1 \le a_i, b_i \le 10^9\))
题解¶
直接线段树套 set 常数太大会 T，必须离线减小常数。
将加入和询问的所有值离散化，建权值线段树。
将所有询问按右端点排序，从小到大遍历，每到一个新的右端点，就把该点的值（如果有）加入到权值线段树中，以二元组 \((x,t)\) 的形式加入，其中 \(x\) 表示该元素的位置，\(t\) 表示该元素加入的时间。
考虑如何询问，对于一个询问 \((b,l,r,i)\)，\(i\) 是该询问的时间，因为我们已经按 \(r\) 排序了，所有加入的元素都满足 \(x \le r\)，因此只需考虑 \((b,l,i)\)，我们可以在线段树上二分以确定 \(b\) 的值，而这个确定过程就需要 \((l,i)\) 的值。可以发现，一个元素对于该询问来说是合法的当且仅当 \(l \le x \land i > t\)，因此可以在每个线段节点维护一个存放询问的单调栈，保证 \((x,t)\) 两个位置前者递增后者递减，这样查询时只需二分第一个 \(x \ge l\) 的位置，看对应的 \(t < i\) 是否满足即可。
具体实现来说，前驱后继可以分为寻找权值 \([1, b_i]\) 中最大的满足条件的数，以及 \([b_i, +\infty]\) 中最小的满足条件的数。以前者为例，考虑按线段树区间查找的方法，优先访问右节点，如果找到一个完全覆盖了的合法的节点，就在该节点继续向下二分并直接返回，不再访问其它节点，这样访问总结点数是 \(O(\log n)\) 的。其实这个做法不需要拆成两个函数，直接写成优先访问右节点，且完全覆盖+合法就往下走即可，和上述分析过程本质是一样的。
这个做法的复杂度还是 \(O(m \log ^2 n)\) 的，那为啥能过呢？因为每个对于每个节点，如果该节点不合法，就不再继续往下走，这个剪枝极大提升了效率，就过了。
I¶
solved by 2sozx Bazoka13 JJLeo
题意¶
\(n\) 个天体，\(m\) 个如下事件之一：
- 新来了一个观测者，它需要观察 \(k\) 个特定天体，一旦这些天体出现时间之和 \(\ge y\) 分钟，他就会离开。
- 天体 \(x\) 出现了 \(y\) 分钟，问出现后有多少观测者离开。
强制在线。(\(1 \le n,m \le 2\times 10^5\)，\(1 \le k \le 3\)，\(1 \le y \le 10^6\))
题解¶
根据抽屉原理，如果一个观测者将要离开，那么必然存在一个他观察的天体出现时间不少于 \(\lceil \dfrac{y}{k} \rceil\)。
将每个观测者需求的 \(y\) 分钟「拆分」为 \(k\) 个需求，放到对应天体的优先队列中，每个需求将时长设为 \(\lceil \dfrac{y}{k} \rceil\)，这样一旦他可以离开必然会被其中一个所指出。
对于第二种操作，如果该天体出现时间 \(y\) 不超过该天体优先队列中最短时长，则只维护一个偏移量标记；否则将所有 \(\ge y\) 的需求全部拿出进行更新，如果该观测者时间已经到了，则记录输出，否则设其剩余时长为 \(x\)，再将其拆分」为 \(k\) 个需求，放到对应天体的优先队列中，每个需求将时长设为 \(\lceil \dfrac{x}{k} \rceil\)，可以看出它们必然覆盖之前相同观测者的数据，就像优先队列优化 Dijkstra 一样。
每个元素至多被重新分配 \(\log_{\frac{2}{3}}y\) 次，因此总复杂度为 \(O(m \log m \log y)\)。
J¶
solved by JJLeo
题意¶
定义 \(f(x)\) 为 \(x\) 十进制表示中任意两个不同数位乘积之和，求 \([L,R]\) 中有多少数满足 \(x \equiv f(x) \pmod{m}\)。(\(10 \le L \le R < 10^{5000}\))
题解¶
数位 dp，除了是否贴上界，再开两维记录之前位的数位之和，以及 \((x - f(x)) \bmod m\) 即可。
需要注意当一个数的位数确定，第 \(i\) 位填 \(x\) 最终对应的权值可以乘以一个 \(10^i\) 来得到，不需要使用类似秦九韶的方法，这样可以少开一维。
K¶
upsolved by JJLeo
题意¶
数轴上 \(n\) 个建筑，第 \(i\) 个建筑距离第 \(i+1\) 个建筑 \(d_i\)。\(m\) 个第一类人，\(m\) 个第二类人，每个人在一个建筑内，各有一个权值 \(a_i\)，选择两个不同类别人配对的价值是他们两个的权值加上他们两个所在建筑的距离。问选择 \(1,2,\cdots,m\) 对人配对的最小价值。(\(1 \le n \le 800\)，\(1 \le m \le 50000\))
题解¶
考虑网络流建图，每个建筑距离最近的建筑连一条边（左右相邻都要连），流量无限费用为两者间的距离。对于每个第一类人，从源点向对应建筑连一条边，流量为 \(1\) 费用为 \(a_i\)；对于每个第二类人，从对应建筑向汇点连一条边，流量为 \(1\) 费用为 \(a_i\)。逐步增加流量，对应的最小费用即为答案。
直接跑费用流显然复杂度裂了，可以考虑这个图的特殊性去模拟每一次流量的增广。
首先从源点连向建筑的边和建筑连向汇点的边必然都不会发生反悔，且每次增广对于每个建筑而言，必然选费用最小的边。对于建筑之间的边，记录哪些方向的边的反向边是有流量的，它们的费用是 \(-a_i\)，会优先选作为流经的边。基于图是「一条链」，正反扫两遍就可以 \(O(n)\) 得到这一次的最小费用增广路，再用 \(O(n)\) 的时间将增广路上相关边的流量像费用流算法一样进行更改即可。
做 \(m\) 次每次输出答案即可，总时间复杂度为 \(O(nm)\)。
记录¶
0min：分题，MJX冲D
15min：MJX AC，期间CSK冲E，MJX冲B
18min：MJX AC，CSK冲E
25min：CSK WA1 后AC，冲G
60min：CSK WA2 后AC，期间ZYF冲J
68min：ZYF AC，看C可做写C，CSK看I
149min：ZYF AC，期间MJX写I
164min：MJX AC，冲A
268min：MJX WA2 后AC，直接下机看题解去
till end：题解让人迷惑
总结¶
E(+1):比较符写错，>= 写成了 ==
G(+2):边界情况没处理
I(+2):输出结尾不能有空格，读题不认真，有一个输入不异或上一次答案
A(+2):%未取abs，平行坐标轴时模数应为4