课程咨询 :18087159764

  • 纸箱堆叠(1s 128MB) box

    发布:广州C++培训      来源:达内新闻      时间:2017-01-16

  • 广州C++培训机构的小编这一期分享纸箱堆叠(1s 128MB) box。

    【问题描述】

    P工厂是一个生产纸箱的工厂。纸箱生产线在人工输入三个参数n, p, a之后,即可自动化生产三边边长为

    (a mod P, a^2 mod p, a^3 mod P)

    (a^4 mod p, a^5 mod p, a^6 mod P)

    ....

    (a^(3n-2) mod p, a^(3n-1) mod p, a^(3n) mod p)

    的n个纸箱。在运输这些纸箱时,为了节约空间,必须将它们嵌套堆叠起来。

    一个纸箱可以嵌套堆叠进另一个纸箱当且仅当它的最短边、次短边和最长边长度分别严格小于另一个纸箱的最短边、次短边和最长边长度。这里不考虑任何旋转后在对角线方向的嵌套堆叠。

    你的任务是找出这n个纸箱中数量最多的一个子集,使得它们两两之间都可嵌套堆叠起来。

    【输入格式】

    输入文件的第一行三个整数,分别代表a, p, n

    【输出格式】

    输出文件仅包含一个整数,代表数量最多的可嵌套堆叠起来的纸箱的个数。

    【样例输入】

    10 17 4

    【样例输出】

    2

    【样例说明】

    生产出的纸箱的三边长为(10, 15, 14), (4, 6, 9) , (5, 16, 7), (2, 3, 13)。其中只有(4, 6, 9)可堆叠进(5, 16, 7),故答案为2。

    【样例说明】

    2<=P<=2000000000,1<=a<=p-1,a^k mod p<>0,ap<=2000000000,1<=N<=50000

    题解:

    主要算法:CDQ分治(快速排序,树状数组);动态规划(Dp);

    我们设长宽高为x,y,z

    CDQ分治,以x为关键词排序

    接下来递归分成两区间

    假设左区间已经处理完了答案

    将左右区间分别以y为关键字排序

    那么就保证了任何左区间的x必定小于任何右区间的x

    我们用两个指针分别从左右区间顺序向后扫

    将左区间的z作为位置不断加入树状数组,值为当前点的答案

    由于左右区间有序,可以手动保证右区间的扫到的点的y大于所有左区间扫到的点的y

    就可以用树状数组更新右区间点的值:当前点的答案等于能转移到当前点的点的答案加一的最大值,这里用上了Dp的思想

    然后清空树状数组,再将左右区间合并按第一维排序,恢复原状态,保证处理的是最初的右区间,且此区间按第一维有序

上一篇:广州C++培训机构带你讲SHA-1算法

下一篇:单向链表实现

最新开班日期  |  更多

c++--零基础周末班

c++--零基础周末班

开班日期:6月30日

c++--零基础全日制班

c++--零基础全日制班

开班日期:6月30日

c++--免费训练营

c++--免费训练营

开班日期:6月30日

c++--高薪就业班

c++--高薪就业班

开班日期:6月30日

  • 网址:http://gz.c.tedu.cn     地址:广州市天河北五山路 141 号尚德大厦 627
  • 课程培训电话:18087159764     全国服务监督电话:400-111-8989
  • 服务邮箱 tousu@tedu.cn
  • 2001-2016 达内时代科技集团有限公司 版权所有 京ICP证8000853号-56