纸箱堆叠 bzoj 2253

2017-01-04 12:08:21来源:cnblogs.com作者:LoseYourTemper人点击

纸箱堆叠 (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的思想

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

接着递归处理右区间,继续更新答案

  1 #include<algorithm>  2 #include<iostream>  3 #include<cstdlib>  4 #include<cstring>  5 #include<cstdio>  6 #include<cmath>  7 using namespace std;  8 inline int Get()  9 { 10     int x = 0; 11     char c = getchar(); 12     while('0' > c || c > '9') c = getchar(); 13     while('0' <= c && c <= '9') 14     { 15         x = (x << 3) + (x << 1) + c - '0'; 16         c = getchar(); 17     } 18     return x; 19 } 20 const int me = 100233; 21 struct box 22 { 23     int x, y, z, ans; 24 }; 25 box c[me], s[me]; 26 int a, p, n, m; 27 int tr[me]; 28 int num[me]; 29 inline bool rulex(box a, box b) 30 { 31     if(a.x != b.x) return a.x < b.x; 32     if(a.y != b.y) return a.y < b.y; 33     return a.z < b.z; 34 } 35 inline bool rules(int a, int b) 36 { 37     if(s[a].z != s[b].z) return s[a].z < s[b].z; 38     if(s[a].x != s[b].x) return s[a].x < s[b].x; 39     return s[a].y < s[b].y; 40 } 41 inline bool ruley(box a, box b) 42 { 43     if(a.y != b.y) return a.y < b.y; 44     return a.z < b.z; 45 } 46 inline int Max(int x) 47 { 48     int maxx = 0; 49     while(x > 0) 50     { 51         maxx = max(tr[x], maxx); 52         x -= x & (-x); 53     } 54     return maxx; 55 } 56 inline void Ins(int x, int y) 57 { 58     while(x <= m) 59     { 60         tr[x] = max(tr[x], y); 61         x += x & (-x); 62     } 63 } 64 inline void Del(int x) 65 { 66     while(x <= m) 67     { 68         tr[x] = 0; 69         x += x & (-x); 70     } 71 } 72 inline int Maxx(int x, int y) 73 { 74     return (x > y) ? x : y; 75 } 76 void Work(int l, int r) 77 { 78     if(l == r) return; 79     int mi = l + r >> 1; 80     while(s[mi].x == s[mi - 1].x) --mi; 81     if(mi < l) return; 82     Work(l, mi); 83     sort(s + l, s + mi + 1, ruley); 84     sort(s + mi + 1, s + r + 1, ruley); 85     int u = l, v = mi + 1; 86     while(u <= mi && v <= r) 87     { 88         if(s[u].y < s[v].y) 89         { 90             Ins(s[u].z, s[u].ans); 91             ++u; 92         } 93         else 94         { 95             s[v].ans = Maxx(s[v].ans, Max(s[v].z - 1) + 1); 96             ++v; 97         } 98     } 99     for(int i = v; i <= r; ++i)100         s[i].ans = Maxx(s[i].ans, Max(s[i].z - 1) + 1);101     for(int i = l; i <= mi; ++i) Del(s[i].z);102     sort(s + mi + 1, s + r + 1, rulex);103     Work(mi + 1, r);104 }105 int cc[4];106 int main()107 {108     a = Get(), p = Get(), n = Get();109     cc[0] = 1;110     for(int i = 1; i <= n; ++i)111     {112         cc[1] = cc[0] * a % p;113         cc[2] = cc[1] * a % p;114         cc[3] = cc[2] * a % p;115         cc[0] = cc[3];116         sort(cc + 1, cc + 4);117         c[i].x = cc[1], c[i].y = cc[2], c[i].z = cc[3];118         c[i].ans = 1;119     }120     sort(c + 1, c + 1 + n, rulex);121     for(int i = 1; i <= n; ++i)122     {123         if(c[i].x != c[i - 1].x || c[i].y != c[i - 1].y || c[i].z != c[i - 1].z)124         {125             s[++m] = c[i];126             num[m] = m;127         }128     }129     sort(num + 1, num + 1 + m, rules);130     int k = 0;131     for(int i = 1; i <= m; ++i)132     {133         k = i;134         while(s[num[i]].z == s[num[i + 1]].z)135         {136             s[num[i]].z = k;137             ++i;138         }139         s[num[i]].z = k;140     }141     Work(1, m);142     int ans = 0;143     for(int i = 1; i <= m; ++i)144         if(s[i].ans > ans)145             ans = s[i].ans;146     printf("%d", ans);147 }

 

最新文章

123

最新摄影

微信扫一扫

第七城市微信公众平台