UOJ Round #8
A. 赴京赶考
30
$n, m \le 100$
$q \le 10$
使用 0-1 BFS 搜索。
时间复杂度 $\mathcal O(qnm)$。
50
$n \le 10^5, m = 1$
$q \le 10^5$
预处理 $(1, 1) \rightarrow (1, i)$ 和 $(1, i) \rightarrow (1, n)$ 的结果，将 $(1, i) \rightarrow (1, j)$ 和 $(1, j) \rightarrow (1, n) \rightarrow (1, 1) \rightarrow (1, i)$ 的结果取较小者。
时间复杂度 $\mathcal O(n + q)$。
100
$n, m \le 10^5$
$q \le 10^5$
对于 $a_i \neq a_{i + 1}$，无论 $b_j$ 取值，从 $(i, j)$ 穿越到 $(i + 1, j)$ 必然会花费等待时间。
对于 $a_i = a_{i + 1}$ ，必然不会花费等待时间。
所以一条路线的总等待时间可以拆分为各个维度的等待时间之和。
时间复杂度 $\mathcal O(n + m + q)$。
B. 决战圆锥曲线
10
$n \le 100$
$m \le 100$
暴力模拟。
时间复杂度 $\mathcal O(nm)$。
30
$a = c = 0$
查询区间 $y$ 最大值，使用线段树维护。
时间复杂度 $\mathcal O(m \log n)$。
50
$c = 0$
只考虑 $x, y$，显然影响答案的点在凸包上，使用线段树维护上凸壳。
注意存在翻转操作，还要维护区间的下凸壳。
由于数据随机，一个长度为 $n$ 的区间凸包大小是 $\mathcal O(\log n)$ 的，所以在线段树 PushUp 时可以暴力合并凸包，修改操作单次 $\mathcal O(\log^2 n)$。
询问操作可以暴力扫每个子区间的凸包上所有点，带入得到最优值，也是单次 $\mathcal O(\log^2 n)$。
时间复杂度 $O(m \log^2 n)$。
70
$n \le 10^5$
$m \le 2 \times 10^5$
对于一个点 $(x_i, y_i)$，如果存在一个点 $(x_j, y_j)$ 满足 $x_i \le x_j$ 且 $y_i \le y_j$，那么 $i$ 对答案是一定没有影响的。
由于数据随机，一个长度为 $n$ 的区间对答案产生影响的点个数为 $\mathcal O(\log n)$。
使用用线段树来维护区间内对答案产生影响的点集。
时间复杂度 $\mathcal O(m \log^2 n)$。
C. 宿命多项式
10
\[\begin{aligned} & 1 \le a_0 \le c_0 \\ & 1 \le a_0 + a_1 \le c_1 \end{aligned}\]$n \le 1$
对于一个 $a_0$，$a_1$ 有 $c_1$ 种选择，答案为 $c_0 \cdot c_1$。
20
\[\begin{aligned} 1 & \le a_0 \le c_0 \\ 1 & \le a_0 + a_1 + a_2 \le c_1 \\ 1 & \le a_0 + 2a_1 + 4a_2 \le c_2 \end{aligned}\]$n \le 2$
$c_i \le 10^5$
枚举 $c_0$，符合条件的 $a_1, a_2$ 在平面上对应的点为一个平行四边形，问题转化为统计该平行四边形内部整点数。
Pick 定理：给定顶点座标均为整点（或正方形格子点）的简单多边形，其面积 $A$ 和内部格点数目 $i$、边上格点数目 $b$ 的关系：
\[A = i + \frac{b}{2} - 1\]60
$n \le 4$
考虑更换枚举对象，不要枚举系数，而是枚举这个多项式的点值。
每次解方程组时未知数前系数都是不变的，变的只是右边的常数。
把系数矩阵的逆矩阵求出来，会发现逆矩阵中的元素的分母都很小。
由于我们只在乎解是否是整数而不在乎解具体是多少，只要枚举 $f(1), \cdots, f(n)$ 在模其对应分母意义下的值，判断对应的系数是否是整数即可。
时间复杂度 $\mathcal O((n! (n - 1)! (n - 2)! \cdots 1!)^2 \cdot n)$。