首页 > > 程序设计 > C/C++ >

纸箱堆叠 BZOJ 2253

2018-06-17 23:25:39来源：未知阅读 ()

纸箱堆叠

【问题描述】

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

【样例输出】

【样例说明】

生产出的纸箱的三边长为(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

题解：

我们设长宽高为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 }