NOIP2025 邮寄
AC_Lover
·
·
生活·游记
晚上听英语歌成功实现快速入睡，结果大概 4 点醒了，看手表看到 4，被大脑自动映射成了 14 点，以为 2 点就醒了，后来在半昏迷状态中听到 6 点的整点报时，整笑了。
状态还算比较好，可能是清晨的空气过于寒冷了，在广大附门口集合，听说尼斯昨晚 4 点发烧了，祝他好运（？），这么多 4 到底暗示了什么？
晃晃悠悠进场并罚座，努力使自己平静，以便在过度紧张的情况下降智。很快啊，8:27 给到了解压密码 [email protected]:dream。发现大样例大小很小，打开pdf并通篇阅读，贪+计+？+ds，有不详的预感了。
开 \texttt{T1}，在经过几个纯比赛开始时脑抽的思考后，发现其实策略一定是最小的 x+y 选和 x 选，那么可以直接枚举选前 i 小的 x，然后算出最小的 x+y 可以贡献多少。这个直接通过了大样例，不放心试图用 x 很小 y 很大卡掉，发现这样一定不会选更大的 x+y，那不对完了。
然后看 \texttt{T2}，读完，懵了，这是能计数的东西？再读，这等价于要求错误的性价比背包贪心和正确的背包结果相同，不是这是人类？先跳了。
感觉 \texttt{T3} 友善一点，手玩样例觉得可以让每个非叶子节点取到叶子节点的 \mathrm{mex}，进一步可以扩展成其儿子节点的权值 \max+1，对着这个 \mathrm{dp}，结果 tree2 答案全部都小了，手玩发现其实子树可以用于增加某个点的权值，这个非常巨大难写，挂了一堆细节，非常痛苦地调过了样例，测 tree2 竟然直接对了，以为要赢了，结果 tree3 再次全部小了。道心破碎，这我玩个鸡毛。跳了，暴力都不打了。
狂暴撰写，没想到这个都能让我调试，调了半天还没找到问题，整个人非常红温，结果发现是背包写成恰好为 $m$ 了，改完对了，想骂人。
回去做 $\texttt{T4}$，想完分治怎么做已经 $12:40$，来不及了，破防了，写完 $5$ 分暴力之后结束了。
出来看大家脸色都不好，问了一圈没有人过 $\texttt{T2}$，全都打了暴力，不过省集域和乐乐似乎通过了 $\texttt{T2}$，心情很差，没怎么逗留就出去了。
估分应该是 $100+25+\epsilon+5$，$\texttt{T3}$ 的假做法不知道能脏到什么分。
你告诉我 黄紫嘿嘿？
[退队倾向]
**upd:**
最后是 $100+24+0+20=144$，恰好卡线 $\texttt{GD}$ 一等线狗到了一等。
赛后总结，发现 $\texttt{T3}$ 赛时的思路大体其实是对的，不过并不是只有选子树这种贡献方式，可以任意选一些点来为上面的点贡献，因此扩展到三维 $f_{i,j,k}$ 就是对的了，这样就有 $48$ 了。$\texttt{T4}$ 赛后立刻复刻了赛时想到的那个分治，直接拿到了 $75$，赛时甚至以为这个只有 $30$ 分左右。若是全部都分析到了，应该是 $100+24+48+75=247$，赛时的策略还是要更正。