NOIP2023 游记

· · 个人记录

2023-10-30

论 FJ NOIP 晋级线比 ZJ 高 25pts 是什么操作。

水了一发好久以前打的 CodeForces 题题解。

机房线段树大比拼！花了 9.5min 过掉了线段树1，某巨佬甚至只需要 5min。

然后和某巨佬想了一晚上 P4632 [APIO2018]新家 。看起来像是一个乱七八糟的偏序问题，显然地可以离线把时间维度解决掉，最后止步于二分答案（似乎很显然，然而二分答案是一个很重要的降维操作）后有一个莫名其妙的再离线一次的想法，颜色不连续的性质导致很难 \mathcal{O}(log n) 维护。然后惊叹于将 type 转化成计算 [r,n] 区间内的任意一种 type 的 pre 的最小值的人类智慧。开写！

2023-10-31

写了一个中午的 P4632 [APIO2018]新家 然后调了一个下午，最后发现是因为第 n+1 号点的 pre 一定会是 0 号点，在初始化的时候要在线段树里面把它 insert 进去，吸个氧就过了，两个 log 的做法讲道理跑的还挺快的。

题解，AC记录

2023-11-1

继续写奇怪的题。P4631 [APIO2018] 选圆圈 看起来很像奇怪的计算几何，事实上剪个枝随便就过了（我是绝对的小常选手！），时间复杂度 \mathcal{O}(Can\ Be\ Accepted)（by the way 最近在学圆锥曲线，真的很难！）。

题解，AC记录

2023-11-2

补了一下暑假没写的 P8421 [THUPC2022 决赛] rsraogps，大概就是说维护一个前缀和，然后由于按位与、按位或、gcd 的性质，修改最多不超过 \log n 次。故直接暴力修改然后求前缀和时间复杂度是正确的 \mathcal{O}(n\log v)。

AC记录

写了一发奇奇妙妙的 P9139 [THUPC 2023 初赛] 喵了个喵 II，看了一眼讨论区然后直接写了个 dfs RE 了，去 loj 参考了一发代码然后一发过掉了（？）。

AC记录

2023-11-3

写了一发 P4211 [LNOI2014] LCA 然后挂掉了（？）感觉做法很高妙，我想不出来。

给定 l,r,pos 让你求 \sum_{i=l}^r dep[\operatorname{LCA}(i,pos)] 把每个节点到根节点路径上的点权值加 1，这样问题转化成求 pos 到根节点的路径上权值和，差分一下然后离线去做。

好久没写树剖了，感觉手很生。

晚自习去考了个化学，感觉还不错。

2023-11-4

调了一个多小时把 P4211 [LNOI2014] LCA 和 P5305 [GXOI/GZOI2019] 旧词 都过掉了。

res(res+st.query(1,cnt,1,in[fa].seg,in[pos].seg))%mod;
//res(res+st.query(1,cnt,1,rev[fa],rev[pos]))%mod;

因为一个奇怪的小笔误浪费一下午也是没谁了。

AC记录 && AC记录

2023-11-5

凌晨，洗澡前点开了 P5811 [IOI2019] 景点划分 这道题，然后在浴室里思考了一下（某学姐：浴室确实是一个适合思考的地方）。

题意是给定一个连通图，要求将其划分成 A,B,C 三个部分，大小分别为 a,b,c。然后很显然的可以先缩点然后在 deg 上面考虑，转化成树上问题。不妨设 a\le b\le c，然后发现可以把 c 丢掉，考虑让根节点为重心，如果最大的子树大小大于等于 a 且小于 n-b 则直接把它弄成 A，剩下的暴力去跑一个大小为 b 的集合就好了。

容易发现 a\le b\le \frac{n}{2}，所以重心的这个想法很对啊。

然后看了一眼题解，都是先跑 dfs 树不缩点，其实感觉上和我的做法没什么区别（但是突然发现如果缩点之后再做的代码量会更大而且更复杂更多分讨论）。

早上 11 点起床之后写掉了，调了一些小错。然后发现 subtask 4 and 5 WA 掉了，一看全是给判 No Solution 了，想了半天发现有一种情况没有考虑，如果重心的子树有到重心的祖先的返祖边，那么这种情况可以把该子树和祖先的那个子树合并成一个连通块，而我的代码没有考虑到这点直接给他判无解了，加个分类讨论就过掉了。

AC记录