10月月赛题解

大家好，我是本场的月赛出题人Occult

闲来无事为C语言网免费贡献了这一套题，不知道大家觉得这套题如何

不过就结果而言好像难度略高了，这个锅我背了，一出题就控制不住自己了。

前几天正好赶上我外出比赛，于是于今天放出整套题目题解仅供参考。

因为时间紧，数据造的没有那么严谨，如有疑问可以联系本人，QQ568805874

题解按照我个人认定的难度排序

1.小O的图案

一道按规律打印图案的题目,没有什么特别的,老老实实找规律就好了.

可以按照标程的思想,按照奇数和偶数分开讨论的办法.

2.小O的乘积

因为求的是最小的乘积,所以根据情况可以分为三种

所有数字大于等于0,那么选择最小两个数相乘是答案.

所有数字小于等于0,那么选择最大两个数相乘是答案.

数字有正有负,那么选择最大最小两个数相乘是答案.

3.小O的数字

同样是一个打印图案的题目,

读入可以选择直接用字符串读入或者用数字读入然后处理到数组里

然后根据数字的类型分别打印五行内容即可.

4.小O的字符

先根据题意推出所谓的包含关系的本质,就是字符存在次数的关系.

把两个字符串转化成两个数组,数组用来记录每个字符出现的次数.

然后遍历整个字符集合,判断大小的情况即可.

5.小O的溢出

稍微涉及到算法的题目,根据题意可以推测出,最大的攻击一定是最后使用的

所以我们取出最大的攻击力留到最后,然后把其余的攻击力进行组合

推出一个最接近BOSS血量m的伤害值(小于m的),然后用最大攻击力补刀.

得到的就是答案,至于如何算出一个最接近m的伤害值,可以采用01背包的思想.

6.小O的质数

较为困难的题目,留意到数据范围中R-L>=1000000的设定,从这出发

思考如何进行小于等于n的素数筛选,有一个nlogn的办法是开一个n大小的数组,初始化为1

从2枚举到n,然后把自身的倍数全部标记为0,这样标记为1的就都是质数了.

同理,我们开一个R-L的数组,从2开始枚举,枚举到根号R为止,把区间里对应的倍数标记为0

这样最后扫一遍区间就可以知道有几个是质数了

标程以及全套题目数据将以压缩包形式上传至官方群文件共享，有需要请自取。