【游记】PKUSC及APIO2024

· · 生活·游记

PKUSC DAY 0

无事

PKUSC DAY 1

进场，没带笔，找 Hanghang 借了一只。

看 T1，怎么贪都对，从回文中心贪就好了，挺答辩的 T1。

然后不会哈希，直接写成了两只 O(\log) ，卡了半天常才发现。

然后就过了一个半小时多。

然后把 T2 T3 的 10+11 的暴力写了一下。

不会计算几何没写 T2 的 15，就写那个 25 的直角三角形。

然后就花了很久数对了。

然后结束了。

100+35+11

大多数人好像是写了个 T3 48 的，写直角三角形的好像不多。

PKUSC DAY 2

看 T1，有点神秘，猜了一个可以过样例的什么最长路啥的写了二十分钟，然后没过。

然后就是假定一个点的经过次数为 2^p 那它就会给他可以到的分别加上 2^{p-1} 的经过次数，然后每个点的经过次数都是偶的，直接写一个 O(n^2) 高精度不知道为啥就过了。

看 T2，首先一个区间向左扩和向右扩都是单调递增的，但是向左不好离线跑莫队，在线线段树的话映射集合太大应该是不好合并的，离线线段树动右端点我不知道为啥觉得做不了。

最后发现 n 个人在值域上只有 O(n) 段有效位置，也就是说这 n 个人来之前有 x 个人已经在澡堂里面对应的 n 个人来之后进去了 y 个的不同的 y 对应的 x 区间数量只有 O(n)，如果我们能找到这 O(n) 个有效位置那么我们就可以做分块做到 O(n\sqrt n) 获得一个 70。

原因是显然对一个人来说已经在澡堂里的人数量在一个连续的区间内他才会进去。

找到有效位置又想了一个小时，想的方法是设当前这个人前面已经进了 now 个，我们直接对还没进去过的做 minn\leftarrow l_i-now 在里面的做 minn\leftarrow r_i-now+1，那么此时开头多 minn 个人才会产生变化。

这样就可以得到一个在线根号做法了。

然后 T3 神秘题，写个 Dij 获得 5 分。

出来发现很多人 T1 卡住了，正解是 bitset，T3 别人的 Dij 好像多 10 分不知道为啥。

洗澡的时候发现 T2 实际上由于左扩单调递增那么右扩加入点的值域区间对应一个左端点的数列区间直接线段树二分加区间加就做完了，感觉比分块容易想。

100+70+5

PKUSC DAY 3

西西又湖湖

APIO DAY 0

无事

APIO DAY 1

进场，没笔，找隔壁老哥借一只。

T1 看起来很低能，写一下过了。

T2 题面挺长的，读了一会，图没条件不太会。

然后就是发现按时间来说就是 DAG 那就按时间松弛即可。

然后就是要算每次换乘之间至少要吃几顿，为什么是至少，因为我读成了一份钱可以满足多顿同一时间的饭，然后我说这个东西我连线段树去做一个复杂度低于 O(n^3) 都做不到，那么应该是不可做的，然后这个东西也显然没有决策单调性，如果我只需要算两个时间点之间有多少可区间就好了，实际上那个部分分就可以只算个数，然后因为有决策单调性直接对每个点维护一个二分栈加个主席树算区间个数就做完了，但是分太少了懒得写。

然后就去写 T3，最后写了个 35，回去继续做 T2，剩二十分钟发现是我自己读不懂中文，他题面给的就是直接算区间个数就行了，而不是用最少数量的点覆盖区间，想了一下，包含优于交叉应该是做个二分栈即可。

然后就退场了。

100+0+35

比较低能。

APIO DAY 2

在到达闭幕式现场之前突然晕厥了。

APIO DAY 3

退场。