前行 - AtCoder Beginner Contest 117 | Lucky_Glass's Blog
0%

前行 - AtCoder Beginner Contest 117

春节了,比赛还真多;
打完 AtCoder 休息一会就打 Codeforces ……


『A : Entrance Examination』〔传送门〕

「题意」

明天要考试了,Taro 不得不多花一点时间复习。
Taro准备学习 $T$ 个小时,但是他还想玩……幸运的是,他可以到另一个世界去,在那里时间过得更快 —— 在那个世界的 $X$ 小时相当于原来世界的 $1$ 小时。
Taro 决定去那个世界学习,请告诉他他学习完后原来世界经过了多少个小时。

「解析」

这个不用解释吧……小学应用题的感觉。
“总数/每份大小”= $\frac{T}{X}$ 。

「源代码」

1
2
3
4
5
6
7
8
9
10
11
/*Lucky_Glass*/
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int main(){
int A,B;
scanf("%d%d",&A,&B);
printf("%.5lf\n",A*1.0/B);
return 0;
}

『B : Entrance Examination』〔传送门〕

「题意」

Taro 正复习,突然被一道题难住了——“有 $n$ 条线段,给出它们的长度 $l_1,l_2,…,l_n$ ,将它们首尾相连,问它们能否连成一个 $n$ 边形”。
已知如果最大边小于其他边之和,就可以构成 $n$ 边形。
你能帮他完成吗?

「解析」

好心的出题人还把方法说出来了……
边输入边算所有边的总和 $Sum$ 和最大值 $Max$,则按照题目意思就是 $Max<Sum-Max$ 就可以构成 $n$ 边形,否则不行。

「源代码」

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/*Lucky_Glass*/
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=10;
int n,num[N+7],Max,Sum;
int main(){
scanf("%d",&n);
for(int i=0;i<n;i++)
scanf("%d",&num[i]),
Sum+=num[i],
Max=max(Max,num[i]);
if(Max<Sum-Max) printf("Yes\n");
else printf("No\n");
return 0;
}

『C : Entrance Examination』〔传送门〕

「题意」

重要复习完了,Taro 回到原来的世界,发现还能玩一会~
Taro 开始玩一个游戏:“工厂里有 $n$ 个产品需要加工,你有 $m$ 个机器人,一开始你可以把机器人放在任意的一个产品的位置,机器人到达一个产品后就会完成加工,你可以通过操控机器人移动以完成所有产品的加工。工厂可以抽象为数轴,产品的位置用一个数字 $X_i$ 描述,表示它在数轴上的位置;机器人每一次可以向左或向右移动 $1$ 个单位长度”。
但是机器人移动十分耗电,Taro 想知道要完成所有加工 $m$ 个机器人移动的次数的总和最小为多少。

「解析」

贪心地想,我们一定不能让 $m$ 个机器人的路径有任何重叠,那么我们大概可以想到将原来的数 $X_1$ ~ $X_n$ 分成 $m$ 个段,每一个段由一个机器人完成;而在一个段内,机器人也可以一次性(路径不重叠)地完成该段的加工,即从段的端点移动到另一个端点。因此对于每一个段,机器人移动的距离就是它的左右端点的距离。

现在我们相当于得到了下面这个图:

image1

上图机器人移动的距离之和就是 $(X_3-X_1)+(X_6-X_4)+(X_8-X_7)$ ,然后就会剩下如图所示的 $m-1$ 条橙色线段没有走,将答案转换一下就是 $(X_8-X_1)-(X_4-X_3)-(X_7-X_6)$ 。那么我们就要让橙色线段尽可能大——将所有相邻点之间的间隔排序后最大的 $m-1$ 个就是橙色线段。

「源代码」

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/*Lucky_Glass*/
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=1e5;
int num[N+7],n,m,bet[N+7];
long long ans;
int main(){
scanf("%d%d",&n,&m);
for(int i=0;i<m;i++)
scanf("%d",&num[i]);
sort(num,num+m);
for(int i=1;i<m;i++)
bet[i]=num[i]-num[i-1],ans+=bet[i];
sort(bet+1,bet+m);
n--;
for(int i=m-1;i>=1&&n;i--,n--)
ans-=bet[i];
printf("%lld\n",ans);
return 0;
}

『D : Entrance Examination』〔传送门〕

「题意」

这是一个充满了位运算的世界,Taro 遇到了一个问题:“有 $n$ 个整数 $A_i$ ( $0\leq A_i \leq 10^{12}$ ),再给出一个数 $K$ ,你要找出一个数 $X$,使得 $0\leq X \leq K$ 时 $(\sum_{i=1}^nA_i \text{xor}X)$ 最大”。(xor 是异或)

求这个最大值。

「解析」

把原来的 $A_i$ 拆成二进制,可以算出 $log_210^{12}<50$ ,所以我们用 int tot[50] 记录所有 $A_i$ 的第 $i$ 位之和。如果 $A_i$ 的二进制第 $i$ 位为 $1$ ,我们就在 tot[i] 中 +1;如果为 $0$ ,就在 tot[i] 中 -1。

最后 tot[i] 可能有正有负。如果为正,就说明第 $i$ 位上 $1$ 比 $0$ 多,则在该位要得到尽可能大的数,$X$ 的第 $i$ 位应为 $0$ ,否则 $X$ 的第 $i$ 位为 $1$。但是还要考虑 $X\leq K$ ,像数位 DP 一样处理,具体见代码。

「源代码」

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
/*Lucky_Glass*/
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
int n;
long long k,ans;
int tot[55];
long long num[int(1e5)+5];
int main(){
scanf("%d%lld",&n,&k);
for(int i=0;i<n;i++){
scanf("%lld",&num[i]);
for(int j=0;j<=50;j++)
if(num[i]&(1ll<<j))
tot[j]++;
else
tot[j]--;
}
long long F=0;
bool fir=true;
for(int i=(int)floor(log2(k));i>=0;i--){
if(fir){
if(((1ll<<i)&k) && tot[i]<0) F|=(1ll<<i);
else if(((1ll<<i)&k)) fir=false;
}
else
if(tot[i]<0) F|=(1ll<<i);
}
for(int i=0;i<n;i++)
ans+=F^num[i];
printf("%lld\n",ans);
return 0;
}

The End

Thanks for reading!

Email: lucky_glass@foxmail.com ,欢迎提问~