2023NOIP A层联测24 总结
T1 给出树的一度点和三度点的数量，构造树的形态，节点数不超过 2000 2000 2000。我考虑先构造出三度点，发现这一度点至少是三度点+2，打完后测样例不对，发现加一度点时要特判是否为三度点，花 5min 打完，不放心，又手写 spj。用时 40min
T2 一个图，用 1 1 1 走到 n n n 代价为 ∑ i = 1 t t w t \sum\limits_{i=1}^ttw_t i=1∑ttwt， w t w_t wt 是第 t t t 条经过的点，求最小代价， n , m ≤ 3 × 1 0 5 n,m\le3\times10^5 n,m≤3×105。想了一会，代价很难维护，想到了二分答案，然后求出每条边经过的最大时间，这就是一个最短路问题，由于边权为 1 1 1，bfs 搞定。用时 20min
T3 一个图，可以删若干条边，求使奇点最多的字典序最小的删边方案。 n ≤ 6 × 1 0 5 n\le6\times10^5 n≤6×105。一开始我想贪心地删偶偶边，但是手模样例假了，看了部分分，20pts 状压，40pts 图是树，还有关于 n n n 的奇偶性的，当时想做一个树型 dp 骗分，但发现没办法求方案，也始终没想出题目跟 n n n 的奇偶性有什么关系。想了 1h 无果，就赶紧打 20pts 暴力跑路了。看完题解发现是要从生成树方面考虑，后面题解还用线段树维护一个标记，没看懂，后面看了其他人代码，学习了并查集做法。
T4 有 n n n 个矩形，每次询问给出一个矩形，这个矩形与给定的 n n n 个矩形相交的面积之并的面积不会维护矩形面积， n ≤ 1 0 5 n\le10^5 n≤105。好像想到用扫描线，但是不会。暴力只有 5pts 不如不打浪费时间，就返回去看 T3 了。题解还要用猫树，不会。
DYOJ 有同步赛，担心打了掉 rating 就没交。结果赛后发现 220 能拿下rk1……
期望得分：100+100+20+0=220
实际得分：100+100+20+0=220
总结：感觉T1T2水，后面很难。没挂分YES。注意细节，可以把重要变量和分类讨论先在纸上简要写下来。对于生成树和并查集不够熟练，看 dalao 代码学习代码实现能力。信息难维护时二分答案还是多考虑一下。构造题先从关键的重要的无可替代的条件或要求入手。数据结构是弱项，抽时间学一下扫描线和猫树。