春节了,比赛还真多;
打完 AtCoder 休息一会就打 Codeforces ……
『A : Entrance Examination』〔传送门〕
「题意」
明天要考试了,Taro 不得不多花一点时间复习。
Taro准备学习 $T$ 个小时,但是他还想玩……幸运的是,他可以到另一个世界去,在那里时间过得更快 —— 在那个世界的 $X$ 小时相当于原来世界的 $1$ 小时。
Taro 决定去那个世界学习,请告诉他他学习完后原来世界经过了多少个小时。
「解析」
这个不用解释吧……小学应用题的感觉。
“总数/每份大小”= $\frac{T}{X}$ 。
「源代码」
1 | /*Lucky_Glass*/ |
『B : Entrance Examination』〔传送门〕
「题意」
Taro 正复习,突然被一道题难住了——“有 $n$ 条线段,给出它们的长度 $l_1,l_2,…,l_n$ ,将它们首尾相连,问它们能否连成一个 $n$ 边形”。
已知如果最大边小于其他边之和,就可以构成 $n$ 边形。
你能帮他完成吗?
「解析」
好心的出题人还把方法说出来了……
边输入边算所有边的总和 $Sum$ 和最大值 $Max$,则按照题目意思就是 $Max<Sum-Max$ 就可以构成 $n$ 边形,否则不行。
「源代码」
1 | /*Lucky_Glass*/ |
『C : Entrance Examination』〔传送门〕
「题意」
重要复习完了,Taro 回到原来的世界,发现还能玩一会~
Taro 开始玩一个游戏:“工厂里有 $n$ 个产品需要加工,你有 $m$ 个机器人,一开始你可以把机器人放在任意的一个产品的位置,机器人到达一个产品后就会完成加工,你可以通过操控机器人移动以完成所有产品的加工。工厂可以抽象为数轴,产品的位置用一个数字 $X_i$ 描述,表示它在数轴上的位置;机器人每一次可以向左或向右移动 $1$ 个单位长度”。
但是机器人移动十分耗电,Taro 想知道要完成所有加工 $m$ 个机器人移动的次数的总和最小为多少。
「解析」
贪心地想,我们一定不能让 $m$ 个机器人的路径有任何重叠,那么我们大概可以想到将原来的数 $X_1$ ~ $X_n$ 分成 $m$ 个段,每一个段由一个机器人完成;而在一个段内,机器人也可以一次性(路径不重叠)地完成该段的加工,即从段的端点移动到另一个端点。因此对于每一个段,机器人移动的距离就是它的左右端点的距离。
现在我们相当于得到了下面这个图:
上图机器人移动的距离之和就是 $(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 | /*Lucky_Glass*/ |
『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 | /*Lucky_Glass*/ |
The End
Thanks for reading!
Email: lucky_glass@foxmail.com ,欢迎提问~