HDu 4742 Pinball Game 3 D(三次元LIS&cdq分治&BITメンテナンス最値)
Pinball Game 3D
Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 688 Accepted Submission(s): 276
Problem Description
RD is a smart boy and excel in pinball game. However, playing common 2D pinball game for a great number of times results in accumulating tedium.
Recently, RD has found a new type of pinball game, a 3D pinball game. The 3D pinball game space can be regarded as a three dimensional coordinate system containing N balls. A ball can be considered as a point. At the beginning, RD made a shot and hit a ball. The ball hit by RD will move and may hit another ball and the “another ball” may move and hit another another ball, etc. But once a ball hit another ball, it will disappear.
RD is skilled in this kind of game, so he is able to control every ball's moving direction. But there is a limitation: if ball A's coordinate is (x1,y1,z1) and ball B's coordinate is (x2,y2,z2), then A can hit B only if x1 <= x2 and y1 <= y2 and z1 <= z2.
Now, you should help RD to calculate the maximum number of balls that can be hit and the number of different shooting schemes that can achieve that number. Two schemes are different if the sets of hit balls are not the same. The order doesn't matter.
Input
The first line contains one integer T indicating the number of cases.
In each case, the first line contains one integer N indicating the number of balls.
The next N lines each contains three non-negative integer (x, y, z), indicating the coordinate of a ball.
The data satisfies T <= 3, N <= 10
5, 0 <= x, y, z <= 2
30, no two balls have the same coordinate in one case.
Output
Print two integers for each case in a line, indicating the maximum number of balls that can be hit and the number of different shooting schemes. As the number of schemes can be quite large, you should output this number mod 2
30.
Sample Input
Sample Output
Source
2013 ACM/ICPC Asia Regional Hangzhou Online
Recommend
liuyiding | We have carefully selected several similar problems for you: 5061 5059 5058 5053 5052
タイトル:
あなたにn(1 e 5)個の三元グループをあげて、それからあなたにこのn個の三元グループのLISを求めます.というLISのシナリオ数です.一方の三元祖aが他方の元祖bより大きい条件はax>=bx,ay>=by,az>=bzである.
考え方:
1次元ならやりやすいです.順番を並べたら終わりです.2次元の話.xをソートします.次に、dp[i]は、iで終わる最長シーケンス長.dp[i]=max(dp[i],dp[j]+1)を表す.j詳細は、コードを参照してください.
Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 688 Accepted Submission(s): 276
Problem Description
RD is a smart boy and excel in pinball game. However, playing common 2D pinball game for a great number of times results in accumulating tedium.
Recently, RD has found a new type of pinball game, a 3D pinball game. The 3D pinball game space can be regarded as a three dimensional coordinate system containing N balls. A ball can be considered as a point. At the beginning, RD made a shot and hit a ball. The ball hit by RD will move and may hit another ball and the “another ball” may move and hit another another ball, etc. But once a ball hit another ball, it will disappear.
RD is skilled in this kind of game, so he is able to control every ball's moving direction. But there is a limitation: if ball A's coordinate is (x1,y1,z1) and ball B's coordinate is (x2,y2,z2), then A can hit B only if x1 <= x2 and y1 <= y2 and z1 <= z2.
Now, you should help RD to calculate the maximum number of balls that can be hit and the number of different shooting schemes that can achieve that number. Two schemes are different if the sets of hit balls are not the same. The order doesn't matter.
Input
The first line contains one integer T indicating the number of cases.
In each case, the first line contains one integer N indicating the number of balls.
The next N lines each contains three non-negative integer (x, y, z), indicating the coordinate of a ball.
The data satisfies T <= 3, N <= 10
5, 0 <= x, y, z <= 2
30, no two balls have the same coordinate in one case.
Output
Print two integers for each case in a line, indicating the maximum number of balls that can be hit and the number of different shooting schemes. As the number of schemes can be quite large, you should output this number mod 2
30.
Sample Input
2
3
2 0 0
0 1 0
0 1 1
5
3 0 0
0 1 0
0 0 1
0 2 2
3 3 3
Sample Output
2 1
3 2
Hint
In the first case, RD can shoot the second ball at first and hit the third ball indirectly. In the second case, RD can shoot the second or the third ball initially and hit the fourth ball as well as the fifth ball. Two schemes are both the best.
Source
2013 ACM/ICPC Asia Regional Hangzhou Online
Recommend
liuyiding | We have carefully selected several similar problems for you: 5061 5059 5058 5053 5052
タイトル:
あなたにn(1 e 5)個の三元グループをあげて、それからあなたにこのn個の三元グループのLISを求めます.というLISのシナリオ数です.一方の三元祖aが他方の元祖bより大きい条件はax>=bx,ay>=by,az>=bzである.
考え方:
1次元ならやりやすいです.順番を並べたら終わりです.2次元の話.xをソートします.次に、dp[i]は、iで終わる最長シーケンス長.dp[i]=max(dp[i],dp[j]+1)を表す.j
#include<algorithm>
#include<iostream>
#include<string.h>
#include<stdio.h>
using namespace std;
const int INF=0x3f3f3f3f;
const int maxn=100010;
const int mod=1<<30;
typedef long long ll;
struct node
{
int x,y,z;
inline bool operator <(const node& tt) const
{
if(x!=tt.x)
return x<tt.x;
if(y!=tt.y)
return y<tt.y;
return z<tt.z;
}
} po[maxn];
int dp[maxn],sy[maxn],sz[maxn],mv[maxn],ans;
int tmp[maxn<<1],ty[maxn],ptr;
ll num[maxn],nv[maxn],ansn;
bool cmp(int a,int b)// y . y i+1 i .
{
if(po[a].y!=po[b].y)
return po[a].y<po[b].y;
return a<b;
}
void update(int x,int v,ll d,int mn)
{
for(int i=x;i<=mn;i+=i&-i)
{
if(v>mv[i])
mv[i]=v,nv[i]=d;
else if(v==mv[i])
nv[i]+=d;
}
}
int qu(int x,ll &nn)
{
int ret=0;
for(int i=x;i>0;i-=i&-i)
{
if(ret<mv[i])
ret=mv[i],nn=nv[i];
else if(mv[i]==ret)
nn+=nv[i];
}
return ret;
}
void solve(int l,int r)
{
if(l==r)
{
if(dp[l]>ans)
ans=dp[l],ansn=num[l];
else if(dp[l]==ans)
ansn+=num[l];
sz[l]=po[l].z;
return;
}
int mid=(l+r)>>1,le=l,ri=mid+1,len=r-l+1,ml=mid-l+1,lim,h,i;
memmove(tmp+ptr,sy+l,len*sizeof(int));
for(i=0;i<len;i++)
if(tmp[ptr+i]<=mid)// 。
sy[le++]=tmp[ptr+i];
else
sy[ri++]=tmp[ptr+i];
ptr+=len;
solve(l,mid);
lim=ptr,ptr-=len;
for(i=1;i<=ml;i++)
mv[i]=0;
for(i=ptr;i<lim;i++)
{
if(tmp[i]<=mid)
{
h=lower_bound(sz+l,sz+l+ml,po[tmp[i]].z)-(sz+l)+1;
update(h,dp[tmp[i]],num[tmp[i]],ml);
continue;
}
h=lower_bound(sz+l,sz+l+ml,po[tmp[i]].z)-(sz+l);
if(h>=ml||sz[l+h]>po[tmp[i]].z)
h--;
if(h>=0)
{
ll cc=0;
int tt=qu(h+1,cc)+1;
if(tt>dp[tmp[i]])
dp[tmp[i]]=tt,num[tmp[i]]=cc;
else if(tt==dp[tmp[i]]&&tt!=1)
num[tmp[i]]+=cc;
}
}
solve(mid+1,r);
merge(sz+l,sz+l+ml,sz+l+ml,sz+l+len,ty);
memmove(sz+l,ty,len*sizeof(int));
}
int main()
{
int t,n,i;
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
for(i=1;i<=n;i++)
scanf("%d%d%d",&po[i].x,&po[i].y,&po[i].z);
ansn=ptr=ans=0;
sort(po+1,po+n+1);
for(i=1;i<=n;i++)
sy[i]=i,dp[i]=1,num[i]=1;
sort(sy+1,sy+n+1,cmp);
solve(1,n);
printf("%d %I64d
",ans,ansn%mod);
}
return 0;
}
/*
。 。 y i+1 i 。
。
1
17
2 0 0
2 1 1
1 2 1
1 0 0
0 0 1
0 2 0
0 2 2
0 1 1
2 0 1
1 2 2
0 1 0
2 0 2
2 2 2
0 1 2
1 0 2
1 1 1
0 0 2
*/