整体评价：其实难度梯度还算合理的，但主要有两个问题。一个是没有好写题，DEFG 几个校队题写起来都很难受。另一个是 D 题位置不太合理，放太靠前搞人心态。以上两点导致本场比赛许多人体验不佳，实际难度比设计偏难。
A题 - 卷无止境
题意：给你竞赛加分政策以及某个人的奖项，让你算他能加多少分。
签到题，没啥好说的，抄数字的时候别看花眼就行。
这哥 7 try ，不知道在想啥。
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
| #include<bits/stdc++.h>
using namespace std;
int n,a,b,c;
int d[110];
int e[10][10]={
{},
{200,100,50,25},
{100,75,25,15},
{75,25,15,15},
{20,15,10,5},
};
void clr(){
fill(d+1,d+30+1,0);
}
int main(){
int t;
scanf("%d",&t);
while(t --> 0){
clr();
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d%d%d",&a,&b,&c);
d[a]=max(d[a],e[b][c]);
}
int ans=0;
for(int i=1;i<=30;i++){
ans+=d[i];
}
printf("%d\n",ans);
}
return 0;
}
|
B题 - 测样例
题意：给你 n ，问你 ∑i=1ni(i−1) ，n≤3×106 。
跟网络赛思路一样的题，van 老师在题目里提示了你数据范围、计算公式、输入输出方法，还提醒你测样例。这样都不过就说不过去了。
首先有公式 ∑i=1ni2=6n(n−1)(2n−1) ，上面那一坨乘起来要爆 unsigned long long ，但是易证 n,n−1,2n−1 中至少有一个是 2 的倍数，并且至少有一个是 3 的倍数。因此先分别把 2 和 3 除掉，再乘起来就不会爆 unsigned long long 。记得要用 ull ，普通 ll 是不够的。当然如果你 int128 玩的够 6 也可以直接算。
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| #include<bits/stdc++.h>
using namespace std;
unsigned long long n;
int main(){
int t=0;
scanf("%d",&t);
while(t --> 0){
scanf("%llu",&n);
unsigned long long a[3]={n,n+1,2*n+1};
for(int i=0;i<3;i++){
if(a[i]%2==0){
a[i]/=2;
}
if(a[i]%3==0){
a[i]/=3;
}
}
printf("%llu\n",a[0]*a[1]*a[2]-(1+n)*n/2);
}
return 0;
}
|
C题 - 又是杠杆
题意：一根无重杠杆上等间隔分布 n 个点，初始第 i 个点有质量为 a[i] 的物品。现在可以从 n 个点中选一个作为支点，并将一个质量为 x 的物品放在 n 个点中的任意一点。问你要使杠杆平衡最小的 x 是多少。答案用分数表示。
我比较喜欢的一道小思维。
第 k 个点的左侧力矩为 ∑i−1k−1(k−i)×a[i]（假设每个点间距都是 1 ）。n2 去算太慢了，但是可以发现支点每往后移动一格，力矩增量实际上就是左边所有数的和。也就是说
Lk=i=1∑k−1(k−i)×a[i]Lk+1=i=1∑k(k+1−i)×a[i]Lk+1−Lk=i=1∑k−1[(k+1−i)−(k−i)]×a[i]+a[k]=i=1∑ka[i].
因此前缀和的前缀和就是每个点的力矩，正着求一遍再反着求一遍就可以得到每个点的左右力矩。由于要求最小的 x 且答案可以是分数，因此直接放到最远的 1 或者 n ，然后力矩差除以放置的距离就是支点放在这的答案。统计最小的答案即可。
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
| #include<bits/stdc++.h>
using namespace std;
int n,a[210000];
long long s[210000],t[210000];
long long u[210000],v[210000];
long long gcd(long long x,long long y){
return y == 0 ? x : gcd(y,x%y);
}
bool cmp(long long x1,long long y1,long long x2,long long y2){
return x1*y2<x2*y1;
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
}
for(int i=1;i<=n;i++){
s[i]=s[i-1]+a[i];
u[i]=u[i-1]+s[i-1];
}
for(int i=n;i>=1;i--){
t[i]=t[i+1]+a[i];
v[i]=v[i+1]+t[i+1];
}
long long ax=1,ay=0;
for(int i=1;i<=n;i++){
if(u[i]==v[i]){
ax=0;
ay=1;
break;
}
else if(u[i]>v[i]){
if(i!=n && cmp(u[i]-v[i],n-i,ax,ay)){
long long d=gcd(u[i]-v[i],n-i);
ax=(u[i]-v[i])/d;
ay=(n-i)/d;
}
}
else{
if(i!=1 && cmp(v[i]-u[i],i-1,ax,ay)){
long long d=gcd(v[i]-u[i],i-1);
ax=(v[i]-u[i])/d;
ay=(i-1)/d;
}
}
}
printf("%lld/%lld\n",ax,ay);
return 0;
}
|
施工中……
