当前位置：网站首页>2022/8/9 考试总结

2022/8/9 考试总结

2022-08-09 22:10:00 【迷蒙之雨】

T3好像写过，想了一会会了，写的挺顺的，顺带卡了卡常数。

T1给我的直觉是最小割，但是想了一会不知道怎么建图。
后来想了想写了个状压dp，插头dp可以拿到55，但是似乎比较麻烦。

随机数列的lis的期望是 $\sqrt n$ ，但是这个题要求构造的 $2\sqrt n$
写了一下发现的确有的时候会被卡。
自闭。

T2想了个神奇的构造，找出n组，从整体来看，每组单调上升，但是每组内部可以降序。
似乎随机的话都能构出来。希望出题人不回卡这种做法。
因为要输出方案，实现起来很复杂，一开始写的时候还要树套树，后来优化到了 $O(n^2)$
大概可以有70pts

写插头dp，但是没有调出来。

考场降智。第一直接是最小割是对的，不过一直想不到怎么建图。
看来还是二分图和最小割建图不太熟，不过55的插头dp没写出来不应该。
要刷一点最小割的题。

神仙的构造。
把原序列分成 $n$ 块，每次选一个次大值最大的块，把这个块的最大值和次大值选中，然后把这个块删除。然后把其他块的最大值删除。
可通过归纳证明这样构造符合题意。
然后用个堆维护就可以做到 $n l o g n$

版权声明
本文为[迷蒙之雨]所创，转载请带上原文链接，感谢
https://blog.csdn.net/jwg2732/article/details/126254879