2023.7.13 杭州集训Day3 解题报告

2023暑杭州集训

Result

期望得分：

实际得分：

Progress

今天居然不是往年省选，总体来说题目简单很多（还是想做省选套题）。

开题。

A 签到题，想了一会看出来二分图，会了（为什么输入这么shi）
B 又是 $n \leq 30$，看来这真的很喜欢状压（，然后过了一会突然想到这个很像 斯坦纳树，那应该大概会了（为什么输入又这么shi）
C 人类智慧数学题？？？

$< 30$ min $A$ 切了，没啥障碍。

发现 $B$ 如果让 $8$ 个点都联通就是斯坦纳树，那我们可以先做个斯坦纳树，然后又想了一会，发现最后跑个子集 DP，直接将一些状态合并以减少选边就可以了。

约 $1.5$ h $B$ 切了。

开 $C$，直接大力分讨，发现有一种情况可以做 三维偏序，考虑能不能把其他情况转化成能做三维偏序的式子。

情况好像巨多，而且偏序的式子都不一样，很难写。

并且有几种情况，要做 $(a_i, b_i, c_i)$ 与 $(a_j, b_j, d_j)$ 的三维偏序，我考场上不知道 cdq 可以做这个东西。

想了会还是不会，换个思路，断环成链。

好像情况少了好多，只要写两个 cdq，直接开冲。

样例没过，肉眼调试，感觉没错，手玩样例，发现好像会算重，并且不会去重，寄。

离下考不到 $0.5$ h，赶紧冲个暴力，然后才意识到出题人没有把数据范围卡得很大。

那不是可以模拟退火？？？但是没时间了（而且我也不是很会写模拟退火）

下考，暴力居然冲过了 $40pts$，果然有老哥用模拟退火，还拿了 $90pts$ 高分。

看起来 $240pts$ 有点大众啊，几个并列 Rank1，居然有老哥切了 $C$ 但没切 $B$，看来是不会斯坦纳树，有点遗憾，但还是强悍。

改题的时候 $Like\_AC$ 告诉我前面那个 怪怪的三维偏序是能做的，而且加个小巧的 trick 就只要讨论两种，好像有点傻了（

A 分群

题面

Solution

签到题。

如果考虑到按男女生分成两部，那显然可以想到二分图。

将所有情况都不满足的点连边，那就是求个最大独立集就行了。

B 地图游戏

题面

Solution

我会斯坦纳树！

那就做个简单的子集 DP 就好了，不赘述了。

难点在斯坦纳树。

C 相遇点对

Solution

首先来解决 $Process$ 中的问题： $(a_i, b_i, c_i)$ 与 $(a_j, b_j, d_j)$ 的三维偏序

其实做法很简单，只要在归并的时候，左部点将 $c_i$ 加进树状数组，右部点用 $d_j$ 查询就好了。

没想到说明还是不很会 cdq ！

还有个小 trick，我们将所有点的速度加上一个值，由于他们的相对位置不会改变，所以是等价的，那么我们将所有的速度都变成正的，他就只存在两种追击的问题。

那么做两个三维偏序就好了。

Summary

积累了 cdq 的技巧，发现了 cdq 有欠缺。