A 题 Vasily the Bear and Triangle
题目大意
一个等腰直角三角形 ABC，角 ACB 是直角，AC=BC，点 C 在原点，让确定 A 和 B 的坐标，使得三角形包含一个矩形，这个矩形一个角在原点，另一个点在 (x, y) 处，并且三角形 ABC 的面积尽量小
将 A B 两点按照 x 坐标从小到大输出
做法分析
A B 两点必然在坐标轴上，且线段 AB 经过点 (x, y)，那么简单分类讨论下就行了
交之前犹豫了一下，10分钟才提交...
参考代码
#include <iostream>
#include <cstring>
#include <cstdio> using namespace std; const int N=; int x, y; int main() {
scanf("%d%d", &x, &y);
if(x> && y> || x< && y<) {
if(x<) {
printf("%d %d %d %d\n", x+y, , , x+y);
}
else {
printf("%d %d %d %d\n", , x+y, x+y, );
}
}
else {
if(x<) {
printf("%d %d %d %d\n", x-y, , , y-x);
}
else {
printf("%d %d %d %d\n", , y-x, x-y, );
}
}
return ;
}
A
B 题 Vasily the Bear and Fly
题目大意
在平面上有 2*m(1≤m≤10) 个同样半径的圆。他们编号分别为 1~2*m，分上下两排排列.
第 1 到 m 个圆的圆心坐标分别为：(2R-R, 0), (4R-R, 0),...,(2mR-R, 0)
第 m+1 到第 m+m 个圆的圆心坐标分别为：(2R-R, 2R), (4R-R, 2R),...,(2mR-R, 2R)
有一只 fly（苍蝇？）在这个平面上运动了 m 次，这 m 次运动分别编号为 0~(m-1)，编号为 i 的那次运动从第 1+i/m 个圆的圆心运动到第 m+1+i%m 个圆的圆心，且走最短路，fly 走过的路径必须包含在这 2*m 个圆确定的区域中，不能走到外面的其他地方
现在问，这只 fly 的 m 次运动中，每次运动走过的平均距离是多少
做法分析
典型的数学题，当时看见，菊花莫名其妙的一紧，脚趾头都抓紧了......
观察这 2*m 个圆的圆心坐标不难发现，他们分成了上下两排，同一排相邻的两个圆相切，上下相邻的两个圆相切
再观察 fly 每次运动走的圆的分布规律，不难发现是每次选定一个下面的圆的圆心，分别以上面的圆的圆心为目的点走一次最短路，所以总共有 m 次运动
那么一个最通常的想法就是：求出这 m 次运动总共走过的距离
先看看最短路吧：
由于每次一定是一个圆在下面，一个圆在上面，那么可以这样搞：
当两个圆相邻时（列号差为 0），最短路是 2R
当两个圆的列号差为 1 时，最短路是 2R+√2R
当两个圆的列号差为 2 时，最短路是 2R+2√2R
当两个圆的列号差为 3 时，最短路是 4R+2√2R
当两个圆的列号差为 4 时，最短路是 6R+2√2R
当两个圆的列号差为 5 时，最短路是 8R+2√2R
......
将他们存进一个数组 A 中，A[i] 表示列号差为 i 的最短路长度
以 m 为单位，看看每次运动的起始点和终止点
前 m 次运动：起始点始终是下面第 1 个圆，终止点从上面第 1 个圆变化到第 m 个圆
接下来的 m 次运动：起始点始终是下面第 2 个圆，终止点从上面第 1 个圆变化到第 m 个圆
再接下来的 m 次运动：起始点始终是下面第 3 个圆，终止点从上面第 1 个圆变化到第 m 个圆
......
细心的读者在这里的时候估计已经知道该怎么做了，还没想出来的朋友可以接着往下看
从上面可以看出：起始点是在不停的往前走的，而终止点始终是上面的圆从 1 到 m
我们再以 m 为单位，看看他们的距离和
前 m 次运动的距离和我们可以求出来：sum1=∑A[i]
那么接下来的 m 次运动的距离和呢：sum2=sum-A[m-1]+A[1]
再接下来的的 m 次运动的距离和呢：sum3=sum2-A[m-2]+A[2]
第 4 个 m 次运动的距离和：sum4=sum3-A[m-3]+A[3]
......
相信看到这里，大家都知道该怎么做了 o(m) 的扫一遍，用两个指针辅助，这样就可以求出来了
参考代码
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath> using namespace std; const int N=; int m;
double R, A[N]; void init() {
A[]=, A[]=+sqrt();
for(int i=; i<m; i++) A[i]=*(i-)+*sqrt();
} int main() {
scanf("%d%lf", &m, &R);
init();
double ans=;
for(int i=; i<m; i++) {
ans+=A[i];
}
int p1=, p2=m-;
double last=ans;
for(int i=; i<m; i++) {
last=last-A[p2]+A[p1];
ans+=last;
p1++, p2--;
}
printf("%lf\n", ans/m/m*R);
return ;
}
B
C 题 Vasily the Bear and Sequence
题目大意
给了 n(1≤n≤10) 个不同的数，要求选出一些数出来，使得这些数按位取与之后的数在二进制下，最低位的 1 所在的位尽量高，如果有多重方案，输出选取数的数量最大的一个方案
做法分析
初一看很神，其实仔细想一下不难发现这题比 B 题还水...
考虑最后选取的数按位取与之后得到的数，设为 sum
要使 sum 在二进制下 1 的最低位最高，也就是说，这一位 1 以后，所有的数都应该是 0
想到这里，反应比较快的读者肯定知道该怎么做了
枚举最低位，设为 pos，先在所有数中选出二进制表示下，在 pos 位为 1，的那些数，如果这些数按位取与，能够使得所有低于 pos 位的二进制位全为 0，那么这些数就是一个合法的答案，当然，如果我们是从高位往地位枚举的，这些数就是我们最后的答案了
参考代码
#include <cstring>
#include <cstdio>
#include <iostream> using namespace std; int A[], n;
bool vs[]; int main() {
scanf("%d", &n);
for(int i=; i<n; i++) scanf("%d", &A[i]);
for(int i=; i>=; i--) {
bool flag=;
memset(vs, , sizeof vs);
for(int j=; j<n; j++) if(A[j]&(<<i)) vs[j]=;
for(int pos=i-; pos>= && flag; pos--) {
bool all=;
for(int j=; j<n && !all; j++) if(vs[j]) {
if(!(A[j]&(<<pos))) all=;
}
if(!all) flag=;
}
if(flag) break;
}
int cnt=;
for(int i=; i<n; i++) if(vs[i]) cnt++;
printf("%d\n", cnt);
for(int i=; i<n; i++) if(vs[i]) {
printf("%d", A[i]);
cnt--;
if(!cnt) printf("\n");
else printf(" ");
}
return ;
}
C