题目大意就是求N之内的最大反素数(一个正整数N满足在1..N 中,N有最多的约数,则它是一个反素数);
根据反素数定义,可以得出反素数的两个性质
- 反素数可以表示成$2^{t_1} \times 3^{t_2} \times 5^{t_3}…$这样连续的素数的幂的乘积
- 若用上面的表示方法,一定有$t_1 \geq t_2 \geq t_3 \geq …$
故可以根据这两个性质通过搜索可以很容易的找到反素数
1 |
|
题目大意就是求N之内的最大反素数(一个正整数N满足在1..N 中,N有最多的约数,则它是一个反素数);
根据反素数定义,可以得出反素数的两个性质
故可以根据这两个性质通过搜索可以很容易的找到反素数
1 | #include <algorithm> |
原题地址:ZOJ3574 Under Attack II
题目大意就是给出一个y无限的矩形区域,他的左边界在x=a,又边界x=b,求,现在给出n条直线,把这个矩形区域分成多少份?
很容易想到,每增加一条直线,若该直线与之前的直线在矩形内(不包括边界)有k个交点,则矩形增加的区域就是k+1,不知道为什么?我会在后续文章中介绍关于直线分割平面的相关推导。
但就算知道这,也还不行,如果直接两重循环,铁定TLE,我刚开始就是这样,然后彻彻底底被喵呜神给鄙视了!
其实,解决这题还有一个O(nlogn)的算法,我们可以这样看,假设,每一条边都已经固定在矩形上,然后,我们从矩形的左边开始看起,从下到上,映射到右边,如果在右边观看时,碰到有k个点(这些点对应的边一定要看过,也就是说对应左边的点要低)在上面,则说明该线段与前面的线段有k个交点。你也许不是很明白,看图,对应左边序号的123456,右边是246135,也就是说对于4号线,有1,3号线的左边低于4,右边高于4,则第4号线与前三条有两个交点,这不正是刚才要求的。现在转换成这样,是不是很熟悉,没错,求逆序对。逆序对的求法有多种,主要有归并排序,树状数组,如果不知道怎么做,可关注后续文章,会有关于求逆序对的总结。
我采用的是用用归并来求逆序对,详细也可参考刘汝佳的《算法入门竞赛经典》P144,那里介绍很详细,我也是直接拿着那的模板,详细看代码
more >>
等待更新……
等待更新……
C题可以说是本次比赛最简单的一题,题目大意是,每一个炸弹可以毁坏公路的一定区域,问投了多个炸弹后,从南到北和从北到南的公路上第一个毁坏最严重的是在哪一点。
例如,对于测试数据,在一个长10的公路,第一个炸弹,毁坏了公路的长从1到5的区域,毁坏程度是2,同理,第二个炸弹,毁坏了公路的长从6到9的区域,毁坏程度是2.所以,南到北和从北到南的公路上第一个毁坏最严重的点分别是1和9
没什么好说的,开一个适当大小的数组,我们可以对每一个炸弹的起点和终点分别加上毁坏程度和减少毁坏程度,这样,当炸弹全部投放完毕后,然后遍历这个数组,并用sumk求前面k的数组的和,则sumk就是第k个点的最后毁坏程度,详情看代码
more >>
tag:
缺失模块。
1、请确保node版本大于6.2
2、在博客根目录(注意不是yilia根目录)执行以下命令:
npm i hexo-generator-json-content --save
3、在根目录_config.yml里添加配置:
jsonContent: meta: false pages: false posts: title: true date: true path: true text: false raw: false content: false slug: false updated: false comments: false link: false permalink: false excerpt: false categories: false tags: true