目录
2020-2021 BUAA ICPC Team Supplementary Training 02
Results
Summary
- Solved 6 out of 10 problems
- Rank 3 / 18
- Solved 7 out of 10 afterwards
| # | = | Penalty | A | B | C | D | E | F | G | H | I | J |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 3 | 6 | 904 | +2 01:47 | +2 00:41 | -4 | + 00:25 | +1 03:21 | + 04:02 | + 03:08 |
Member Distribution
| Solved | A | B | C | D | E | F | G | H | I | J |
|---|---|---|---|---|---|---|---|---|---|---|
| Pantw | √ | √ | ||||||||
| Withinlover | O | √ | ||||||||
| Gary | √ | √ | √ |
(√ for solved, O for upsolved, - for tried but not solved)
Solutions
A
二分答案mid，小于mid的看做0，大于mid看做1，排序相当于一段区间赋值为连续的0或1，于是可以在线段树上查询和修改 $n\log^2n$
B
C
这个东西直接按坐标枚举线跨过的格子即可。需要分斜率绝对值 $> 1$ 和 $\le 1$ 两类，注意 dx 和 dy 的符号。
D
E
F
分奇偶讨论，偶数情况直接排开就好了，我是傻子
最开始的想法是一大一小排开就ok了，后来自己造了个n=5的样例叉掉了。然后写了个暴力和数据生成器疯狂的跑
后来发现一个好一点的样例5 1 5 6 7 9，答案有四个，分别是：
5 9 6 1 7
6 9 5 1 7
7 1 5 9 6
7 1 6 9 5
（其实后两个就是倒了过来，不过抓住了一个重要规律，奇数位永远是5 6 7
后来照着这个样例造了不少类似的，就大概确定做法了。
然后一直WA，考试结束才知道要奇偶讨论
（貌似可以推出来然而我不会
G
签到题
首先把所有的数字从小到大排序，将最小的数字压入堆里。每取出一个数字，就额外加入两个可能答案就好了。
假设取出了 $a_i$，就加入 $a_{i + 1}$ 和 $a_i + a_{i + 1}$。
闭着眼睛感受一下，哇！是对的！（其实就是利用排完序后已知的大小关系做了个优化）
H
这个题细节比较多。
看到这个题第一反应是拓扑学欧拉定理：
$$V+F-E=\chi$$
这个题里显然直线被多边形截得的部分与多边形本身构成一个连通图，那么 $\chi=2$。
多边形固有点数与固有边数都是 $N$。设新增点数 $\varDelta V$，新增边数 $\varDelta E$。
对上述公式进行代入并移项，得到：
$$F=(N+\varDelta E)+\chi-(N+\varDelta V)=\varDelta E-\varDelta V+2$$
那么最大化答案的过程就是最大化 $\varDelta E - \varDelta V$ 的过程。
如图，考察直线与多边形相交时对 $\varDelta E - \varDelta V$ 的贡献情况。
- 直线与多边形的某边重合：$V+0, E+0$
- 直线与多边形的某边相交：$V+1, E+1$
- 直线过多边形的某点：$V+0, E+0$
上述三者对答案的贡献均为 $0$，那么多出来的答案就只可能由多边形截直线所得的线段贡献。
至此，可以发现这个题相当于最大化多边形截直线所得线段数。
考虑如何计算这个最大线段数。
每条截线段一定是由两个边夹着的。
所以一个直接的想法是直接统计每条边对应的斜率区间，然后求被覆盖次数最大的位置，直接拿次数除二得到线段数。
然后写了 WA7，想了想好像一个正方形就能叉掉（吃了不仔细看样例的亏，一开始就听队友的写扫描的方法就完了 2333）
（下图中这个角度被四条边对应的区间覆盖，但只有 1 条截线段）
然后乖乖的写扫描。容易发现只有在顶点处答案才会改变。考虑以下四种情况：
- > 形，转过该斜率后答案 +1
- > 形，到达该斜率时答案 +1
- < 形，转过该斜率后答案 -1
- < 形，到达该斜率时答案 -1
剩下的问题就是怎么确定多边形在我的哪一侧。
这个也好办，数分知识告诉我们，对于单连通区域，在边界上逆时针走的时候区域一定一直在左手侧，用叉积判一判即可。
写完发现倒在了样例 2，画出来发现是这么个东西：
提示我们处理顶点两侧有边与扫描线重合的情况。
类似上图右边这样一长串重合只有首尾弯走的情况，线扫过后答案只会 +1 而不会 +2。
那么我们对这样一串顶点，只能选择一个顶点计算贡献，否则会算重。如果不处理会漏算。
解决方案也好想，只处理一头就可以了，具体是哪一头则需要两种情况错开：
- 对 > 类顶点 $i$，我只处理 $(i-1, i)$ 与扫描线平行，$(i, i+1)$ 与扫描线不平行的。
- 对 < 类顶点 $i$，我只处理 $(i, i+1)$ 与扫描线平行，$(i-1, i)$ 与扫描线不平行的。
这样一来，以下几种情况的答案均可以准确计算，这个问题也就圆满解决了。
（图中绿色箭头代表扫描线方向，橙色箭头代表多边形顶点编号正序方向，红色点是纳入考虑的点，蓝色贡献是滞后生效，紫色贡献立即生效）
I
对于一个只包含叶子节点的子树，发现他最多可以保留两条边不选，其余边必须两两配对，继续向上递归其叶子节点个数，会发现，每个节点的子树最多只会保留两条向上传递，继而又会发现如果节点的2个子树都包含两个叶子节点，这两个子树需要在这一层相互匹配被消掉，于是dfs一遍向上传递包含一个叶子节点和两个叶子节点个数量即可
J
Comments
ptw：
- 不希望总是加训起飞，还剩两场牛客，加油！
- F 题应该多讨论讨论的，其实就是个比较难猜的结论。
Gary:
- A题线段树空间没开够，需要整理板子
- J题读错题白给了一段时间
