NOIP2023模拟9联测32 总结

题目

T1 花菖蒲

大意

构造一个一度点数等于 \(a\)，二度点数等于 \(b\)，总点数小于 \(2000\) 的树。

\(a,b \leq 200\)

赛时思路

构造一条链，去除首位后有 \(b\) 个节点，这 \(b\) 个节点接一个一度点，加上首位两个一度点，如果一度点不够，那么将首部改造一个一度点为多度点，接多个一度点；如果一度点过多，那么无解。

正解思路

赛场思路即为正解，但忘加特判最后首部出现三度边的情况。

T2 百日草

大意

有向图中，求 \(1\) 出发，\(n\) 结束的代价最小值，代价为 \(1\) 到 \(n\) 路径中，经过的 边权乘到该边的时间 的最大值，每条边通过时间为一。

\(n,m \leq 3*10^5\)

赛时思路

想到二分答案控制经过的代价，求最小值，然后 hack 了……（似乎是这样子不能写 01bfs，不过后来又想到了 01bfs 并不影响答案，但再也没有向二分答案想了）

后面不知道二分什么，于是写了一个假的贪心，贪每次 01bfs 扩展到该节点最小代价，一个节点可以被扩多次，只要代价最小即可。

显然是错的，不仅过了大样例，还拿到了 \(80pts\)……

正解思路

就是一开始的二分答案，加 01bfs 的判断。

T3 紫丁香

大意

\(n\) 个点 \(m\) 条边的简单无向连通图，删掉若干条边，最大化度数为奇数的点的个数。

还要给出构造，输出一个长度为 \(m\) 的 01 串，1 表示保留这个边，0 表示删掉这个边，要求字典序最大。

\(n \leq 6*10^5,m \leq 9*10^5\)

赛时思路

开始分析了为树的情况，没有分析出结果，只好写了 \(20\) 的暴力。

正解思路

还没补出来。

T4 麒麟草

大意

平面上 \(n\) 个矩形。有 \(q\) 个查询，每次询问给出一个矩形，求询问矩形与这 \(n\) 个矩形重叠的面积的并。

强制在线。

\(n,q \leq 10^5\)，\(x,y \leq 10^9\)。

赛时思路

赛时暴力数组模拟平面，想冲离线部分分也没冲出来，写暴力将面积的标记错写到点上，于是没写出来。

正解思路

在线可持久化扫描线，还没补出来。

赛时

前期正常步骤。

开题分配 \(T1:50,T2:50,T3:40,T4:40\)。

\(T1\) 不是很有思路，先想 \(T2\)。

\(T2\) 想到二分答案，开始想 \(T3\)。

所以题都雨露均沾了一下，到 \(9:20\) 想到 \(T1\) 开始写。

写 \(T2\) 之前，把二分答案证伪了（？？？），然后不知道怎么做，看着身边的人都 \(AC\) 了，较上劲了一直在想。

剩 \(1h20min\)，水 \(T3\) 暴力。

\(T4\) 暴力写不出来，而且也不是很想写，回头继续想 \(T2\)。

由于一开始证伪了正解，所以说不知道要怎么办，只好糊了个乱搞。

后面 \(T4\) 又想写了（……），由于时间问题就没思考构思，结果写完发现又写错了。

最后检查题目，\(T1\) 的自己造的小样例也过了。（甚至没出到特判的情况……）

结束。

注：策略类分析未注明的均按照《考试策略》进行。

赛后

\(T1\) 忘特判 \(90pts\)。\(T2:80pts\)。\(T3:20pts\)。

\(T3\) 是正常情况，\(T1\) 这个特判没想到大意了，\(T2\) 的证伪太难受了，导致后面一直避开了正解。

反思

后面心态还是崩，如果不知道其他人的情况可能会好很多。

时间或心态紧张就忘记了要构思之类的步骤，导致后面写的时间长，调的时间更长。

\(T2\) 有点陷入 \(AC\) 综合症，唯一正确的选择是先写了 \(T3\) 的暴力。

1.心态要及时调整，还是不要关注身边人的做题情况，像跑步一样，跟着自己节奏来。

2.要大胆猜想，仔细论证，减少或避免出现证错的情况。

3.读题一定要结合样例！

4.难题暴力优先的策略一定要落实到位，最后比赛同层次差距就在这里。