BZOJ_2253_[2010 Beijing wc]纸箱堆叠 _CDQ分治+树状数组
Description
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个纸箱中数量最多的一个子集,使得它们两两之间都可
嵌套堆叠起来。
Input
输入文件的第一行三个整数,分别代表 a,p,n
Output
输出文件仅包含一个整数,代表数量最多的可嵌套堆叠起来的纸箱的个数。
Sample Input
Sample Output
【样例说明】
生产出的纸箱的三边长为(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
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
#define N 50050
ll A,P;
int n,f[N],t[N],tmp[N],V[N],c[N],ans;
struct Q {
int x,y,z;
}a[N];
bool cmp(const Q &x,const Q &y) {return x.x<y.x;}
bool cmp1(int x,int y) {return a[x].y<a[y].y;}
void fix(int x,int v) {for(;x<=n;x+=x&(-x)) c[x]=max(c[x],v);}
int inq(int x) {int re=0;for(;x;x-=x&(-x)) re=max(re,c[x]); return re;}
void clear(int x) {for(;x<=n;x+=x&(-x)) c[x]=0;}
void solve(int l,int r) {
if(l==r) {f[l]=max(f[l],1); return ;}
int mid=(l+r)>>1;
int i,j=l,k=mid+1;
for(i=l;i<=r;i++) {
if(t[i]<=mid) tmp[j++]=t[i];
else tmp[k++]=t[i];
}
for(i=l;i<=r;i++) t[i]=tmp[i];
solve(l,mid);
j=l;
for(i=mid+1;i<=r;i++) {
while(j<=mid&&a[t[j]].y<a[t[i]].y) fix(a[t[j]].z,f[t[j]]),j++;
f[t[i]]=max(f[t[i]],inq(a[t[i]].z-1)+1);
}
for(i=l;i<j;i++) clear(a[t[i]].z);
solve(mid+1,r);
j=l,k=mid+1,i=l;
while(j<=mid&&k<=r) {
if(a[t[j]].y<a[t[k]].y) tmp[i++]=t[j++];
else tmp[i++]=t[k++];
}
while(j<=mid) tmp[i++]=t[j++];
while(k<=r) tmp[i++]=t[k++];
for(i=l;i<=r;i++) t[i]=tmp[i];
}
int main() {
scanf("%lld%lld%d",&A,&P,&n);
ll x,y,z=1;
int i;
for(i=1;i<=n;i++) {
x=z*A%P,y=x*A%P,z=y*A%P;
a[i].x=min(x,min(y,z));
a[i].z=max(x,max(y,z));
a[i].y=x+y+z-a[i].x-a[i].z;
V[i]=a[i].z;
}
sort(V+1,V+n+1);
int cnt=unique(V+1,V+n+1)-V-1;
for(i=1;i<=n;i++) a[i].z=lower_bound(V+1,V+cnt+1,a[i].z)-V;
sort(a+1,a+n+1,cmp);
for(i=1;i<=n;i++) t[i]=i;
sort(t+1,t+n+1,cmp1);
solve(1,n);
for(i=1;i<=n;i++) ans=max(ans,f[i]);
printf("%d\n",ans);
}
BZOJ_2253_[2010 Beijing wc]纸箱堆叠 _CDQ分治+树状数组的更多相关文章
-
【BZOJ2253】[2010 Beijing wc]纸箱堆叠 cdq分治
[BZOJ2253][2010 Beijing wc]纸箱堆叠 Description P 工厂是一个生产纸箱的工厂.纸箱生产线在人工输入三个参数 n p a , , 之后,即可自动化生产三边边长为 ...
-
BZOJ2253 2010 Beijing wc 纸箱堆叠 CDQ分治
这题之前度娘上没有CDQ分治做法,gerwYY出来以后写了一个.不过要sort3遍,常数很大. gerw说可以类似划分树的思想优化复杂度,但是蒟蒻目前不会划分树(会了主席树就懒得去弄了). 嗯 将me ...
-
BZOJ2253: [2010 Beijing wc]纸箱堆叠
题解: 其实就是求三维偏序最长链.类似于三维逆序对,我们可以用树状数组套平衡树来实现. DP方程 :f[i]=max(f[j]+1) a[j]<a[i] 我们按一维排序,另一位建立树状数组,把第 ...
-
BZOJ 2253: [2010 Beijing wc]纸箱堆叠
题目 2253: [2010 Beijing wc]纸箱堆叠 Time Limit: 30 Sec Memory Limit: 256 MBSubmit: 239 Solved: 94 Descr ...
-
BZOJ_3262_陌上花开_CDQ分治+树状数组
BZOJ_3262_陌上花开_CDQ分治+树状数组 Description 有n朵花,每朵花有三个属性:花形(s).颜色(c).气味(m),用三个整数表示. 现在要对每朵花评级,一朵花的级别是它拥有的 ...
-
BZOJ_3295_[Cqoi2011]动态逆序对_CDQ分治+树状数组
BZOJ_3295_[Cqoi2011]动态逆序对_CDQ分治+树状数组 Description 对于序列A,它的逆序对数定义为满足i<j,且Ai>Aj的数对(i,j)的个数.给1到n的一 ...
-
【BZOJ】2253: [2010 Beijing wc]纸箱堆叠
题意 三维严格偏序最长链.(\(n \le 50000\)) 分析 按第一维排序然后以第二和第三维作为关键字依次加入一个二维平面,维护前缀矩形最大值. 题解 当然可以树套树....可是似乎没有随机化算 ...
-
【BZOJ4553】[Tjoi2016&;Heoi2016]序列 cdq分治+树状数组
[BZOJ4553][Tjoi2016&Heoi2016]序列 Description 佳媛姐姐过生日的时候,她的小伙伴从某宝上买了一个有趣的玩具送给他.玩具上有一个数列,数列中某些项的值可能 ...
-
BZOJ 1176 Mokia CDQ分治+树状数组
1176: [Balkan2007]Mokia Time Limit: 30 Sec Memory Limit: 162 MBSubmit: 1854 Solved: 821[Submit][St ...
随机推荐
-
剖析width、height继承
在CSS这个一切皆为框的世界里,我们今天再来探究探究width与height. 我靠,width与height有什么好探究的,不就是设定元素的宽.高吗?大不了还要区分标准盒子模型和IE盒子模型的区别, ...
-
One Time Auth
One Time Auth One-time authentication (shortened as OTA) is a new experimental feature designed to i ...
-
Android应用插件式开发解决方法
转自:http://blog.csdn.net/arui319/article/details/8109650 一.现实需求描述 一般的,一个Android应用在开发到了一定阶段以后,功能模块将会越来 ...
-
Hummer框架平台介绍
三年工作过程中经常会用到使用Java开源框架,但经常会遇到重新组合比较麻烦,本次采用目前主流开源框架及插件整理出一套融合开发.测试.部署整个流程的平台. 本平台采用Hummer代号,是悍马和蜂鸟分意思 ...
-
关于IPv6
App在本地IPv6的测试环境下运行一切正常,结果又是被拒,悲剧原因还是IPv6的问题;求解决方法被拒原因We discovered one or more bugs in your app when ...
-
DEDE提高生成HTmL的速度
1.找到include/inc/inc_fun_SpGetArcList.php打开之. 2.查找以下代码: for($i=0;$i<$ridnum;$i++){ if($tps ...
-
Eclipse 基础操作与设置
1.快捷键 ctrl+F 在某个文档里搜索对应字段 ctrl+H 全文件查询对应字段 ctrl +shift +R 快速查找某个java类 ctrl +shift +O 自动导入需要的包,删除没用过的 ...
-
UVA140-Bandwidth(搜索剪枝)
Problem UVA140-Bandwidth Time Limit: 3000 mSec Problem Description Given a graph (V, E) where V is ...
-
js判断数组是否包含某个字符串变量
最近碰到一个这样的现象,后台返回的数据中,数组里面有一些有变量值,有一些没有变量值. 举个例子,比如后台返回的例子是这样的: var arr=[ { "status":" ...
-
Shape流动效果
<Window x:Class="MvvmLight1.MainWindow" xmlns="http://schemas.microsoft.com/winfx/ ...