| Problem | CodeForces | luogu | 题解页数 |
|---|---|---|---|
| A | A - CodeForces | A - luogu | 2 |
| B | B - CodeForces | B - luogu | 3 |
| C | C - CodeForces Gym | 2 | |
| D | D - luogu | 5 | |
| E | E - luogu | 3 | |
| F | F - CodeForces | F - luogu | 2 |
| G | G - CodeForces | G - luogu | 6 |
杂题选讲课件里的第18~19页。
你会发现有个事情...
你其实不需要维护 $3 \times 10^5 \times 10^9$ 个数据，因为每次1，2操作后只可能有该段的第一个数成为全局最小值。因此你只需要维护 $3 \times 10^5$ 个数据。
如果把所有数据都看作平面直角坐标系中的点，如果下标是 $i$ 值是 $a_i$ 对应点就是 $(i-1,a_i)$，题目就变成了：
动态维护下凸壳即可。
注意：
It is solved.
杂题选讲课件里的第11~12页。
引用Rain-chr的一句话：
相当困难的网络流题。
相信学过网络流的同学都猜到这是个二分图。这题建图有点奇怪，点数最大能达到 $8 \times 10^5$。
怎么建图？我们发现不可能有L形，也就是...
将原图每相邻两个 # 之间的边看作建图后的点，若建图后两个点对应原图中一个正方形内的相邻两边，则这两条边不能同时选中！
在原图中，一条边被选中即意味着把这条边两边的正方形放到同一长方形中。因此，正方形相邻两边不同时选中等价于不存在L形，也就是符合题目条件。
要让长方形个数最少，就要让选中的边数尽量多，因此最佳方案显然是二分图最大独立集！
最终答案为原图中 # 的个数减去二分图最大独立集。
注意点数最大能达到 $8 \times 10^5$，因此用Dinic+当前弧优化！！！
It is solved.
杂题选讲课件里的第25~26（26~27）页。
比如说这些点：$A(0,0),B(1,1),C(3,2),D(2,3),E(-2,4),F(5,6)$。如图所示，在红色 $\color{#FF0000}\triangle ABC$，绿色 $\color{#00FF00}\triangle BEF$，蓝色 $\color{#0000FF}\triangle CDE$ 三个三角形中分别找出斜率绝对值最小的边，可以发现分别是 $BC,EF,DE$。我们发现斜率绝对值最小的边两个端点的纵坐标总是相邻的，比如说 $\color{#00FF00}\triangle BEF$ 中 $B,E,F$ 的纵坐标分别为 $1,4,6$，那么称这个三角形中，$B,E$ 的纵坐标相邻，$E,F$ 的纵坐标相邻。根据以下式子：
$$ \frac{a}{b}<\frac{c}{d} \Rightarrow \frac{a}{b}<\frac{a+c}{b+d}<\frac{b}{d} $$
因此若两个点 $A,C$ 纵坐标不相邻，中间有点 $B$，那么 $AC$ 的斜率一定介于 $AB$ 和 $BC$ 的斜率之间，从而不可能成为最小值。
因此，斜率绝对值最小的点对纵坐标一定相邻，用莫队维护相邻点对的斜率集合即可。
对 $x$ 坐标莫队，按照 $y$ 坐标对点排序并维护相邻点对的斜率集合。单次修改是 $O(\log n)$ 的，将块大小设为 $O(\frac{n}{\sqrt{q}})$ 即可做到 $O(n \log n \sqrt{q})$。
——https://xinyoudui.com/courses/1700/all/#/pages/58464 第26~27页
\sqrtqwq/
It is solved.
推公式题。
首先我们...想到一个事情。题目中 $a_i \operatorname{bitand} a_j \ge \min(a_i,a_j)$ 是什么神奇条件？
根据 $\operatorname{bitand}$ 的性质，显然 $a_i \operatorname{bitand} a_j \le a_i,a_i \operatorname{bitand} a_j \le a_j$，因此 $a_i \operatorname{bitand} a_j \le \min(a_i,a_j)$。居然不等号方向反了！
因此有 $a_i \operatorname{bitand} a_j = \min(a_i,a_j)$。还是看不出什么来...
不过如果有 $x \operatorname{bitand} y=x$，那么把 $x$ 二进制中为 $1$ 的位置下标看作集合 $X$，$y$ 二进制中为 $1$ 的位置下标看作集合 $Y$，那么 $X \subseteq Y$。其中 $2^0$ 到 $2^n$ 位的下标分别是 $0$ 到 $n$。
例如 $0,1,2,6,7$，那么 $(x,y)=(0,1),(0,2),(0,6),(0,7),(1,7),(2,6),(2,7),(6,7)$ 均满足条件（假定 $x < y$）。
考虑DP每个数分别要装在第几个箱子里，因为这是一个DAG（有向无环图），所以对它拓扑排序后按每条边转移即可。其实拓扑序就是原数从小到大的顺序。
但是边数太多了qwq！
为了让边数更少，我们发现上文中 $(x,y)=(2,6),(2,7),(6,7)$ 明显存在冗余，$(2,7)$ 是一条无用边，所以拓扑排序后只考虑有用边即可。
但是判定有用边就会超时！
怎么办？我们想到如果有一个输入是这样子：
1048576
0 1 2 3 4 5 6 ... 1048575那谁看了都笑。这有用边就是 $x$ 与 $y$ 只差 $1$ 位的 $(x,y)$！
如果把输入转化成这个样子，那么就可以轻松解决。可不可以...
仍然是DP每个数分别要装在第几个箱子里，下标是 $0$ 到 $2^{20}-1$。这次，转移方程如下：
$$ dp_i=\max_{j}(dp_j)+v_i $$
其中 $j$ 为 $i$ 在任意为 $1$ 的二进制位变为 $0$ 后的值，$v_i$ 表示 $i$ 是否在输入中。
举个栗子。假设输入为：
5
0 1 6 7 2此时 $dp_3=v_3+\max(dp_1,dp_2)=0+\max(1,1)=1$。
$dp_7=v_7+\max(dp_3,dp_5,dp_6)=1+\max(dp_3,dp_5,dp_6)$。
稍加计算可得 $dp_7=1+\max(1,1,3)=4$。
It is solved.
这跟Asadashino有何关系？
先看奇怪的女装（简称nz）。
当我们进行nz操作后，原序列将会变为：
| 原 | $a_l$ | $a_{l+1}$ | $\cdots$ | $a_{p-1}$ | $a_p$ | $a_{p+1}$ | $a_{p+2}$ | $\cdots$ | $a_{r-1}$ | $a_r$ |
|---|---|---|---|---|---|---|---|---|---|---|
| 新 | $a_p$ | $a_{p-1}$ | $\cdots$ | $a_{l+1}$ | $a_l$ | $a_r$ | $a_{r-1}$ | $\cdots$ | $a_{p+2}$ | $a_{p+1}$ |
仔细看将会发现这相当于把原序列整体旋转加整体翻转。由于整体翻转不影响查询结果，因此可以简单看做整体旋转。
旋转+旋转=旋转，因此任意多次nz都可以合并为 $1$ 次。
再看诗乃序列。
我们希望维护任意区间的最长相同子段。
根据线段树的基本思路，我们可以维护任意区间的最长相同前缀子段、相同后缀子段和相同子段。同时要维护区间的最左端值和最右端值。
此题线段树比较难写...核心代码
询问时，如果 $k=0$，直接输出最长相同子段；$k>0$ 时，如果最左端值与最右端值相等，最终结果还要与最长相同前缀子段+最长相同后缀子段取max。
需要保证最终结果不超过询问区间长度。
我调线段树调了 $3$ 个小时qwq
It is solved.
我估计没有谁会第一眼想到长链剖分。
考虑第一条边如何加。
因此：
若将树拆成链并像树链剖分一样计算 $top_i$，那么一条链的贡献就是 $dep_l-dep_{top_l}+1$。其中 $l$ 是叶子节点。
长链剖分，将所有叶子节点的 $dep_l-dep_{top_l}+1$ 丢到优先队列中，第一次取最大的一个，然后每次取最大的两个计算减少的割边数即可。、
It is solved.
有没有感觉...像4.6模考题虚无缥缈（异或线性基）和2.8模考题铁路突击（欧拉回路）！
的确很像，但本次作业题和异或一点点关系都没有，而是类似gcd基的问题。
给定有向带权图，若干次询问，每次给出 $v,s,t$，问是否存在经过 $v$ 的回路权值 $\equiv t − s \pmod t$。
经过 $v$ 的回路？
因为这个有向带权图是静态的，所以可以求出其强连通分量，之后任意给定 $v$，经过 $v$ 的回路一定在 $v$ 所在的强连通分量中！
（以下的讨论都在 $v$ 所在的强连通分量中进行。）
可以发现，只要有一个经过 $v$ 的回路权值 $\equiv a \pmod t$，那么你可以走这个回路 $t$ 次，得到一条权值 $\equiv 0 \pmod t$ 的回路。你也可以走这个回路 $t-1$ 次，得到一条权值 $\equiv -a \pmod t$ 的回路。
又可以发现，同一强连通分量中若存在一条从 $x$ 到 $y$ 权值 $\equiv a \pmod t$ 的路径，则必然存在一条从 $y$ 到 $x$ 权值 $\equiv -a \pmod t$ 的路径。很简单，一定存在一条同时经过 $x$ 和 $y$ 的回路。从 $y$ 开始沿回路走 $t$ 圈，走完之后往回“退”到 $x$ 的位置（也可以理解为在最后一圈时只走到 $x$ 就结束）。容易证明这条路径权值 $\equiv -a \pmod t$。
那么，对于点 $v$，若强连通分量中存在一个权值 $\equiv a \pmod t$ 的回路，则可以从 $v$ 出发：
因此，根据裴蜀定理，记 $g$ 为该强连通分量中所有环权值的gcd，那么在模意义下，回路权值可以且仅可以取到 $g$ 的倍数。
如何求 $g$？
- 初始时 $g \leftarrow 0$。
- 求出原强连通分量中的任意一个dfs树，并计算每个点的高度（从dfs树根节点到该点的树上路径权值），点 $v$ 的高度记为 $h_v$。
- 对于任意边 $(u,v)$，计算 $h_u-h_v+l_{(u,v)}$ 并与 $g$ 取最大公约数。其中 $l_{(u,v)}$ 表示边 $(u,v)$ 的权值。
这样，当 $(u,v)$ 是dfs树的边时，其结果为 $0$，不影响 $g$；否则：
我们实际上计算了一个通过 $(u,v)$ 的回路的权值。由于任意回路都至少要经过一条非dfs树的边，就可以将这条回路拆解为多条，每条只通过一个非dfs树的边，权值同样是 $g$ 的倍数。
最后，看 $s$ 是不是 $\gcd(g,t)$ 的倍数即可。
It is solved.
| Problem | CodeForces | luogu | 洛谷题解 |
|---|---|---|---|
| A | A - CodeForces | A - luogu | A |
| B | B - CodeForces | B - luogu | B |
| C | C - CodeForces Gym | Not Found | |
| D | D - luogu | D | |
| E | E - luogu | E | |
| F | F - CodeForces | F - luogu | F |
| G | G - CodeForces | G - luogu | G |