[总结]2023-7-6A组模拟赛
P1 心路历程
看完题之后发现：唉，好像简单了一点。
然后就开始想T1。一开始以为是DP，发现不好转移。不知道为什么脑子里面一直在想二维偏序，之后就往数据结构方面想。
我发现：一个点，绝对不可能从后面走回来。类似于这样：
之后就想到：如果是这样，那么到一个点路程花费时间是一定的。所以可以枚举每一个点作为终点。然后在选它和在它前面的一些点。显然：选出来的点必定是总体的前 \(k\) 大，否则不会更优。那么就可以二分一个 \(k\)，然后写个平衡树，查询第 \(k\) 大，之后再用个数据结构查询前 \(k\) 大的点的 \(t_i\) 的和，即 \(\sum _{\text{rank}_i\le k} t_i\)，用于判断加上路程之后是否大于 \(m\)。
在前 \(k\) 大的和那里想了很久。然后发现可以用权值树状数组，前 \(k\) 大的数一定在树状数组中对应第 \(k\) 大的位置的前面。可以打个离散化，之后写个结构体，把离散化的下标顺便记录在平衡树里。时间复杂度是 \(O(n\log ^2n)\)。
然后由于一些细节问题犹豫了一会，直到9:10，开始敲代码。又要写Splay，不过只用写插入和查询第 \(k\) 小的函数，所以还是比较好写。
到了10:20，终于写完了。样例过了之后有肉眼BASH一会，就去想T2。
一开始以为T2是个结论。之后经过一番看起来很正确的推论之后断定答案是 \(2^{n-1}\)。打了快速幂之后就去看T3。
T3发现题目有点绕，经过几分钟之后的思考，发现要求特定生成树。之后30%就是 \(O(\binom m {n-1})\)；60%想了排序完之后一个类似于双指针的东西。不知道为什么，就开始觉得正解是贪心。大概就是令指针 \(l,r\) 一开始等于 \(\dfrac{m}{2}\)。之后就往两边移动。每次移动都以贪心的思想，看哪边移动完之后贡献更优，就移动那一边。
还以为三题都切了，然后打到一半发现不对劲，贪心是错的。赶紧去打60%，发现60%也假了。之后60%就想了 一个 \(O(m^2)\) 的区间选边之后用并查集维护连通性。打着打着，还以为有一个小时（一开始OJ显示12:50结束），发现只有8min了，赶紧把T1、T2交了（怕罚时）。之后又改了会T3，发现分段暴力的30%挂了，过不了样例，就把30%给注释掉了，只交了60%的（毕竟60%过了样例）。
然后又是看榜环节，依旧从下往上看。发现自己竟然没倒数，但rnk35。
T1是切了，但是也有很多人都切了；但为什么T2只有20pts，T3只有10pts？
P2 赛后总结
交流发现今天的题目不难（有两个人AK），而且T1是我想复杂了，别人一个堆就能过。
这次问题主要是时间分配不合理，花了2h搞T1，导致后面的题没时间想，甚至T4都没有仔细看。这就说明一个问题：对于时间分配的经验不足，而且过于固执搞T1。但凡不肉眼BASH那么久，花多点时间搞T3的60%，写写T4的暴力，也不至于rnk35。
虽说今天切题了（暑假以来第一次）但是不能因此暴力不打满。这样是不对的，这说明我只想冲正解而不去考虑多拿分。这种思想很可怕，特别是会影响到正式赛场上摆烂。
所以，确认自己切了题之后要马上去想其他题，特别是部分分。4道题AC和暴力是并存的，而不是二选一。至于正确性以及其他细节问题，可以再比赛的最后半小时写对拍。这又要求做题速度要快。
P3 题目总结
T1
别人好像是边插入堆里面边查询第 \(k\) 小。不过我觉得考场上手搓平衡树也无可厚非，因为那些明明知道要平衡树而想方设法不写的人就是对知识点不熟练。
不过这种题不应该花太多时间。主要我犹豫在一个 \(t\) 值相等的情况，不知道是合并在一起好还是分开考虑。这次的经验是：分开考虑。因为二分会全部考虑到。
T2
很有趣的DP+结论。显然只用统计大根堆或者小根堆。于是一个有 \(i\) 个节点的树可以有左子树和右子树转移。方程大概是这样：
\[f_i=f_j\cdot f_k \cdot \binom {i-1} {j} \]其中的 \(i,j,k\) 表示节点个数。\(f_j\) 代表 \(i\) 的左子树，\(f_k\) 代表 \(k\) 的右子树。后面那个系数显然是因为：\(i\) 个点选一个来当根，剩下的给左子树或右子树。
好像还有一些枚举优化，还没看。
T3
注意到这样一个事实：一张图中的最小生成树的最大边对于其他生成树中的最大边是最小的。所以这就给了我们一个启示：改一下最小生成树。
可以考虑枚举最小的边，然后把小于它的边删掉，之后求最小生成树，其中找到最大边之后就可以产生贡献。
显然这样是 \(O(m^2)\) 的，是对于60%的。那么考虑优化。根据经验，可以倒过来（即从大到小）枚举最小边，然后考虑加进图里面。分类讨论一下：
- 加入后，产生了环。
- 加入后，没有产生环。
对于后者，直接加入（因为这张图还不联通）。对于前者，我们可以考虑用这条边代替这个环中权值最大的边。这为什么是对的呢？
不妨思考一下Krusikal算法的过程。发现边是从小到大加入的；如果加入前这两个点不连通，就加入。假设这个环有 \(p\) 个点，显然现在必定有方案用 \(p-1\) 条边让这个环中的节点联通。但是现在有 \(p\) 条边，那么现在加入的边显然比所有的边都小，那么必定会选中；那对于原来来讲，必定有一条边会被删除，那就是权值最大的边。
然后你可以用并查集判有没有环，用DFS找环（说实话，我怕爆栈）。
于是乎这个水题改了我一个下午，首先是正确性问题，我发现我找环由于链式前向星的特性（无向边变成两条有向边），以及DFS判断新的点是否是父亲的特性，如果出现一下情况，它会找不到环。
于是就要特判这种情况，具体来说就是：如果发现祖先节点，并且它还是父亲，如果这条过去的边不是之前过来的那条边，就可以走。
之后就是TLE。我开始卡常。发现开了O2也要跑3s。怎么看都觉得那个删边操作不对劲（我是标记删边），之后问了lmz，他说要直接删，不能标记。后面我改了改，删边之后保持了链式前向星的特性就1000+ms了。
写了快读，没用（**快读）；加了register，过了。
我爱卡常！！！
标签：6A,发现,T3,T2,之后,T1,60%,2023,模拟 From： https://www.cnblogs.com/xmtxlym/p/17533262.html