2018.10 月赛题解

ultmaster edited 6 年，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)modp$$

注意处理一下减出来的东西是负数的情况。

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: 比较懒，造了随机数据。听说乱搞能过的时候，觉得这样似乎也挺不错的，就没有去卡，而是题面中添加了数据随机的提示。可惜的是，这题没法自闭了。

Comments

oxx1108

6 年，6 月前

A可以加强到p非素数

回复 11 0

ultmaster

6 年，6 月前

请大家不要在评论区贴代码。要贴代码也使用 Pastebin。请大家文明留言，谢谢合作。

回复 3 0

xuanweiace

6 年，6 月前

B题题干，加上正整数会好一些吧？当时卡这里了

回复 1 0

xuanweiace

6 年，6 月前

A题p是素数与否，不影响解题吧？

回复 1 0

xuanweiace

6 年，6 月前

A题改成非素数的话，思路不变化吧？

回复 1 0

ultmaster

6 年，6 月前

楼上已经有人说了。

回复 1 0

___qxy

6 年，6 月前

建议D题加个数据

4
1 2 1
aaa
111

我和我同学的代码跑这个数据一个输出illegal一个输出aa，然而两份代码都ac了…
我想答案应该是illegal吧…(小声

回复 0 0

ultmaster

6 年，6 月前

仔细读题啊。。。

回复 0 0

___qxy

6 年，6 月前

QAQ啊没注意到…非常抱歉了

回复 0 0

Lucien

6 年，6 月前

为什么TLE了, 复杂度应(ke)该(neng)是$O(n)$的吧…求解…
https://pasteme.cn/1090

回复 0 0

ultmaster

6 年，6 月前

初始化就爆炸了。你看看 $T$ 的规模。

回复 0 0

HztNo1

6 年，6 月前

Problem B
by ultmaster. tag: 数学、贪心

首先注意到p的取值应该就是max ai+ 1。然后相邻两项之间贪心地填东西。答案就是

n + ∑i = 2n( ai− ai − 1− 1 ) mod p
注意处理一下减出来的东西是负数的情况。
？？？？？？？？？？？？？？？？？？

回复 2 1

ultmaster

6 年，6 月前

你为什么在复制的同时，删除了所有格式？

回复 1 0