纸箱堆叠 bzoj 2253

时间:2024-07-11 09:04:14

纸箱堆叠

【问题描述】

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


题解:

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

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

接下来递归分成两区间

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

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

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

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

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

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

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

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

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

 #include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<cmath>
using namespace std;
inline int Get()
{
int x = ;
char c = getchar();
while('' > c || c > '') c = getchar();
while('' <= c && c <= '')
{
x = (x << ) + (x << ) + c - '';
c = getchar();
}
return x;
}
const int me = ;
struct box
{
int x, y, z, ans;
};
box c[me], s[me];
int a, p, n, m;
int tr[me];
int num[me];
inline bool rulex(box a, box b)
{
if(a.x != b.x) return a.x < b.x;
if(a.y != b.y) return a.y < b.y;
return a.z < b.z;
}
inline bool rules(int a, int b)
{
if(s[a].z != s[b].z) return s[a].z < s[b].z;
if(s[a].x != s[b].x) return s[a].x < s[b].x;
return s[a].y < s[b].y;
}
inline bool ruley(box a, box b)
{
if(a.y != b.y) return a.y < b.y;
return a.z < b.z;
}
inline int Max(int x)
{
int maxx = ;
while(x > )
{
maxx = max(tr[x], maxx);
x -= x & (-x);
}
return maxx;
}
inline void Ins(int x, int y)
{
while(x <= m)
{
tr[x] = max(tr[x], y);
x += x & (-x);
}
}
inline void Del(int x)
{
while(x <= m)
{
tr[x] = ;
x += x & (-x);
}
}
inline int Maxx(int x, int y)
{
return (x > y) ? x : y;
}
void Work(int l, int r)
{
if(l == r) return;
int mi = l + r >> ;
while(s[mi].x == s[mi - ].x) --mi;
if(mi < l) return;
Work(l, mi);
sort(s + l, s + mi + , ruley);
sort(s + mi + , s + r + , ruley);
int u = l, v = mi + ;
while(u <= mi && v <= r)
{
if(s[u].y < s[v].y)
{
Ins(s[u].z, s[u].ans);
++u;
}
else
{
s[v].ans = Maxx(s[v].ans, Max(s[v].z - ) + );
++v;
}
}
for(int i = v; i <= r; ++i)
s[i].ans = Maxx(s[i].ans, Max(s[i].z - ) + );
for(int i = l; i <= mi; ++i) Del(s[i].z);
sort(s + mi + , s + r + , rulex);
Work(mi + , r);
}
int cc[];
int main()
{
a = Get(), p = Get(), n = Get();
cc[] = ;
for(int i = ; i <= n; ++i)
{
cc[] = cc[] * a % p;
cc[] = cc[] * a % p;
cc[] = cc[] * a % p;
cc[] = cc[];
sort(cc + , cc + );
c[i].x = cc[], c[i].y = cc[], c[i].z = cc[];
c[i].ans = ;
}
sort(c + , c + + n, rulex);
for(int i = ; i <= n; ++i)
{
if(c[i].x != c[i - ].x || c[i].y != c[i - ].y || c[i].z != c[i - ].z)
{
s[++m] = c[i];
num[m] = m;
}
}
sort(num + , num + + m, rules);
int k = ;
for(int i = ; i <= m; ++i)
{
k = i;
while(s[num[i]].z == s[num[i + ]].z)
{
s[num[i]].z = k;
++i;
}
s[num[i]].z = k;
}
Work(, m);
int ans = ;
for(int i = ; i <= m; ++i)
if(s[i].ans > ans)
ans = s[i].ans;
printf("%d", ans);
}