2019寒假集训day3

T1混合牛奶
刚开始让人误以为是多重背包问题,但事实并非如此,还更简单一下。
用贪心的思想即可,快速排序把价格便宜的牛奶排在前面。
为什么说不是多重背包呢,因为这里的牛奶可以一升一升买。

T2回文质数
有一个比较复杂算法,耗时956ms(不稳定):
对于数据范围1——1e9
我们知道,回文的密度要比质数要小,所以我们可以先判断回文。
我们可以想到,一个数如果既是回文又是质数,那么它的个位仅可能是1,3,5,7,9.这时枚举的i可以2个2个加。
它的最高位也只能是1,3,5,7,9.所以对于向20001的数字可以直接跳转到30001.
虽然看似时间复杂度小了很多,但是那些优化判断也是需要时间的,优化作用不是很好,这时怎么办呢?
最后我们发现,1e8之后已经没有符合条件的数字了,这时我们可以把枚举范围缩小到1e8,或者采用On算法:打表。数字并不多,可以事先求出。

T3最短网络
最小生成树,比较明显的一道题;
推荐使用Prim算法,因为这里邻接矩阵已经事先给出,不用自己转化。

T4兽径管理
依然考最小生成树算法
Prim算法不推荐使用,不好优化
这里讲Kruskal算法
暴力做法:每次加一条边都sort一次,后做最小生成树,部分数据超时。
有没有更快的做法?
我们发现,我们可以给每一条边标记它的加边时间,然后一次sort的同时把时间也带上,这样我们可以通过标记来判断符不符合时间,这样以来只需sort一次。

发表评论

电子邮件地址不会被公开。 必填项已用*标注