2024.11.23 信友队 NOIP 模拟赛

· · 个人记录

11.23 信友队模拟赛

心态炸没的一场，开局 1.5h 一道也不会/kk

t1 写完 + 调完 已经 3h 了，拼手速无脑写了 t2 t3 暴力，最后 t4 暴力没写完...

100+35+32+0=167 遗憾离场（但是 rk10...参加这个比赛的人实在不强

dawn

一坨码力题

考虑到 \min{n,m}\le 18，不妨令 n\le m，可以 2^n 枚举强制哪些行回文。

考虑对称的两列是否回文，枚举把相互影响的四个位置变成每种状态的代价，发现不相互影响的位置相互独立，各自取最小值即可。

实现需要特判奇数时中间的行列，于是一坨。

festival

前 1.5h 想到了一些零碎的点，但是没能结合到一起

key1：从小到大插入每个数

相当于插入之后，LIS 必定 +1，这是非常好的。

key2：状压 LIS 序列

设 f_i 表示前 i 位的 LIS，注意到 f_i-f_{i-1}\in \{0,1\}，故可以状压差分数组表示 f_i。

考虑在 i,i+1 中间插入新的数 n+1 的影响，发现在新的 f'_i 中，只有 f'_{i+1} 会改变，后面的直接平移就可以。

key3：记录 a_i 的顺序

限制 a_i 是 p 的子序列，就是要求 a_i 在 p 中按顺序出现（没有逆序对）。

记 F(i,j,S) 表示加入了 1 ~ i，a 序列中最后一个数的位置是 j ，f_i 的状态为 S 的方案数。

转移时枚举插入的位置，若当前插入的数在 a 中，要求插入位置 >j。

由于 S 一定是 [1,i] 的子集，故状态数是 O(n2^n) 的，时间复杂度 O(n^2 2^n) 完美通过。

mystery

本场比赛看上去最正常的 ds 题目（笑

key：转化条件

查询连续的下标区间，但位置是不连续的，所以要找到对应关系。

考虑 [l,r] 合法等价于从右往左能“多米诺骨牌”式推平：对于 \forall i\in [l,r]，要么 a_i 是最大值，要么 \exist j\in [l,r],a_j<a_i\le a_j+d。

为了方便处理相同元素的影响，我们将条件改写为：要么 a_i 是区间内最大的数，而且是最大值中最靠右的一个；要么存在 l\le j<i,a_i<a_j\le a_i+d，要么存在 i<j\le r,a_i\le a_j\le a_i+d，也就是说我们允许右侧出现相等，但是不允许左侧相等。（因为“链式”操作必须要连在一起）

记 s_i 表示 i 左边第一个在 (a_i,a_i+d] 中的数，t_i 表示右边第一个在 [a_i,a_i+d] 中的数。

扫描线扫 r，考虑对每个 l 的贡献（哪些 l 是不行的）。

对于每个 i，考虑它对 l 的限制。

一个合法的 l 应该是不被任何 i 限制的，可以对每个限制区间 +1，限制解除时 -1，这样答案就是每个点的历史 =0 次数。

发现对于每个 i，限制只会变化 O(1) 次（t_i>r 且后缀最大值 \to t_i>r 且不是最大值 \to t_i\le r），故复杂度 O((n+q)\log n)。

线段树维护历史 min 和出现次数，类似线段树 3 考虑维护历史 tag 最小值，当前 min 出现次数之类，应该能做。

destiny

devans 风格的构造题

众所周知，存在欧拉回路当且仅当图连通且不存在奇点。

key：不许重边 \to 考虑补图

巧妙的，找到补图的一棵生成树，从叶子开始考虑子树中奇点个数，若为奇数，则加入边 (u,fa_u)。

后续把图连到一起是平凡的，构造一些环结构即可。