20220809NOI模拟赛

时间安排

7:30–7:35 读题。T1目测是个建图或者DP，T3貌似做一下高位前缀和就行了。

7:35–9:00 T3,忽然感觉以前做过类似的，比较一下1的个数，那么这样就是$m\times 2^n$ 的，只能拿到 50 分，100 分应该是什么更进一步的优化。

9:00–9:40 T2,考虑 $n^2$ 怎么做，发现不知道怎么做，有一个显然的 $n^3$ DP,但是好像没法扩展到 $n^2$。

9:40–10:20 T1,感觉是要建图的，不过还不知道怎么建，考虑先状压拿部分分，貌似可以插头 DP ，不过数据范围有点大，插头应该不是正解。直接做的话要分讨一下，转移感觉很麻烦，先看T2、T3.

10:20–11:30 看T2，T3。T2 貌似可以取最长上升子序列骗一下，但是随机情况下可能达不到要求。

11:30–12:00 T1,猜了几个结论都挂了。

回顾&反思

T1: 果真是建图，发现垂直的边必然要选一个，且这是合法的充要条件，于是跑最小点覆盖就行了。比赛的时候完全没注意到这个性质。感觉好多这种题都是对边或者点建二分图跑最小点覆盖或者独立集什么的，经典的就是发现有关系的两个点不能都选什么的。要做一做这种建图的题。

T2: 乱搞构造。话说 jsy 竟然用最长上升子序列乱搞过了 60，将两两分为一组，这样只要求n的上升子序列，而期望情况下最长上升子序列是 $\sqrt{N}$ 的，这道题 $N=n\times (n+1)$ ，正好。正解的话，将 $n\times (n+1)$ 个数分成 n 组，每次取次大值最大组取最大和次大并将改组删去，并删去其他剩余组的当前最大，统计当前次大最大值，如此循环，这样每组选 2 个，易归纳得有解且满足题意。

T3: 比赛时只对 1 的数量考虑了，这样只能将指数缩减 $\frac{1}{2}$ ，换个角度考虑，每一位要么都是 0，要么都是 1 ,要么一个 1 一个 0 ，分别看作不同的元素计数，分别做就可以降到 $\frac{1}{3}$ 。