2023NOIP A层联测24 总结

T1 给出树的一度点和三度点的数量，构造树的形态，节点数不超过 $2000$。我考虑先构造出三度点，发现这一度点至少是三度点+2，打完后测样例不对，发现加一度点时要特判是否为三度点，花 5min 打完，不放心，又手写 spj。用时 40min

T2 一个图，用 $1$ 走到 $n$ 代价为 $\sum _{i=1}^{t}t{w}_t$，$w_t$ 是第 $t$ 条经过的点，求最小代价，$n,m\le 3\times 10^5$。想了一会，代价很难维护，想到了二分答案，然后求出每条边经过的最大时间，这就是一个最短路问题，由于边权为 $1$，bfs 搞定。用时 20min

T3 一个图，可以删若干条边，求使奇点最多的字典序最小的删边方案。$n\le 6\times 10^5$。一开始我想贪心地删偶偶边，但是手模样例假了，看了部分分，20pts 状压，40pts 图是树，还有关于 $n$ 的奇偶性的，当时想做一个树型 dp 骗分，但发现没办法求方案，也始终没想出题目跟 $n$ 的奇偶性有什么关系。想了 1h 无果，就赶紧打 20pts 暴力跑路了。看完题解发现是要从生成树方面考虑，后面题解还用线段树维护一个标记，没看懂，后面看了其他人代码，学习了并查集做法。

T4 有 $n$ 个矩形，每次询问给出一个矩形，这个矩形与给定的 $n$ 个矩形相交的面积之并的面积不会维护矩形面积，$n\le 10^5$。好像想到用扫描线，但是不会。暴力只有 5pts 不如不打浪费时间，就返回去看 T3 了。题解还要用猫树，不会。

DYOJ 有同步赛，担心打了掉 rating 就没交。结果赛后发现 220 能拿下rk1……

期望得分：100+100+20+0=220

实际得分：100+100+20+0=220

总结：感觉T1T2水，后面很难。没挂分YES。注意细节，可以把重要变量和分类讨论先在纸上简要写下来。对于生成树和并查集不够熟练，看 dalao 代码学习代码实现能力。信息难维护时二分答案还是多考虑一下。构造题先从关键的重要的无可替代的条件或要求入手。数据结构是弱项，抽时间学一下扫描线和猫树。