LibreOJ Round #6
T1. 花煎
25
$k \le 10$
打表。
50
$k \le 500$
暴搜。
一个环旋转后的色彩值不变，不妨固定元素 $1$ 和 $\frac{n}{2} + 1$ 为对立元素。
根据定义，环一定是对称的，因而 $m = k^2$ 中的 $k$ 即表示 $[1, \frac{n}{2}]$ 半圆内所有被对立元素分隔的子段的长度之积。
假设所有子段长均为 $x$，那么可以通过 $(x + 1) \cdot (\lceil \log_x k \rceil + 1)$ 个元素构造出一个符合条件的半圆，取 $x = 3$ 得到最低的上界 $(3 + 1) \times (6 + 1) = 28$，因而在 $k \le 500$ 时最优解中半圆的大小不会超过 $28$。
枚举半圆的大小及半圆上的每个元素是独立还是对立，计算每种方案的色彩值。
时间复杂度 $\mathcal O(2^{4 \cdot \lceil \log_3 k \rceil + 1}) \approx O(k^{2.52})$。
65
$k \le 5000$
背包。
找到一个由正整数组成的可重集 $\{ x_i \}$，其中每一个元素 $x_i$ 对应一个长度为 $x_i$ 的子段，使得 $\prod x_i \ge k$ 且 $\sum (x_i + 1)$ 尽可能小。
将 $\prod x_i \ge k$ 两边取对得 $\sum \ln x_i \ge \ln k$，这是一个完全背包问题的模型：对于每个正整数 $x$，有一种数量无限、体积为 $x + 1$、价值为 $\ln x$ 的物品，一个物品实际上对应一个长度为 $x$ 的子段，其占用 $x + 1$ 个半圆上的元素。
答案为使得总价值不小于 $\ln k$ 所需的最小体积。
时间复杂度 $\mathcal O(k^2)$。
100
$k \le 10^{18}$
几个结论：
- 长度为 $\mathbf{0, 1}$ 的子段不出现
- 长度为 $\mathbf{2}$ 的子段出现不超过一次
- 长度为 $\mathbf{3}$ 的子段出现不超过四次
- 长度为 $\mathbf{5}$ 的子段出现不超过一次
- 长度大于等于 $\mathbf{6}$ 的子段不出现
综上所述，一个最优方案可以只由长度为 $2, 3, 5$ 的子段组成，且数量极少，枚举它们的个数 $c_2 \ (\le 1), c_3 \ (\le 4), c_5 \ (\le 1)$，计算达到要求额外需要的乘积。
\[k' = \left \lceil \frac{k}{2^{c_2} \cdot 3^{c_3} \cdot 5^{c_5}} \right \rceil\]添加 $\lceil \log_4 k’ \rceil$ 个长度为 $4$ 的子段便能达到要求，对于所有的情况取答案的最小值即可。
继续优化：
- 长度为 $\mathbf{2}$ 的子段不和长为 $\mathbf{4}$ 的子段同时出现
- 长度为 $\mathbf{5}$ 的子段不和两个长为 $\mathbf{4}$ 的子段同时出现
预处理使得这种方案出现的最小值（这个值不大于 $2 \times 3^4 \times 4 \times 5 = 3240$）以内的答案，大于该范围的只枚举 $3$ 的个数即可。
时间复杂度 $\mathcal O(\log k)$。
T2. 花团
15
$q \le 18, v \le 15000$
暴搜。
任意时刻的物品数 $n = \mathcal O(q)$，枚举每个物品是否选择计算答案。
时间复杂度 $\mathcal O(2^q q)$。
35
$q, v \le 1000$
背包。
记 $f(i, j)$ 表示在前 $i$ 个物品选择，总体积为 $j$ 的最大价值。
\[f(i, j) = \max(f(i - 1, j), f(i - 1, j - v_i) + w_i)\]即 $f_j = \max f_{j - v_i} + w_i$，当 $n \gt v$ 时可以预处理每种体积的最大值。
时间复杂度 $\mathcal O(q v \min(q, v))$。
51
$T = 0$
std::bitset 优化第一问。
时间复杂度 $\mathcal O(\frac{q v \min(q, v)}{w})$。
75
$q, v \le 10000$
$T = 0$
线段树分治。
时间复杂度 $\mathcal O(q v \log q)$。
100
$q, v \le 15000$
$T \in \{ 0, 1 \}$
在线线段树分治。
时间复杂度 $\mathcal O(q v \log q)$。
T3. 花火
6
$n \le 4$
深搜。
17
$n \le 8$
广搜。
状态数为 $2 \cdot n!$，每个状态有 $C_n^2$ 个扩展。
时间复杂度 $\mathcal O(n! n^2)$。
33
$n \le 100$
两个性质：
- 总是可以假设交换不相邻元素在第一次进行。
- 如果已经交换了不相邻元素，之后的最小交换次数等于此时排列的逆序数。
$\mathcal O(n^2)$ 暴力枚举交换第一步哪两个元素，对每种第一步的交换 $\mathcal O(n^2)$ 计算逆序数。
时间复杂度 $\mathcal O(n^4)$。
41
$n \le 300$
使用归并排序或树状数组优化求逆序对。
时间复杂度 $\mathcal O(n^3 \log n)$。
54
$n \le 700$
每次只有两个元素发生改变，没必要整个数列再求一遍逆序对。
首先求出初始排列的逆序数 $A$，然后枚举第一次交换的数对 $(i, j)$（$i \lt j$），即交换了 $h_i$ 和 $h_j$，只有形如 $(i, x)$（$i \lt x \lt j$）和 $(x, j)$（$i \lt x \lt j$）的数对顺序性发生改变，则新排列逆序数为
\[A' = [h_j \gt h_i] - [h_i \gt h_j] + \sum_{x = i + 1}^{j - 1}([h_j \gt h_x] + [h_x \gt h_i] - [h_i \gt h_x] - [h_x \gt h_j])\]- 若 $h_i \lt h_j$，则 $A’ = A + 1 + \sum_{x = i + 1}^{j - 1} 2 [h_i \lt h_x \lt h_j]$；
- 若 $h_i \gt h_j$，则 $A’ = A - 1 - \sum_{x = i + 1}^{j - 1} 2 [h_j \lt h_x \lt h_i]$。
显然对每种第一次交换的情况可以 $\mathcal O(n)$ 暴力计算出新排列的逆序数 $A’$。
时间复杂度 $\mathcal O(n^3)$。
61
$n \le 2000$
交换 $h_i \lt h_j$ 的数对 $(i, j)$ 是不优的，只需考虑满足 $h_i \gt h_j$ 的数对。
把每个元素 $h_i$ 看成二维坐标系中的一个点 $(i, h_i)$，那么对于每一对 $(i, j)$（$h_i \gt h_j$），计算 $\sum_{x = i + 1}^{j - 1} [h_j \lt h_x \lt h_i]$ 就是统计以 $(i, h_i), (j, h_j)$ 为左上角和右下角且边平行与坐标轴的矩形内有多少个点。
这是一个经典的二维数点问题，用可持久化线段树或者离线之后树状数组即可解决。
时间复杂度 $\mathcal O(n^2 \log n)$。
67
$n \le 6000$
数据结构学傻了。
使用二维前缀和 $\mathcal O(n^2)$ 预处理，$\mathcal O(1)$ 查询。
时间复杂度 $\mathcal O(n^2)$。
100
$n \le 300000$
对于两个左端点 $l_i \lt l_j$，其对应最优的右端点满足 $r_i \lt r_j$，即决策单调性。
直接分治转移，每次转移中点并递归到左右两侧，另外用一棵树状数组维护当前转移区间内的区间和，使用宽度优先顺序转移即可保证转移区间的端点移动总次数为 $\mathcal O(n \log n)$。
时间复杂度 $\mathcal O(n \log^2 n)$。
T4. 花札
9
$m = c = 1$
所有牌都一样，谁的牌多谁赢。
时间复杂度 $\mathcal O(n)$。
19
$n_1, n_2 \le 10$
状压 DP。
时间复杂度 $\mathcal O(2^n n^2)$。
30
$m, c \le 2$
最多只有 $4$ 种牌，分别记录每种牌的数量 DP。
时间复杂度 $\mathcal O(n^{m c})$。
55
$n_1, n_2 \le 400$
对每张牌建一个点，向能够作为它后继的点连边，形成一个二分图，不妨设神犇的 $n_1$ 个点在左侧，LCR 的 $n_2$ 个点在右侧。
初始时在二分图的一个点上，两人轮流沿着边走，不允许重复访问节点，不能移动者输。
要求左侧每个点是否一定在最大匹配上，考虑删去这个点后求最大匹配看答案是否减小。
时间复杂度 $\mathcal O(n^{3.5})$。
69
$n_1, n_2 \le 1000$
考虑一个在匹配上的点 $v$，要判断是否存在以 $v$ 为一端的偶数长度交替路，可以删去点 $v$ 并从 $v$ 原来的匹配点开始找增广路，若能找到则存在。
时间复杂度 $\mathcal O(n^3)$。
84
$n_1, n_2 \le 4000$
为了减少边数使用网络流模型，对每个颜色和点数建立一个点，这样只要连 $\mathcal O(n)$ 条单位边，点边和边数都是 $\mathcal O(n)$ 的，Dinic 算法可以获得很高的运行效率
用退流来判断一个点是否一定在最大匹配中。
时间复杂度 $\mathcal O(n^2)$。
100
$n_1, n_2 \le 40000$
一个点 $i$ 一定在最大匹配中等价于在某个最大流中 $S$ 到 $i$ 的边有流量，且残量网络上不存在 $S$ 到 $i$ 的路径，只需在残量网络上从源点开始搜索能到达的点即可。
时间复杂度 $\mathcal O(n^{\frac{5}{3}})$。