稍稍总结一下：铜牌题目难度较低，5题都不涉及数据结构，基本算是思维题。手速快罚时少的话甚至能拿银。复现赛三小时出了5题，应该是当时现场赛的银尾排名了。
A.Xu Xiake in Henan Province
签到题，有手就行
#include <bits/stdc++.h>
using namespace std
;
string res
[] = {"Typically Otaku","Eye-opener","Young Traveller","Excellent Traveller","Contemporary Xu Xiake"};
signed main(){
int t
;
cin
>>t
;
while(t
--){
int cnt
= 0;
for(int i
= 0 ; i
< 4 ; i
++){
int x
; cin
>>x
;
cnt
+= (x
> 0);
}
cout
<<res
[cnt
]<<endl
;
}
}
D. Keiichi Tsuchiya the Drift King
给出a,b,d,r，求w。 要求小车的b边始终要贴在圆弧上且保持相切。
思路：简单计算几何
对于给定的角度d，如果d>=x，如下图。那么直接从左上角连一条线到圆心。这个长度就是路的最大宽度+r。显然很好求。 如果d < x 呢。w显然是比上一个结论要小的。如下图： 可以发现宽度显然小于w，因为左边还有挺大的空隙。那么红线(2)依然很容易求出来的，然而答案不是红线，而应该是黄色的线。所以用公式把黄色线求出来然后 - r 就是答案了。
AC代码：
#include <bits/stdc++.h>
using namespace std
;
signed main(){
int t
;
cin
>>t
;
while(t
--){
double a
,b
,r
,d
;
cin
>>a
>>b
>>r
>>d
;
d
= d
/180*acos(-1);
double red
= sqrt((a
+r
)*(a
+r
)+b
*b
);
double x
= acos((a
+r
)/red
);
if(x
<= d
){
printf("%.12f\n",red
-r
);
}else{
double y
= x
-d
;
double yellow
= red
*cos(y
);
printf("%.12f\n",yellow
-r
);
}
}
}
E. Resistors in Parallel
给了一个并联电阻的阻值计算公式。以及两个限制条件。
对于一个有平方因子的数。他的阻值接近于无穷大。
思路：
总共有1-n，n种选择，每种选择就是这个数的所有约数的倒数的倒数。显然要使得R最小，也就是需要让下面的分子和越大。要让下面的和最大，就是要让项数尽量多，并且，每一项都尽量大，也就是分母尽量小，也就是一个数的约数尽量多，且每个约数尽量小。 仔细想想题目的限制条件，若一个数有平方因子，那么其实平方因子对答案的贡献为0，因为阻值无穷大，倒数就是趋于0。比如 12，有因子，1，2，3，4，6，12，其中 4 和 12 的贡献都为0， 所以12的贡献也就等价于6的贡献。 进一步总结就是找到一个数 x，x <= n，并且 x = 21315171…… 也就是x 是前k个质因子的乘积。 因为这样的数一定是因子数尽量多且每个因子尽量小的数。简单证明就是任意替换一个指数为0，最后的答案是比指数为1的小的。 那问题就简单了，第一步把质因子打表出来，可以发现乘到541的时候就超过 100位数 了。后面的没必要再算。 然后就是计算所有的约数和。 根据公式，下面的分母就是 x，分子就是x的所有约数的和。 利用公式：sum = (20+21+22…)*(30+31+32…)*(50+51+52…) 然后求gcd取最简分数形式就行了 当然 数据范围 巨大。要不用大数板子，要不用java/python，复现赛能交python就写python了
AC代码：
t
= int(input())
li
= [2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127,131,137,139,149,151,157,163,167,173,179,181,191,193,197,199,211,223,227,229,233,239,241,251,257,263,269,271,277,281,283,293,307,311,313,317,331,337,347,349,353,359,367,373,379,383,389,397,401,409,419,421,431,433,439,443,449,457,461,463,467,479,487,491,499,503,509,521,523,541]
def gcd(x
,y
):
if(y
== 0):
return x
else:
return gcd
(y
,x
%y
)
for i
in range(t
):
n
= int(input())
res
= 0
sum1
= 1
for i
in li
:
if(sum1
*i
> n
):
break
res
+= 1
sum1
*= i
res1
= 1
for i
in range(res
):
res1
*= (li
[i
]+1)
g
= gcd
(sum1
,res1
)
print(str(sum1
//g
)+"/"+str(res1
//g
))
F. Honeycomb
给一个这样的迷宫，求 起点S - 终点T 最少要经过几个六角形。
样例输入
1
3 4
+---+ +---+
/ \
/ \
+ +---+ +---+
\ \
/ \
+ + S
+---+ T
+
/ \
/ /
+ +---+ + +
\ \
/ \
+---+ +---+ +
/ /
+ +---+ + +
\
/ \
+---+ +---+ +
\
/ \
/
+---+ +---+
样例输出
7
思路：
显然是一个bfs模板题啊。但是这个迷宫不是简单的二维数组。一开始的想法是，把迷宫压平变成一个二维数组表示的迷宫。但是越想越复杂。后来想直接存字符表示的迷宫就好了啊，而且4050*8050的字符数组也不会爆内存。 然后就是直接码代码了。
AC代码：
#include <bits/stdc++.h>
using namespace std
;
char mp
[4050][8050];
bool vis
[4050][8050];
struct node
{
int x
,y
,step
;
node(){}
node(int _x
,int _y
,int _step
){
x
= _x
;
y
= _y
;
step
= _step
;
}
};
int dir
[][2] = {-2,-6,-2,6,2,-6,2,6,-4,0,4,0};
int dir2
[][2] = {-1,-3,-1,3,1,-3,1,3,-2,0,2,0};
queue
<node
> que
;
int sx
,sy
,tx
,ty
;
int bfs(){
while(!que
.empty()) que
.pop();
que
.push(node(sx
,sy
,1));
vis
[sx
][sy
] = 1;
while(!que
.empty()){
node now
= que
.front();
que
.pop();
if(now
.x
== tx
&& now
.y
== ty
) return now
.step
;
for(int i
= 0 ; i
< 6 ; i
++){
int xx
= now
.x
+ dir
[i
][0];
int yy
= now
.y
+ dir
[i
][1];
int x1
= now
.x
+ dir2
[i
][0];
int y1
= now
.y
+ dir2
[i
][1];
if(mp
[x1
][y1
] == ' ' && !vis
[xx
][yy
]){
vis
[xx
][yy
] = 1;
que
.push(node(xx
,yy
,now
.step
+1));
}
}
}
return -1;
}
signed main(){
int t
;
scanf("%d",&t
);
while(t
--){
int n
,m
;
scanf("%d%d",&n
,&m
);getchar();
for(int i
= 0 ; i
< 4*n
+3 ; i
++){
int pos
= 0;
char ch
;
while((ch
= getchar()) && ch
!= '\n'){
if(ch
== 'S') sx
= i
,sy
= pos
;
if(ch
== 'T') tx
= i
,ty
= pos
;
vis
[i
][pos
] = 0;
mp
[i
][pos
++] = ch
;
}
}
cout
<<bfs()<<endl
;
}
}
I. Distance
给定一条直线上n个点的位置。求 选出1-n个点时 。所有点对的距离和的最大值。
思路：贪心。
选一个点时为0，显然成立。 选两个点时，选最左端和最右端的，显然成立。 选三个点时，选最左端和最右端的，加中间任意一个。因为中间任意一个到这两个点的距离和都等于这两个点本身的距离。 选四个点时，最左端和最右端的点肯定是要选的。假设左右端点的距离为x1那么加入一个点时，距离和增加x1 再加入一个点时仍然要增加x1。且再增加新增的两个点的距离x2。那么显然之前选x1时就已经是最优解，再往后选这两个点都是固定的不会动。那么只能让x2尽量大。也就是选择目前最靠左和最靠右的两个点。 推广结论。 当前选择的点如果是第奇数个，之前说明已经选择了偶数个点。这个点可以任意选，并且加入这个点时，增加的距离就是 前n/2个 点对的距离和。 如下： 加入第5个节点时，增加的距离就是红色部分+绿色部分。 当前选择的点如果是第偶然个，增加的第一部分距离和选择奇数个的相同。第二部分距离，就是他和上一个点的距离。图中蓝色部分
AC代码：
#include <bits/stdc++.h>
#define int long long
using namespace std
;
int a
[100050];
signed main(){
int t
;
cin
>>t
;
a
[0] = 0;
while(t
--){
int n
;
cin
>>n
;
for(int i
= 1 ; i
< n
; i
++){
cin
>>a
[i
];
a
[i
] += a
[i
-1];
}
int sum
= 0;
int pre
= 0;
for(int i
= 1 ; i
<= n
; i
++){
if(i
%2 == 1)
sum
+= pre
;
else{
pre
+= a
[n
-i
/2]-a
[i
/2-1];
sum
+= pre
;
}
if(i
!= n
)
cout
<<sum
<<" ";
else
cout
<<sum
<<endl
;
}
}
}
