2023.7.11 杭州集训Day2 考试记录

2023暑杭州集训

SCOI2009 套题

Result

期望得分：

实际得分：

Process

考试时间回归 $3.5$ h，简介：没有罚坐，B题犯病没调出来 Rank $3$ 变 Rank $5$

开题。

A 一眼双指针，签到题
B 置换+构造+概率，相当于内向基环树上构造，概率可以转成数数，数数+构造？？？感觉毒瘤
C 数据范围很小，状压/搜索

忘了用了多久，反正秒了 $A$，可能是考虑到基环树上构造往往繁琐，选择先开 $C$

$C$ 肯定需要对选或不选豆子状压，那么怎么计算答案，当时觉得一步一步走十分不好判断包含，于是觉得是个偏构造/贪心的算答案方式。

然后想了很久乱搞了几次，没有一个确定的想法。

转头开 $B$，发现这个概率可以弄掉，那就变成纯构造，树上的构造显然很简单，开始凹环上的构造。

没有什么思路，准备玩样例，结果发现样例似乎给的十分有规律，观察加微调，弄了 $0.5$ h 左右，似乎凹出来了。

开冲，发现确实不是很好写，又不是很想写拍，后面跑同学手搓的数据挂了，调了很久，搞到快下考。

最后仍然挂了，有个特判没考虑到，还有些地方写挂了，痛失 $50pts$

A 生日快乐

简单题 略

B 骰子的学问

题面

Solution

置换，那就是内向基环树森林。

那么题目的条件即是，若 $a$ 指向 $b$，则满足 $a_i > b_j$ 的二元组有 $\geq \lfloor\frac{m^2}{2}\rfloor + 1$ 对

树上的很好构造，直接从叶子往下给极大值就行。

难点在于环。

给出从样例凹出来的构造方式：

我们从任意一个点开始，绕着环给每个点填 $[1,n]$ ，然后走反向边，从其父亲开始，给每个点填 $[n+1,2\times n]$ 以此类推。

不会证明，但会感性理解。

我们考虑类似断环成链，那么应该从终点往起点从小到大填，这就是为何要以反向边的方向。

然而这样每次起点将大于终点，看似不满足，所以需要轮换着填，这样每一对相邻的都有 $1$ 对的大小关系是反的，十分平均。

也就是轮换的填法十分平均，对应着环的特性。

实现上，找环是十分容易写错的点。

另：(n = 3, m = 4) 的置换环不满足此结论，其构造样例已给出。

Summary

感觉构造题还是多玩样例，而且这种轮换着填 $[k\times n + 1, (k + 1) \times n]$ 的东西好像有些典。

C 围豆豆

题面

Solution

数据范围很小，状压或搜索。

无论如何，显然要确定每个豆子选或不选，压个状态 $S$ 出来。

那么难点就在于如何 check 每个豆子是否被选到。

我们引进计算几何中，判断点是否在多边形内的射线定理。

对于某个点，取其上，下，左，右任意一方向，作射线，若交多边形于奇数个交点，则其在多边形内。

条件显然比抽象的包含简单很多。

我们发现这个东西是很好维护的，也就是说我们每走一步都可以维护当前的 $S$

那么考虑 BFS，设 $f(x, y, S)$ 为 走到 $x$，$y$，状态为 $S$ 的最小步数。

$S$ 十分好维护，不赘述。

关于实现上的细节：

需要注意的是，射线定理中，若是射线与多边形的边界重合，则其那条边只算一个交点。

也就是说，若正常算，其在边上每横着移动一次，都会算一个交点，会算多。

故我们只在纵向移动时改变 $S$ 的状态。

Summary

放弃 状压 / 搜索的主要原因还是没找到很好的判断点在多边形内的check方式，导致其很不可做。