Solution Set -「LGR-126」洛咕咕的 NOIP 模拟赛

  机房在三楼, 不在五楼.

  三楼确实有阶梯教室.

  三楼向外望是一楼大厅屋顶所以看上去不高.

  十一点前必须离开科技楼是因为爱因斯坦要锁大门.

  我不会被自己写的东西清空 san 值.

  我是兔子.

  Contest link.

\(\mathscr{A}\sim\) 折线

  Tag:「水题无 tag」

  显然答案 \(\ge2\). 若能横向或纵向把点集恰好一刀切成两半, 则答案为 \(2\); 否则若能找到一个右下角或左上角的矩形恰好覆盖点集一半, 则答案为 \(3\); 否则不难构造出 \(4\). 判 \(3\) 可以扫描线 + 数据结构二分或者单调指针维护. 复杂度 \(\mathcal O(n\log n)\), 瓶颈可以做到只有排序.

\(\mathscr{B}\sim\) 冒泡排序

  Tags:「A.DP-计数 DP」「C.性质/结论」

  不妨令 \(f(p)\gets n-f(p)\).

  排列没啥好说的. 对于圆排列, 第一个任务自然是描述给定圆排列 \(p\) 的最小操作次数 \(f(p)\).

  我们知道, 排列上, \(f(p)\) 为 \(p\) 的从 \(p_1\) 开始的最长贪心上升子序列 (LGIS) 长度. 结合这一点, 同时观察样例解释, 我敢打赌, 圆排列上 \(f(p)\) 为 \(\forall i\in[1,n]\), 从 \(p_i\) 开始的 LGIS 长度的最小值. 证明不难.

  呜... 但这个结论并不能转化出方便的计数情景. 再注意到, LGIS 的最后一项必然是 \(n\), 所以直接把 \(n\) 钦定在 \(p_n\), 固定圆排列的同时直接破环为链. 链上问题就好做了, 令 \(f(i,j)\) 表示用 \(i\) 个数排出任意 LGIS \(\le j\) 的方案数. 枚举 \(i\) 个数中最大值的出现位置即可转移. 复杂度 \(\mathcal O(n^3)\).

\(\mathscr{C}\sim\) 动态图连通性 *

  Tags:「A.图论-最短路相关」「B.Tricks」

  好题, 但为了 \(80\text{pt}\) 拼三大坨暴力真的好难受.

  首先转化一下问题, 在离线之后, 我们只需要保留一条 \(1\to n\) 的路径作为最后一条存在的路径. 则这条路径上的边不能 cut, 其他边若存在都能 cut.

  什么叫 "最后存在"? 可以发现, 令 \(S\) 为路径上每条边被 cut 的时间排序后的序列, 则 \(S\) 的字典序对应着路径的存在时间关系, 字典序越大, 存在时间越靠后. 我们只需要求出一条 "字典序最长路" 即可.

  我们先将所有从未被 cut 的边依次 cut 掉, 这是所有边的 cut 时间互不相同. 则令 cut 时间为 \(x\) 的边的权值为 \(2^x\), 字典序最长就变成路径权值和 reverse 后最小. 这样的权值约定是满足 Dijkstra 的需求性质的. 所以我们可以用 Dijkstra 求最短路, 但还剩下最后一个问题, 如何比较权值呢?

  最自然的想法是主席树维护区间 hash 暴力存储权值, 树上二分求二进制最低不同 bit. 一种更优美的方法是在最短路树上求 LCA: 对于两条路径 \(1\to w\to u\) 和 \(1\to w\to v\), 由于边权互不相同, 所以 \(w\to u\) 和 \(w\to v\) 上的边权互不相同, 为了比较字典序, 就只需要比较这两条路径的 \(\min\) 值大小! 这个比较常数巨大, 所以最好用线段树替代 Dijkstra 中的堆. 复杂度 \(\mathcal O(m\log^2n)\).

\(\mathscr{D}\sim\) 线段 *@

  Tags:「A.分治-猫树分治」「B.Tricks」

  不知道该评价是好题还是好 trick.

  猫树分治, 一个区间的贡献在跨 \(\textit{mid}\) 处统计. 对于取交操作, 若其不完全包含 \([l,r]\), 则其会对 \([l,r]\) 产生影响. 讨论若区间跨过 \(\textit{mid}\), 则所有线段左端点会向取交区间取 \(\max\), 右端点类似. 这可以用堆维护 (端点值, 出现次数) 维护. 对于没跨过 \(\textit{mid}\) 的询问, 它会将一些区间丢到更深层的分治区间, 总次数是 \(\mathcal O(n\log n)\) 的. 一个恶心的地方在于, 我们需要维护没跨 \(\textit{mid}\) 的询问对异侧端点的影响, 这里貌似需要手写堆支持全局取 \(\min\) 维护. 总之复杂度就是 \(\mathcal O(n\log n\log q)\).