2018.10 月赛题解

ultmaster edited 4 月,2 周前

ultmaster: A, C, D 是「用过的题」。当时现场情况非常惨烈,也不知道是同学们水平不大行,还是出题人水平不大行。

kblack: Huge gap between B and C.

Problem A

by ultmaster. tag: 构造

由于 ,又 是质数,所以 ,否则无解。不妨假设 。可以将 分成 块,然后一块一块填即可。类似于这样:

1 1 1 2 2 2 3 3 3
4 4 4 5 5 5 6 6 6

Problem B

by ultmaster. tag: 数学、贪心

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

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

Problem C

by ultmaster. tag: 数学

表示第 行有多少个 0,用 表示第 列有多少个 0, 表示第 行第 列是否为 0。则

对原式进行展开得到:

其中 为整个矩阵中 0 的个数。

每次修改操作至多只会影响一个 和一个 ,将原来的 的贡献撤回,然后重新计算贡献即可。

Problem D

by ultmaster. tag: 字符串、哈希

可能的解肯定落在深度最深的节点上。可以先求出来。

注意到字符串的长度可能达到 ,暴力建 Trie 会超时。一种方法是把后缀树建出来,然后把后缀树转化成后缀 Trie,判断是否和给出的树一样。缺点是实现难度较高(但是有板子啊?)。

可以采用哈希,求出每个终态对应的字符串的哈希值,组成一个集合;然后与原字符串的每个后缀的哈希值组成的集合进行比较判断。哈希的时候注意你采用的哈希是「大端」的还是「小端」的。

comment: 此题数据造起来真的是太恶心了。如果数据还是丢人了,那……没办法了啊?

comment 2: 第一版的 std 也是错的,错在没有判断是否所有的叶子节点都是终态。验题人居然跟出题人错在了同一个地方。要不是有稳健的 kblack,这题就锅了。

Problem E

by zerol. tag: 数据结构、随机算法

解法一:

解法二:

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

Comments

oxx1108

A可以加强到p非素数

ultmaster

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

xuanweiace

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

xuanweiace

A题p是素数与否,不影响解题吧?

xuanweiace

A题改成非素数的话,思路不变化吧?

ultmaster

楼上已经有人说了。

___qxy

建议D题加个数据

4
1 2 1
aaa
111

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

ultmaster

仔细读题啊。。。

___qxy

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

Lucien

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

ultmaster

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

HztNo1

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

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

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

ultmaster

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

你正在回复博客
存在问题!