日记

终于复活啦！！！

Cheater# Link to

我们设最终 $b$ 中 $[1,mid]$ 的会被删完，$a$ 中 $[1,n - mid + 1]$ 会被删完。

考虑何时这个 $mid$ 合法。显然，如果有 $\min\limits_{i = 1}^{n - mid + 1}a_i > \min\limits_{i = 1}^{mid}b_i$ 时删的完。

考虑反证。显而易见的有当且仅当 $\min\limits_{i = 1}^{n - mid + 1}a_i < \min\limits_{i = 1}^{mid}b_i$ 非法。因为这样那个最小值死活都不可能被删了。

看到这个 $mid$ 就该想到二分。但是在二分之前我们还得先证明以下单调性。也就是说当一个 $mid$ 合法时 $mid + 1$ 也一定合法。我们发现当 $mid$ 增加时，$\min\limits_{i = 1}^{n - mid + 1}a_i$ 单调不降，$\min\limits_{i = 1}^{mid}b_i$ 单调不增。得证。

考虑有交换的情况。我们发现，对于 $i \in [1,n - mid + 1]$，如果有 $a_i < \min\limits_{i = 1}^{mid}b_i$，我们可以通过交换把他扔出去，前提是外面有比 $\min\limits_{i = 1}^{mid}b_i$ 大的。我们记录一个 $cnt1$ 表示有多少个 $a_i < \min\limits_{i = 1}^{mid}b_i$，$cnt2$ 表示外面有多少个比他大的。那么当一个 $mid$ 合法，当且仅当 $cnt1 \le 1 \wedge cnt2 \ge cnt1$。于是直接二分最小的 $mid$，$n - mid + 1$ 就是答案。

Two Arrays# Link to

我们考虑每个数。对于每个没出现的数，显然不会造成贡献。对于每个只出现 $1$ 次的数，永远造成 $1$ 的贡献。对于出现 $2$ 次及以上的数，可以造成 $\le 2$ 的贡献。但是经过一番手玩，我们发现这个 $2$ 的上界似乎是一直可达的，于是这题就变成了一道构造题。

我们对于每个 $a_i \leftrightarrow b_i$ 建一条无向边。确定位置的过程就是在给他定向。一条 $u \to v$ 的边就代表 $a_i = u,b_i = v$。于是我们就想把每个度 $\ge 2$ 的点都构造成至少一进一出的状态。

我们掏一颗 dfs 树出来，对于一条树边，他就是正向的。也就是说我从 $u$ 走到 $v$ 的这条树边定向就该是 $u \to v$。反之就是反向的，应该是 $v \to u$。我们发现这样构造的话，除了根节点的其他点都基本是合法的。如果根节点不合法，我们就翻转它的一颗子树里的所有边就是了。

LCM# Link to

我们钦定 $A_1 \le A_2$。我们发现 $A_3$ 应当属于 $[A_2,A_1 + A_2]$，因为 $\operatorname{lcm}(X_1,X_2) \in [X_2,X_1 \times X_2]$。于是我们就能判无解了。剩下的都是有解的情况。

• $A_3 = A_1 + A_2$
  我们显然想让 $X_3 = X_1 \times X_2$，我们构造一个 $X_1 = 6 \times 10^{A_1 - 1} + 1,X_2 = 6 \times 10^{A_2 - 1}$ 就可行了。
• $A_3 \le A_1 + A_2$
  构造一个 $X_1 = 10^{A_1 - 1},X_2 = 10^{A_2} - 10^{A_1 + A_2 - A_3 - 1}$ 就行。

Dot Product# Link to

设 $c_i = \frac{a_i}{b_i}$。当所有 $c_i$ 相同时显然无解。

设我们找到了一对 $i,j$ 满足 $c_i < c_j$。我们可以构造 $x_i = -(a_j + b_j),x_j = a_i + b_i$。其余都是 $0$。

为何正确？
自己推柿子去。

Movie Theater# Link to

我们发现，对于两个不包含的区间，他们做出的贡献总是固定的。贡献可变的总是那些相互包含的。

设 $i$ 包含了 $j$。那么我们想让 $ans_i$ 比 $ans_j$ 大，那么我们就从 $i$ 向 $j$ 建边。建完发现是个 DAG，我们直接拓扑排序。至于字典序最小，用个大根堆就是了。

为啥不用小根堆呢？

Cheerleaders# Link to

我们发现，“某几条边界上不存在点”的情况是好求的。因为只有 $4$ 条边，我们直接暴力容斥。枚举删除哪几条边就是了。

事实证明：有些时候用“类反演”的思维理解容斥好一点，有些时候就是真容斥。

Frogs# Link to

这题更是重量级。

我们口胡一下，发现只有 $\gcd(a_i,m)$ 的倍数的点会被选。你以为这就可以开始容斥了吗？其实不然。

我们发现 $\gcd(a_i,m)$ 一定是 $m$ 的因数（这不废话吗），而 $[1,10^9]$ 里因数最多的也就 $1500$ 多个因数。我们枚举每个因数，对于第 $i$ 个因数，我们记录一个 $val_i$ 表示它做出贡献的系数。每当我们计算完一个因数的贡献，我们就把它的倍数的 $val$ 减去一个 $val_i$。

根本就不是容斥，你被骗啦！

后日谈 # Link to 后日谈

今天似乎是有点颓废的，但是却做了这么多题。今天除了补好题还有数论，我还水了两道网络流。

今天到底颓不颓呢？