2014
03-23

# Roba’s dream

LCY has made comments to HDU-ACM team leaders, “some team leaders can change girl ACMers into their girl friends, it’s a great job; but menjitianya2007 can make his girl friend be an ACM partner, it’s great beyond .”(http://blog.sina.com.cn/s/blog_5dc12a880100c6n1.html) Yes , it is true that there are many lovers in ACM teams, boy ACMers’ nuttiness and patience attract PLMMs. How to catch the girls’ heart? So as to realize roba’s third dream(http://roba.ycool.com/post.1738620.html) , lxhgww decides to invite the lovers in all ACM teams and let them talk something about their love experience.

lxhgww decide to choose at most one of each couple to talk about their experience. He thought people in different height have different love experience, so he would like to invite ACMers with different height to give a talk, what’s more, the shortest one (and also the first one) invited should always be 1.500000m and the (i+1)th ACMer should be exactly taller than the ith one by 0.000001m. Now,lxhgww want to the maximal number of ACMers he can invite. If he invited ACMers whose heights are1.500000,1.500001,but he can’t invite a 1.500002m tall,then 2 will be the maximal number.

The first line is the case number T(<=15).
For each case, there is an integer N(<=1000000) in the first line indicating N couples of lovers.
The next N lines of each case have two numbers round to 6 decimals each, they are the height of the ith couple of ACMers, all are no shorter than 1.5m.,and no higher than 2.0m.

The first line is the case number T(<=15).
For each case, there is an integer N(<=1000000) in the first line indicating N couples of lovers.
The next N lines of each case have two numbers round to 6 decimals each, they are the height of the ith couple of ACMers, all are no shorter than 1.5m.,and no higher than 2.0m.

1
3
1.500000 1.500001
1.500002 1.500001
1.500003 1.500004

2

#include <iostream>
using namespace std;
const int maxn=1100000,maxm=4*maxn;
struct Edge
{
int y;
int ne;
} e[maxm];
int st[maxn],ee;
{
e[ee].y=y;e[ee].ne=st[x];st[x]=ee++;
e[ee].y=x;e[ee].ne=st[y];st[y]=ee++;
}
int c[maxn];
int numn[maxn],numm[maxn],lost[maxn];
void bfs(int k,int col)
{
int i;
c[k]=col;
{
for (i=st[k];i!=-1;i=e[i].ne)
{
numm[col]++;
if (c[e[i].y]==0)
{
c[e[i].y]=col;
s[tail++]=e[i].y;
}
}
}
numn[col]=tail;
}
int main()
{
freopen("in.in","r",stdin);
int cass;
for (scanf("%d",&cass);cass–;)
{
int n;
scanf("%d",&n);
int i,x,y,z1,z2;
memset(st,-1,sizeof(st));
ee=0;
for (i=0;i<n;i++)
{
scanf("%d.%d %d.%d",&z1,&x,&z2,&y);
x=z1*1000000+x-1500000;
y=z2*1000000+y-1500000;
}
memset(c,0,sizeof(c));
memset(numn,0,sizeof(numn));
memset(numm,0,sizeof(numm));
memset(lost,-1,sizeof(lost));
int col=0;
for (i=0;i<maxn;i++) if (c[i]==0)
{
col++;
bfs(i,col);
}
for (i=1;i<=col;i++) numm[i]/=2;
for (i=0;i<maxn;i++) if (numn[c[i]]>numm[c[i]]) if (lost[c[i]]<i) lost[c[i]]=i;
for (i=0;i<maxn;i++)
if (lost[c[i]]==i) break;
printf("%d\n",i);
}
return 0;
}

1. 约瑟夫也用说这么长……很成熟的一个问题了，分治的方法解起来o(n)就可以了，有兴趣可以看看具体数学的第一章，关于约瑟夫问题推导出了一系列的结论，很漂亮