2025/9/10 | 2025CSP-S模拟赛57
https://oj.gxyzh.com/d/hzoj/contest/68d921a11bde45b9248e2bb9/problems
国庆第一天训练。初三牲要死了。搬到机构里训练,效率几乎为零。
T1其实是简单题。但是考场上想了AB性质后就没有想法了,就是把这串数的最终结果求出来,然后给每个原数匹配一个最终数。答案是每个数的增加量乘bi的一种排列的最小值。当时也想到了增加量最大的匹配小的bi的。但是因为一些原因不能直接简单地将原数和最终数匹配(比如必须满足最终数大于等于原数)例如原数列为1 2 2 5,最终数列为1 2 3 5,显然就不能直接将1和5匹配,这样子最后一个5就没的匹配了。
所以我们考虑换个思路 从大到小匹配,在最终数列里面找到第一个大于等于当前数的数字即可。这样就能满足要求了。
T2,当时写了个O(n2)的dp(真的应该是严格的n2啊),但是只能获得O(n^3)的30pts,非常气愤却无果。正解首先是要观察到一个性质,就是最终划分的mex只有一种,这个mex就是全局的mex。证明不说了。然后原来那个dp式子就能写的很简单了。设dp[i]表示以i结尾的划分方案数,如果能满足mex[j][i]等于全局的mex i就能从j转移过来,然后会发现能转移过来的j一定是一段前缀(因为全局的mex一定是大于等于局部的mex的),而且这个前缀也是单调不降的。用单指针求出每个i对应的最右边的j,转移用前缀和优化即可。
T3感觉是很神奇的一道题,它需要用到一个知识点:Kruscal重构树,因为这个树有一个性质就是,任意两点的lca就是他们原图中路径上最大边权最小值。但是我学到的这种解法非常简单直白啊(我总感觉它并不是真正意义上的Kruscal重构树),就是建两棵树,满足如果i是j的祖先i就一定是i到j这条路径上的最大/最小值,然后两棵树各跑一遍,统计在第一棵树里i是j的祖先且在1第二棵树里j是i的祖先的对数即可。