5月杂题

5.7

做了什么：坐飞机，大吃大喝。

P9139 [THUPC 2023 初赛] 喵了个喵 II:

先考虑每个出现两次怎么做，发现只要每对区间不是包含关系即可。

回到此题，相当于要把 4 个数分成两组，有 \(1-2,3-4\) ，\(1-3,2-4\) 两种选法。

2-SAT+主席树优化建图 即可。

5.8

做了什么：模拟赛，发的题，CF。

LOJ6476 「ICPC World Finals 2017」复制，复制，复制并变异 Replicate Replicate Rfplicbte

考虑逆向思考，如何还原到操作前的状态，发现每次找到最后一行中最右的 \(1\) ，设其坐标为 \((x,y)\) ，则在 \((x-1,y-1)\) 放雷，并把周围的 3*3 反转一下。

这样消下去就会剩两行两列，我们发现由之可以直接推出关键点的坐标。

LOJ511

处理字典序的过程是平凡的，问题可以转化成：每个点可选/不选，一些点只能选，一些点只能不选，求独立集个数，对 \(V=10^{18}\) 取 min。并且每次会改变一个点是否能选/不选的状态。

有两种做法，一种是直接传统 ddp。

这种做法非常麻烦，因为还要对每个点的轻儿子建线段树，处理不能除/减。

一种是利用答案和 \(V\) 取 min ，观察到自由点超过 \(2\log(V)\) 时直接输出 \(V\) ，否则暴力 dp。

CF341E

咕。

CF346E

咕。

CF1827D

注意到把 \(j\) 从大往小枚举，\(g\) 会形如 \(O(n)\) 次区间加，然后利用 BIT 维护历史和即可。

5.9

做了什么：改题，做发的题。

CF1798F

一个结论：\(2n-1\) 个数里一定能找出 \(n\) 个，和是 \(n\) 的倍数。

证明：咕。

由此，我们把集合大小从小往大排序，每次直接任取 \(2s-1\) 个剩余的数，做一遍背包构造方案。对于最后一个集合，再补上合适的数。

由此直接 dp 即可。

LOJ3278「JOISC 2020 Day3」收获

发现对于每个人 \(u\)，我们都能处理出：如果某个苹果树被 \(u\) 摘了，则下一个摘的人 \(f\) 是谁。由此可以连出一棵基环树。

每个苹果树能用二元组 \((u,t)\) 表示,意思是 \(u\) 第一个摘，是 \(t\) 时刻摘的。

对于树的贡献，相当于算子树内 \(t+d_u-d_f\le T\) 的二元组个数。二维偏序。

对于环的贡献，设 \(dis(u,v)\) 表示 \(u\) 顺着环走到 \(u\) 的时间，则有 \(T-t-dis(u,f)\) 除以 \(L\) 下取整再加 \(1\) 。可以拆成两遍偏序。

gym102412D

首先可以用文艺平衡树维护序列，现在的难点在于合并信息。

发现如果已经有三元上升，就不需要准确维护信息。

通过讨论发现我们需要处理：一个子树中 \(>z\) 的最小数。因为没有三元上升，\(>z\) 的数一定单调递减，所以直接二分即可。因为平衡树树高 \(O(\log n)\) ，复杂度即为 \(O(n\log^2 n)\) 。

gym102391E

处理最小直径，二分答案。可以对仙人掌建出圆方树。设 \(d_u\) 是使 \(u\) 子树合法的前提下，\(u\) 到最深叶子的距离最小值。dp 一下就好了。实现比较复杂：

就是我们断开的地方，左右分别维护三个信息： \(s,m_1,m_2\) 其中 \(m_1\) 是当前 \(u\) 到当前最深叶子的距离，\(m_2\) 是当前点 \(v\) 到其他点的最远距离， \(s\) 是 \(u\) 到 \(v\) 的距离。

5.10

做了什么：去 jzhx，听线性代数，模拟赛。

CTT2019 D3T2

如果不是环是链，则操作等同于：求出前缀和数组 \(s\) ，交换 \(s\) 的相邻两项。就是求逆序对个数。

现在是环了，我们把原序列无限复制，并设定一个“零势能面”，类似的定义 \(s\) 。设原序列所有数的和是 \(A\) ，则 \(s_{i+n}=s_{i}+A\) 。我们把 \(s_{i},s_{i+n},s_{i+2n}...\) 看成一个系统，则操作等同于交换一对相邻系统的位置。对于两个系统，如果相对应的一对位置有 \(a>b\) ,\(a\) 在 \(b\) 前，则我们需要操作 \(b-a\) 除以 \(A\) 上取整次。拆成两遍二维偏序来算就好了。

5.11

做了什么：去玄武湖玩，做发的题。

CSES2418

咕咕咕。

gym100254F

咕咕咕。

CSES2427

咕咕咕。