2023NOIP A层联测27 总结

T1 一棵树，操作是把一个点染黑，查询点 $x$ 到黑点路径上的最小编号，$n\le 10^6$。当时的思路是把树分成几部分，中间和周围的散块，发现不会，就没思路了，就去打了25pts暴力。赛后发现55pts暴力很简单，真遗憾没去打。题解方法很巧妙，设了装置为根，又维护点到根的最小编号，tql。

T2 一棵树，有若干棋子，每次操作把两个棋子相互靠近一步，问是否能把所有棋子移到同一点上，$n\le 10^6$。分析了性质发现，对于一个点，只有有棋子的点到它的距离之和为偶数，才可能有解。然后就不知道接下来怎么判断，就打了个假的贪心，取可能有解的最小距离除以2为答案，喜提71pts。题解是换根dp，写法很复杂。

T3 随机生成 $n$ 个长度为 $a_i$ 的小写字母串，$f(s)$ 表示 $s$ 的最小表示的开头字符在 $s$ 的下标，取最小的，求 $\sum _{i=1}^n[f(s_i)=f(s_{i\mathrm{mod}n+1})]$。看错题了，以为求最小的字符的下标，就用了1h+思考写代码，搞了半天过不了样例。赛后看懂题后发现，哎，真遗憾。

T4 树上有一条蛇，移动时身体不能重合，问是否能够头尾互换。题目很抽象，没看懂。发现题解又是换根，还要讨论一大堆，不过思路挺清晰，洛谷上是黑题，感觉最多紫。

期望得分：25+?+0+0=25+?

实际得分：25+71+0+0=96

总结：这场比赛在我看来比较难，导致我的心态不好，不想做，部分分都没有精力去骗，考试策略没有严格执行。对于解决树上问题不能熟练润用。要仔细看题目，正确理解题意。无根树转有根树，再维护到根的信息，可能有大用，树型dp继续优化多半是换根。考前要休息好。