八月月赛题解

TooY0ung 2020-08-08 22:06:26 2020-08-09 17:04:59

八月月赛题解

1. 这是第一道温暖的签到题

很温暖,奇偶性签到题。

ans=(len(s)+1)/2

2. 这是第二道温暖的签到题

很温暖,计数签到题。

扫一遍,计数连续的0有多少个,超过k个就输出work,否则home

3. 这是第三道温暖的签到题

很温暖,字符串判断题。

最近noip考了两年签到题字符串了,所以也来了一道。

注意不是数多少个xcyd,是数多少行包含xcyd

4. 这是第四道温暖的签到题

其实挺温暖的,可能大家没有发现玄机。

炮弹数和智能机械数是相同的,所以一发炮弹必须消灭一个智能机械,也就是说,当两个数组排序后,A[i]<=B[i],否则,答案为0

设初始答案为1

两个数组从小到大排序之后

遍历炮弹伤害数组:

找到血量小于等于这个炮弹伤害的智能机械数量 记为n,炮弹下标记为m(下标从1开始)答案乘上(n-(m-1))

可以解释为:有n种选择,但是前面的(m-1)发炮弹已经消灭了(m-1)个机械了,所以对于这发炮弹的的选择只剩下了(n-(m-1))

遍历结束,即为答案。

注意:因为答案可能会特别大,所以答案需要对1e9+7进行取模。

5. 这是第五道温暖的签到题

其实还是挺温暖的,可能大家还是没有发现玄机。

标程给的是贪心,也有验题老师拿压位dp A的(既不好写又难调,推荐贪心大法好)

对智能机械按血量从大到小排序

将炮弹按照伤害值从大到小排序

从前向后遍历智能机械

期间维护一个优先队列,里面放炮弹(两个属性,费用、伤害值),费用小的优先

遍历智能机械时,先将所有伤害值大于等于这个智能机械生命值的炮弹压入优先队列中(每发炮弹最多压入一次)

全部压入后,如果优先队列为空,则不能将所有智能机械全部消灭

不为空,则取出队顶元素并出队,累计费用值

直到所有智能机械遍历完成,即为最优答案,答案不会超出int的范围

6. 这是第六道温暖的签到题

好吧,这个确实没那么温暖,需要点数学计算。

不过单从榜单角度来看,应该作为压轴题目还是挺温暖的吧,毕竟前几个月月赛压轴题都非常惨淡(大家都是0分)

考虑简化的问题 A = [1,a]B = [1,b]

先只看[1, a]的部分

AB两个集合各做了“1a的平方和”的贡献

但有 “1a的和”的重复贡献

所以这部分的贡献是sum(a^2) * 2 - sum(1, a)

然后是[a+1, b]的部分

A集合不做贡献 B集合做了a次“a+1b的和”的贡献

所以这部分的贡献是sum(a + 1, b) * a

恭喜以下选手

共 21 条回复

Jack_Kasluo

前排兹磁

Jack_Kasluo

太《温暖》了!真是凉心出题人啊[doge]

Kruskal

显然楼上心态崩了啊

Jack_Kasluo

对哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈,这次我裂开了

Jack_Kasluo

我们讨论了好久都没做出来qaq

babyec

可能需要数学老师的帮助(大雾)

Leiyuxuan

前排兜售各种小零食!

linzihan1314

发现第六题思路完全对不上。。。。。

linzihan1314

第六题做了两个不同版本的,都是80分,一个结果是TLE,另一个WA,,,,,

TooY0ung

带除法的记得加上逆元

Leiyuxuan

T6我不开long long见祖宗啊

linzihan1314

T6我都开unsigned long long了

linzihan1314

T6我目前做出来的时间复杂度是O(1)

linzihan1314

感觉思路完全没毛病,但居然还是80分

Leiyuxuan

我T6柿子推了3h,然后还带了个高精,爆肝200行只有10pts/fad 然后赛后参数改long long加上几个%运算就60pts了(大雾)

guanbo

生命值从大到小枚举,炮弹排序:代价从小到大,价格不同时伤害从大到小 第五题贪心策略:生命值从大到小枚举,炮弹排序:代价从小到大,价格不同时伤害从大到小 ,只能拿80分

Kruskal

头像挺萌

AMAZE UI
Hello world!