TuringJudge monthly 图灵姬月赛 2019.10【解题报告】

Zeratul 2019-10-05 23:29:35 2019-10-08 13:49:11

A:自定义排序

众所周知,这是一道签到题。

考察结构体排序的知识。

题如其名,自定义排序。只需重载运算符或定义cmp函数,调用std::sort即可。

本着和谐友善的原则,本题即使不会以上语法,也可以写冒牌排序/选择排序拿到80分。

B:The World Without HIM

考察进制转换。

题目实际可以转化成十进制和六进制的互相转换。

缺少4个数码,相当于把六进制的0,1,2,3,4,5六个数码变成0,3,4,5,7,8。

注意,答案不能直接用int存储,因为十进制转换之后位数会变多,从而超过int的范围。

C:校验码

考察递推和矩阵快速幂。

讨论字符串的最后一位。如果校验码是 c ,字符串是最后一位是 k[j] ,那么前面的和是 c-k[j]

定义 dp[i] 是校验码为 i 时的方案数,可以通过讨论字符串的最后一位实现递推。即 dp[i] = \sum{dp[i-k[j]]}

以上做法即可得到90分。

显然这也是一个线性递推式,并且最多就只有9项,因此可以应用矩阵快速幂进一步加速。

D:动态最大连续和

考察并查集和标准容器std::multiset的使用。

虽然题面看上去是个线段树,然鹅这题和线段树并没有什么联系。

每次修改后都不会把一个数修改为负数,因此最大连续和也就是最大联通块。

考虑所有的pos都不相同的情况(前70分):加入一个数时,如果这个数的左边不是-INF,那么要合并这个数和左边的部分。右边也是同理。因此这是一个维护联通性的问题,直接使用并查集维护即可。

对于pos可能出现重复的数据,相当于可以修改一个联通块的权值,这会导致答案不再单调。因此需要使用std::multiset维护所有联通块的权值。

恭喜以下同学

麻烦回复一下邮件

共 3 条回复

FiLaReTKuN

前排兜售小零食

_Wallace_

t4线段树范围写错,搞得和写暴力的分数一样,太草了。。。

lu_ruo_kuan

赞一个

AMAZE UI
Hello world!