百度之星Astar2012程序设计大赛 初赛试题(二)

百度之星Astar2012程序设计大赛初赛试题

————及答案（第二场）

A：度度熊就是要刷排名第一

一天度度熊在Baidu游戏大厅中发现了一个隐藏的神奇游戏，叫做“度度熊的逆袭”。度度熊很好奇到底是什么情况，于是就进入了游戏。这个游戏很神奇，游戏会给出n个数Ai，度度熊可以任意从中选取一些数，一个数可以选任意多次。选好之后度度熊得到的分数为度度熊选出的数的Xor(异或)值。度度熊顿时产生了兴趣，决心要刷至Ranklist的第一名。但是度度熊犯难了，度度熊不知道自己给出的方案是不是最好的，于是度度熊找到了你，希望你告诉他对于某个回合，度度熊能得到的最高分和第二高分是多少？

输入

第1行1个数n，接下来1行n个整数表示Ai, (0<=Ai<231)

1<=n<=105

输出

输出一行两个数，表示度度熊能够得到的最高分和第二高分为多少

样例输入

2

5 3

样例输出

6 5

#include

main()

{

long a[100000],i,max1,max2,j,n;

scanf("%ld",&n);

for(i=0;i

scanf("%ld",&a[i]);

max1=0;

for(i=0;i

for(j=i+1;j

if(max1

{

max2=max1;

max1=a[i]^a[j];

}

printf("%ld %ld",max1,max2);

}

B：度度熊的礼物

度度熊拥有一个自己的Baidu空间，度度熊时不时会给空间朋友赠送礼物，以增加度度熊与朋友之间的友谊值。度度熊在偶然的机会下得到了两种超级礼物，于是决定给每位朋友赠送一件超级礼物。不同类型的朋友在收到不同的礼物所能达到的开心值是不一样的。开心值衡量标准是这样的：每种超级礼物都拥有两个属性(A, B)，每个朋友也有两种属性(X, Y)，如果该朋友收到这个超级礼物，则这个朋友得到的开心值为A*X + B*Y。

由于拥有超级礼物的个数限制，度度熊很好奇如何分配这些超级礼物，才能使好友的开心值总和最大呢？

输入

第一行n表示度度熊的好友个数。

接下来n行每行两个整数表示度度熊好朋友的两种属性值Xi, Yi。

接下来2行，每行三个整数k

i , A

i

, B

i

，表示度度熊拥有第i种超级礼物的

个数以及两个属性值。

1<=n<=1000, 0<=X

i ,Y

i

, A

i

, B

i

1+k

2

>=n

输出

输出一行一个值表示好友开心值总和的最大值样例输入

4

3 6

7 4

1 5

2 4

3 3 4

3 4 3

样例输出

118

提示

送给第一种礼物的人有1，3，4，送给第二种礼物的人有2

#include

#include

#include

#include

using namespace std;

struct dat{

double x, y, z;

double v;

dat(double a, double b, double c, double d):x(a), y(b), z(c), v(d){} dat(){}

};

struct Val{

int i, j;

double v;

Val(int ti, int tj, double tv):i(ti), j(tj), v(tv){}

Val(){}

};

const int M = 1001;

dat web[M];

vector val;

double S(int i, int j){

return (web[j].x-web[i].x) * (web[j].x-web[i].x) +

(web[j].y-web[i].y) * (web[j].y-web[i].y) +

(web[j].z-web[i].z) * (web[j].z-web[i].z);

}

bool cmp(const dat& a, const dat& b){

return a.v

}

bool cmp2(const Val& a, const Val& b){ return a.v

}

int faaa[M];

int find(int a){

int x = a;

while(x!=faaa[x]) x = faaa[x];

while(a!=faaa[a]){

int t = a;

a = faaa[a];

faaa[t] = x;

}

return a;

}

int main()

{

int n, k;

double t, max=0.0, x, y, z;

cin>>n>>k;

for(int i=0; i

faaa[i] = i;

cin>>x>>y>>z;

t = x*x+y*y+z*z;

web[i] = dat(x,y,z,t);

val.push_back(Val(i, i, t) );

for(int j=0; j

val.push_back(Val(i, j, S(i, j)) ); }

}

sort(val.begin(), val.end(), cmp2); int dif = n-k;

int i;

for(i=0; dif; i++){

int fa = find(val[i].i);

int fb = find(val[i].j);

if(fa != fb){

faaa[fa] = fb;

dif --;

}

}

while(val[i].i!=val[i].j && find(val[i].i) == find(val[i].j)) i++;

printf("%.6lf\n", val[i].v);

return 0;

}

C：网页聚类

有N（N2+ (y_j-y_i)2 + (z_j-z_i)2。请求出最大的t，使得N个网页可以聚成K类，其中每个类至少包含一个网页，且任意两个位于不同类中网页的相似度都至少为t。

输入

第一行包含两个整数N和K，后面N行每行三列，分别为x、y、z。

输出

最大的t的值，使用四舍五入在小数点后保留六位小数。

样例输入

5 3

0.1 0.2 0.4

0.2 0.8 0.7

0.3 0.4 0.5

0.0 0.5 0.0

0.3 0.3 0.2

样例输出

0.170000

D：小王子的表演

为了庆祝女王的生日，王宫前的广场上正举行着一场神枪手的表演赛。这些神枪手中包括军队里的射击天才，山中的顶级猎人，异国的神奇牛仔……来自五湖四海的高手汇聚一堂。在比赛中技压群雄的人，不仅仅能给女王的生日添上华丽的祝福，还能够获得无上的荣誉。

比赛的规则很简单。场中存在着N个靶子，每个枪手允许在场内任何一点向任意方向射击一次，穿透最多靶子数目的枪手就是胜利者。从广场的平面图来看，

每个靶子都可以被认为是一个点，并且第i个靶子的运动轨迹是以点(x

i ,y

i

)为起

点，点(x

i +a

i

,y

i

+b

i

)为终点的线段。发令枪响的那一刻，每个靶子同时从起点到

终点开始匀速运动。虽然靶子各自的速度不尽相同，但是所有的靶子将会在10秒后同时到达终点，选手必须在这10秒之内（包含开始和结束的瞬间）进行射击。子弹的速度可以认为是无穷大并且射击场没有边界。

小王子偷偷地也报名参加的这次比赛，希望能在母亲的生日上表现出自己的成长。聪明的小王子早就通过观察把所有靶子的运动情况强记在心，那么，小王子最完美的射击究竟能够穿透多少靶子呢？

输入

第一行只有一个整数，N， (1<=N<=50)

之后每一行包含4个整数，x

i ,y

i

,a

i

,b

i

，分别表示第i的靶子运动轨迹的起

点(x

i ,y

i

)，以及方向(a

i

,b

i

)，假设这些整数的绝对值都不大于1000。

输出

只需要输出一个整数，表示最优情况下小王子一发子弹能够击穿的靶子数目样例输入

9

-14 -14 6 0

-12 -14 0 2

-10 -12 0 -2

-12 -12 2 0

-14 -14 0 6

-8 -14 0 6

-8 -8 -6 0

-13 -11 1 2

-9 -11 -1 2

样例输出

4

提示

两个靶子可能会在某些时刻重叠在一起，此时它们不会发生碰撞而是沿着各自的轨迹继续运动下去。数据中没有两个运动完全相同的靶子。