C++大神求助!!!XJOI 奇葩的排序

题目中的最大校验值应由数组排序后,取出最大值和最小值,次大值和次小值……进行做差平方取和

所以在加入一个新的数时,校验值是不会下降的

那么可以发现,校验值是单调递增的,所以可以用二分对每一个固定的左段点找到满足条件的最大的右端点

所以l初始值设为1,不断对r进行二分,找到最大的点

进行二分时要用二进制数(倍增),不能直接取mid

设一个偏量p,右端点即为r+p,一开始设为1,然后对其判断,在k的范围内p就乘2,否则p除以2

进行判断时,将整个区间进行排序,取前m个数和后m个数分别做差,算出值与k比较

而排序用的时间最多,所以要利用之前排好的元素进行归并排序

for (int i=l;i<=r+p;i++)//注意,这句不能放在merge函数中,因为p有可能变小,之前排好序的元素可能排到了r之后,在之后统计答案时无法统计到

一个数的约数也称为因子,比如1是6的因子,2是6的因子,6是6的因子。

质数只有两个因子,1和它本身

现在定义一种新的质数,三质数,三质数只有三个不同的因子。比如4是三质数,因为它有1 ,2, 4三个因子。比如6不是三质数,因为6有1 ,2, 3, 6四个因子。现在有一些数,你需要判断他们是不是三质数。

第一行一个整数T,表示有T组测试数据。

每组测试数据输入一个整数n

对于每组测试数据,判断是否是三质数,如果是输出YES,否则输出NO

本来是想:“OK简单直接打代码”,打完后。。。

我一开始的思路是求不同质子个数,就TLE了

后来想省去一些搜索质子步骤,好家伙结果就WA;

后来一个朋友启发了我:平方数

只有三个因子的数只有平方数

好,那么我们就可以将问题简化为(通过判断一个数的平方根是否为整数,来判断是否为三质数)

今天就没那啥很糙的图了,作者觉得其实思路给了就OK了

小猛新:OK个P啊,怎么判断一个数的平方根是否为整数啊!

判断一个数的平方根是否为整数如上;

好了,重要的讲完了,附上AC代码,拜拜!

我要回帖

更多关于 求助大神这是什么歌 的文章