四题只做出一题，然而 Rating 涨了，应该是因为我一直都很菜吧。
综述#
题数 1/4，排名 172/537。头铁，做完第一个一直在磕第二个；第二个磕不动，读第三个，比赛时题意读错（最近好多次出问题都出在这样的初期准备上，可能我需要换个脑子了）。赛后不借助题解直接补了第三题。
题意和题解#
C. Snuke Festival (sort, partial sum)#
给三个长度为 \(n\) 的数组 \(A_i, B_i, C_i\)，问从三个数组中分别抽出一个数 \(A_u, B_v, C_w\)，有多少种情况能使得 \(A_u < B_v < C_w\)。
三个数组排序。先找有多少对 \(B_v < C_w\)，即对每个 \(v_0\) 记录一下有多少个 \(C_w > B_{v_0}\)；因为数组排好序了，对每个 \(v_0\) 卡个指针 \(w\) 就可以，记这个值为 \(b_{v_0} \gets n - w\)。由于对于每个 \(u_0\)，只要知道哪些 \(B_v > A_{u_0}\)，那么满足题意的三元组的个数就是 \(\sum_{B_v > A_{u_0}}{b_v}\)，类似于处理 \(v_0\) 的方式搞一下就行。
时间复杂度 \(\mathcal{O}(n \log{n})\)。
D. Small Multiple (graph, shortest path)#
对于给定的 \(k\)，找到十进制各数位和最小的 \(k\) 的倍数。
先考虑十进制的各数位和怎么处理。容易发现对于每个非负数 \(u\)，\(10 u\) 的各数位和与 \(u\) 的是相等的，\(u + 1\) 的各数位和则小于或等于 \(u\) 的各数位和加一。这样把每个非负数看作是图上的点，\(u\) 向 \(10u\) 连接一条长度为 0 的边，向 \(u + 1\) 链接一条长度为 1 的边。那么每个数 \(u\) 的各数位和就是从 \(0\) 到 \(u\) 的最短路。
而题目所需的就是 \(0\) 到 \(k\) 的所有倍数的点的最短路。把每个点模 \(k\)，问题就变成了从 \(0\) 跑回来的最短路了。
实现上可以考虑从每个 \({10}^i\) 出发，跑个类似分层的bfs，把长度为 0 的边能连到的点先放到同一层，把长度为 1 的放到下一层，某一层处理完了再处理下一层。搜完或者扫到 \(0\) 了就找到答案了。这样写起来不算困难，时间复杂度也较优。
时间复杂度 \(\mathcal{O}(k)\)。
D. Small Multiple (trie?, locally bruteforce for properties?)#
给两个正数 \(n, k\)，求长度不超过 \(n\) 的、由 \(1\) 到 \(k\) 的整数组成的元组，按字典序排序（长度不同则在后面补 \(0\)，即 \((1, 1) < (2)\)，比赛时这里搞错了），排名居中的数组是哪个。
相当于建一个深度为 \(n\)，\(k\) 叉的 trie，并且除了根的所有点都要算作一个合法的点，求排名居中的那个点。如果 \(k=1\)，不多说。\(k\) 为偶数的时候，会发现根的左半部分和右半部分的合法点数目相同，所以我们只需要找到左半部分字典序最大的点就行，所以答案就是这个点对应的数组，即长度为 \(n\) 的 \(\frac{k}{2}, k, k, \cdots, k\)。
如果 \(k\) 为奇数，考虑每次都走节点排名居中的儿子，一直走到叶子，如果分枝结点不算做合法点数的话，这个节点对应的数组就是答案了，而这个节点的排名多了 \(n-1\)，因为前面多了 \(n-1\) 个父节点。这样我们需要在 trie 上找到从当前这个节点走到排名减 \(\frac{n-1}{2}\) 的前驱。这个过程类似于平衡树找前驱的过程，对于当前的点，如果自己不是父节点的第一个儿子，则跳到父节点的前一个儿子，并且沿字典序最大的方向上一直跳到叶子，这个叶子就是前驱；如果当前节点是父节点的第一个儿子，那么前驱就是自己的父节点了，跳到父节点上就行。这样不断操作 \(\frac{n-1}{2}\) 次就得到了对应答案的点了。
对于找前驱的过程，假设现在这个节点到达了第 \(0 \le u \le n\) 层，那么说明我们已经跳过了 \(\mathcal{O}(k^{n-u})\) 个排名，因此不用担心找前驱的过程会跳太多次的父节点，最多只会跳到叶子节点的第 \(\log_k{n}\) 级父节点。
所以时间复杂度 \(\mathcal{O}(n \log_k{n})\)。
F. XorShift#
（还没读……待补）
评论