这次题目确实挺幽默
由于T6不算奖励,我就没有写(绝对不是我不会),以下是T1-T5的题解:
T1
T2
我们很容易地发现,NNN 越大,1∼N1\sim N1∼N 中出现质数的频率就越低.所以必然存在一个质数,在它之后的所有数都不满足条件.
那么怎么求这个数呢?
我们又发现,1∼N1\sim N1∼N 中出现质数的频率约等于 NlnN\dfrac{N}{\ln N}lnNN .
若 lnN=2\ln N=2lnN=2,则 N≈7.4N\approx7.4N≈7.4.所以这个质数就大概为 777.
我们将 777 之后的一个质数 111111 代入试试,发现 111111 之内的质数有 555 个,确实不满足条件.
所以这个分界线就是 777 了!
那么我们只需要将 777 以内的数逐个判断,发现只有 3,5,73,5,73,5,7 满足条件.
所以,我们只需要判断输入的数是否为 3,5,73,5,73,5,7 中之一就行了!
T3
本题消灭了所有没参加过今年蓝桥杯或使用Python的人
水题,了解题意就行.
注意对负数取模结果仍为负数,所以应先加上模数再取模.
T4
数据强度太高了,看不懂啊(
这题绝对不能骗分,否则你只能拿到94分,50个测试点只能通过47个(
骗分思路:我们发现两个操作不会改变序列的总和,所以我们判断两个序列的和是否相等就行了
可以发现样例是5个Yes,但是成功骗得94分笑死我了(Macw说比赛后会加强数据,帮我看看加强的怎么样)
ok现在来说说正经解法
我们可以将两个序列都按照操作一拆分到极限,再来对比是否相等.
比如
两个序列拆分后完全相同,说明是可以的
但是以刚刚的例子,我们注意到原来的 666 个元素拆分后变成 929292 个元素,要是放极端数据就会有 5×10135\times 10^{13}5×1013 个 111,根本存不下.
那么我们可以只存连续的一段数的个数
例如原来的
压缩后变成
精简了很多
T5
相对简单一些,直接模拟
当然还可以使用堆优化 O(nlogn)O(n\log n)O(nlogn),我就不讲了