A可以加强到p非素数
2018.10 月赛题解
ultmaster edited 5 年，6 月前
ultmaster: A, C, D 是「用过的题」。当时现场情况非常惨烈，也不知道是同学们水平不大行，还是出题人水平不大行。
kblack: Huge gap between B and C. 
Problem A
by ultmaster. tag: 构造
由于 $p | mn$，又 $p$ 是质数，所以 $p | n$ 或 $p|m$，否则无解。不妨假设 $p|m$。可以将 $m$ 分成 $\frac{m}{p}$ 块，然后一块一块填即可。类似于这样：
1 1 1 2 2 2 3 3 3
4 4 4 5 5 5 6 6 6
Problem B
by ultmaster. tag: 数学、贪心
首先注意到 $p$ 的取值应该就是 $\max {a_i} + 1$。然后相邻两项之间贪心地填东西。答案就是
$$n + \sum_{i=2}^{n} (a_i - a_{i-1} - 1) \bmod p$$
注意处理一下减出来的东西是负数的情况。
Problem C
by ultmaster. tag: 数学
用 $r_i$ 表示第 $i$ 行有多少个 0，用 $c_i$ 表示第 $j$ 列有多少个 0，$b_{ij}$ 表示第 $i$ 行第 $j$ 列是否为 0。则 $cost(i,j)=r_i+c_j-b_{ij}$。
对原式进行展开得到：$\displaystyle(n-2) \sum_{i=1}^n c_i^2 + (n-2) \sum_{i=1}^n r_i^2 + 2C^2+C$。
其中 $C$ 为整个矩阵中 0 的个数。
每次修改操作至多只会影响一个 $c_i$ 和一个 $r_i$，将原来的 $c_i,r_i,C$ 的贡献撤回，然后重新计算贡献即可。
Problem D
by ultmaster. tag: 字符串、哈希
可能的解肯定落在深度最深的节点上。可以先求出来。
注意到字符串的长度可能达到 $2 \cdot 10^5$，暴力建 Trie 会超时。一种方法是把后缀树建出来，然后把后缀树转化成后缀 Trie，判断是否和给出的树一样。缺点是实现难度较高（但是有板子啊？）。
可以采用哈希，求出每个终态对应的字符串的哈希值，组成一个集合；然后与原字符串的每个后缀的哈希值组成的集合进行比较判断。哈希的时候注意你采用的哈希是「大端」的还是「小端」的。
comment: 此题数据造起来真的是太恶心了。如果数据还是丢人了，那……没办法了啊？
comment 2: 第一版的 std 也是错的，错在没有判断是否所有的叶子节点都是终态。验题人居然跟出题人错在了同一个地方。要不是有稳健的 kblack，这题就锅了。
Problem E
by zerol. tag: 数据结构、随机算法
解法一：
- 如果是询问一个矩形区域的话，只需要用二维 ST 表维护就好了，100 个数需要用 bitset 压一下。
- 由于询问的是个三角形（均指题目中的等腰直角三角形），考虑用三个高是 $2^k$ 的三角形去覆盖它。不幸的是，中间可能还有块洞需要补，再用若干个正方形去补就好了。
- 预处理复杂度 $O(n^2 \log n)$，询问复杂度 $O(1)$。
解法二：
- 假设每个数字不出现的事件独立（事实上，一个数字不出现会增大另外一个数字出现的概率），在 $d=50$ 时，答案为 100（所有数字都出现）的概率，根据容斥原理，大于 1 减去一个数字不出现的事件的概率的和。即 $1 - 100 \times (1-0.01)^{50 \times 50} \approx 1 - 10^{-9}$。预处理每一行不超过 50 的连续区间的 bitset，然后询问的时候暴力合并一下。复杂度是 $\mathcal{O}(50 \cdot (n^2 + q))$。可以用 60 更为稳妥。
- 为了增加大家「用暴力卡过去」的愉悦感，解法二的空间和时间都比较紧。（但绝不是卡常。我可以说你复杂度不对的啊？）
- 其实要用非随机数据 hack 的话显而易见啊？令 $a_{ij} = i$ 大概可以。不过这个暴力有理有据，好像也挺自然的。
- 比赛中发现有人没用 bitset 也过了。还行吧。跑得有点快啊？大概就是无招胜有招？
zerol: 比较懒，造了随机数据。听说乱搞能过的时候，觉得这样似乎也挺不错的，就没有去卡，而是题面中添加了数据随机的提示。可惜的是，这题没法自闭了。
A题改成非素数的话，思路不变化吧？
楼上已经有人说了。