【AtCoder Beginner Contest Round #181】题解

题目颜色大致代表洛谷题目难度,点击各题标题可以跳转到原题。

A - Heavy Rotation

简化题意:给出正整数 $n$,如果 $n$ 是奇数输出 Black,否则输出 White,$n \le 30$。

题解:这题还要题解?

代码:https://atcoder.jp/contests/abc181/submissions/17780998

B - Trapezoid Sum

简化题意:

  • 有 $n$ 次操作,每次将答案加上一个首项为 $A$,末项为 $B$ 且公差为 1 的等差数列,求最终的答案。
  • $1 \le n \le 10^5$,$1 \le A \le B \le 10^6$。

题解:

  • 每个等差数列项数为 $B-A+1$,根据已知数据套公式求和即可。
  • 注意开 long long。

代码:https://atcoder.jp/contests/abc181/submissions/17784855

C - Collinearity

简化题意:

  • 有 $n$ 个点,第 $i$ 个点坐标为 $(x_i,y_i)$,判断是否存在三点共线。
  • $3 \le n \le 100$,$|x_i|,|y_i| \le 10^3$,任意两点坐标均不相同。

题解:

  • 枚举任意三个点,先求出过前两点的直线的解析式,然后判断第三个点是否在这条直线上即可。
  • 注意当前两个点横坐标相等时不存在斜率,因此要特殊判断(即判断三点横坐标是否均相等即可)。
  • 计算过程可能会有误差,所以判相等时最好要给一段可以接受的判为正确的区间。

代码:https://atcoder.jp/contests/abc181/submissions/17794029

D - Hachi

简化题意:

  • 给一个长度为 $s$ 的数字,判断这个数字在任意交换数位后是否存在一个可以被 $8$ 整除的数。
  • $1 \le s \le 200000$,每位数字均在 $[1,9]$ 之间。

题解:

  • 这题我一开始看错题,以为原数最大就是 $200000$,于是罚时+5min
  • 当然解法也不难,只要先确定这个数中是否存在 $1,2,...,9$ 这些数位。
  • 一个很简单的结论:判断一个数是否是 8 的倍数,只需要判断它对 $10^3$ 取模的值是否是 $8$ 的倍数。
  • 然后,枚举任选存在的 3 个数位,判断这 3 个数位能不能组成 $8$ 的倍数即可。
  • 当然对于一位数和两位数要特判,因为自身无法构成三位数。

代码:https://atcoder.jp/contests/abc181/submissions/17800766

E - Transformable Teacher

简化题意:

  • 有 $n$($n$ 为奇数) 个小朋友和 $m$ 个老师,每个人都有自己的权值。
  • 现在要选出 1 位老师给小朋友们上课,并将小朋友们两两分组。
  • 请选出一个选老师和分组的方案,使得所有组两*值之差的绝对值之和最小。

题解:

  • 首先有如下常识:
    • 选出的老师一定和一个小朋友分成一组。
    • 若将 $k$ ($k$ 是偶数)个人分组,那么将每*值排序,让第 1 个与第 2 个组队,第 3 个与第 4 个组队,以此类推的方案答案一定最小。
    • 对于每个方案中要与老师分配方案的小朋友,分到的老师一定是权值距离它最近的。
  • 知道了这些,就可以开始规划做法:
    • 将每个老师、每个小朋友权值排序;
    • 建立一个特殊的前后缀和,记录每两个*值差的 前/后 缀和;
    • 枚举每个小朋友与老师分组的情况,二分求出最适合该方案的老师;
    • 对于其余分组利用前后缀和方法直接得出答案
    • 特别地,若当前枚举到的小朋友权值从小到大是偶数,代表它前面和它后面的同学都每被分组,因此将这两个人在组成一组并记录答案。
    • 找到答案最小的一种情况,输出即可。
    • 时间复杂度 $O(n \log m)$。
  • 比赛的时候把二分搞成 $n$ 为长度的了,罚时+10min。

代码:https://atcoder.jp/contests/abc181/submissions/17810832

上一篇:如何在Scala Swing应用程序中使用scala.swing.Applet?


下一篇:Java applet没有完全刷新