Solutions

A. Finite or not?

先化简p/q，然后p/q是k进制无限小数的充分必要条件是q中含有k中没有的因子。

求出gcd(q,k)，然后将\(q\)中所有等于这个值的因子去掉，然后再求新的q和之前的gcd的最大公因子，直到不存在1以外的公因子为止。

如果现在q不为1，则说明无限小数。

B. XOR-pyramid

首先可以知道\(f[l][r]=f[l+1][r]\oplus f[l][r-1]\)，可以\(O(n^2)\)算出所有区间的值。

之后将询问按右端点排序离线处理，每当右端点扩展的时候去更新所有左端点处的最值，顺便维护一个左端点的后缀最值，这样就可以\(O(n^2+q\log{q})\)做完所有询问。

C. Elevator

题目大意：一栋 \(9\) 层的楼有一台OO牌电梯，电梯最多容纳 \(4\) 人。现在按照时间顺序依次有 \(n(n\le2000)\) 个请求，每个请求的起点和终点不相同。电梯运行时，要求先来的人必须要先上电梯，但是下电梯的顺序则没有关系。电梯运行一层、每个人进、出电梯分别都需要 \(1s\) 的时间。求最优调度策略下，将所有人送到目的地所需的最短时间。

题解：\(dp\)。

设 \(dp[i][S]\) 表示第 \(i\) 个人刚上电梯，电梯内的所有人的目标楼层的多重集为 \(S\) 这样的状态下花费的最短时间。状态转移即为枚举一个中间楼层，电梯接完第 \(i\) 个人后去往中间楼层，再去接第 \(i+1\) 个人（中间只要有人能下电梯就立刻下）。注意到不会出现先上，再下，再上的情况（如 5-8-1-7），因为无论如何我们都可以把下的操作留到下一次转移，并且不会使结果更坏。

时间复杂度 \(\mathcal{O}(n\cdot9\cdot S)\)，其中 \(S\) 为所有不同的多重集种数。

D. Arkady and Rectangles

题目大意：有一块无穷大的颜色为 \(0\) 的平面，在其上进行 \(n(n\le10^{5})\) 次操作，第 \(i\) 次操作将一块矩形区域染成颜色 \(i\)（会覆盖之前的颜色），问最后平面上有几种不同的颜色？

题解：首先将所有点离散化，按照 \(x\) 坐标建立扫描线，按照 \(y\) 坐标建立一棵线段树，并用一个集合 \(ans\) 记录当前所有能看到的颜色，线段树的每个节点记录如下信息，注意，每个节点都不记录能够覆盖父亲结点区间的颜色信息（如某个节点代表 \([0,4)\)，那么所有能够覆盖 \([0,8)\) 的颜色都不在该点记录）：

• \(col[u]\) 表示能够覆盖 \(u\) 对应区间的所有颜色组成的集合
• \(max[u]\) 表示在 \(u\) 对应的区间中能够看到，但是目前不在 \(ans\) 中的最大颜色
• \(min[u]\) 表示在 \(u\) 对应的区间中能够看到的最小颜色，容易注意到比 \(min[u]\) 小的颜色肯定不能看到，而比 \(min[u]\) 大的颜色肯定能看到（如果有的话）

显然 \(col\) 只需要我们在更新线段树时顺带更新即可，\(max\) 和 \(min\) 在 pull 时更新：

设 maxchild = max(max[u << 1], max[u << 1 | 1])，minchild = min(min[u << 1], min[u << 1 | 1])，maxcol = col[u].empty() ? 0 : *(-- col[u].end())

• 若 col 不为空且 maxcol > maxchild ，此时子树中的 maxchild 都已经被 maxcol 覆盖，无法看到
  • 若 maxcol < minchild，此时 maxcol 本身又被子树覆盖，没有能够看到且不在 ans 中的颜色，max[u] = 0
  • 否则此时 maxcol 是唯一不在 ans 中的可见颜色，max[u] = maxcol
• 否则 max = maxchild
• min = max(minchild, maxcol)，这个式子的正确性可以通过枚举 maxcol, min[u << 1], min[u << 1 | 1] 之间不同的大小关系来验证，这里不赘述。

之后在扫的过程中，每次先把所有的增、删事件处理完，那么显然有 max[root] 即为一个需要加入 ans 的颜色，但是加入之后，max 数组需要进行更新，这时我们再“添加”一遍 max[root] 所在的区间，就能在 pull 时更新 max 数组了。我们需要重复这一操作，直到 max[root] == 0，再进行下一次扫描。

时间复杂度 \(\mathcal{O}(n\log^{2}n)\)。

E. NN country