AtCoder Beginner Contest 330 题解

A - Counting Passes

原题链接

题目描述
给定N个数和一个整数L，输出大于等于L的数的个数。

public static void solve() throws IOException{int n = readInt(), m = readInt();int cnt = 0;for (int i = 1; i <= n; i++) {int a = readInt();if (a >= m) cnt++;}printWriter.println(cnt);
}

B - Minimize Abs 1

原题链接

题目描述
给定一个含有n个元素数组arr，和两个整数L和R，对于每个整数 $arr[i]$求出一个数$X(L\le X\le R)$，使得对于任意的 $L\le Y\le R$ 都满足$|X-arr[i]|\le |Y-arr[i]|$。

思路：分类讨论

• 分别讨论$arr[i]$与$L$和$R$的大小即可。

public static void solve() throws IOException {int n = readInt(), l = readInt(), r = readInt();List<Integer> list = new ArrayList<>();for (int i = 1; i <= n; i++) {int a = readInt();if (a <= l) {list.add(l);} else if (a >= l && a <= r) {list.add(a);} else {list.add(r);}}for (int p : list) {printWriter.print(p + " ");}
}

C - Minimize Abs 2

原题链接

题目描述
给你一个整数 $D(1\le D\le 2\times 10^{12})$，求出非负整数 $x$ 和 $y$ 的最小值 $|x^2+y^2-D|$。

思路：二分

• 先确认 $x^2$，再二分枚举出 $y^2$即可，但是要分类讨论一下，即 ① $x^2+y^2\ge D$ ② $x^2+y^2\le D$。

public static void solve() throws IOException{int N = 2000000;long[] s = new long[N];for (int i = 0; i <= N - 1; i++) {s[i] = (long) Math.pow(i, 2);}long d = readLong();long res = Long.MAX_VALUE;for (int i = 0; i < N; i++) {int l = -1, r = N;while (l + 1 < r) {int mid = (l + r) >> 1;if (s[i] + s[mid] >= d) {r = mid;} else {l = mid;}}res = Math.min(res, s[i] + s[r] - d);}for (int i = 0; i < N; i++) {int l = -1, r = N;while (l + 1 < r) {int mid = (l + r) >> 1;if (s[i] + s[mid] <= d) {l = mid;} else {r = mid;}}if (l != -1) {res = Math.min(res, (d - (s[i] + s[l])));}}printWriter.println(res);
}

D - Counting Ls

原题链接

题目描述
给定一个 $N\times N$ 的仅包含o和x的二维字符矩阵，你需要求出能满足以下条件的字符三元组的个数。

• 该三元组上的字符在矩阵中的位置各不相同，但是都是o。
• 该三元组中，其中两个字符在同一行，其中两个字符在同一列。

思路：计数

• 如果二维矩阵的一个位置的字符为o时，该字符贡献为$(row[i]-1)\ast (col[j]-1)$，其中$row[i]$表示该行o的个数，$col[i]$表示该列o的个数。

public static void solve() throws IOException{int n = readInt();String[] strings = new String[n + 1];for (int i = 1; i <= n; i++) {strings[i] = (" " + readString());}int[] row = new int[n + 1], col = new int[n + 1];for (int i = 1; i <= n; i++) {for (int j = 1; j <= n; j++) {if (strings[i].charAt(j) == 'o') {row[i]++; col[j]++;}}}long res = 0;for (int i = 1; i <= n; i++) {for (int j = 1; j <= n; j++) {if (strings[i].charAt(j) == 'o') {res += 1l * (row[i] - 1) * (col[j] - 1);}}}printWriter.println(res);
}

E - Mex and Update

原题链接

题目描述
给定一个长度为$n$的整数序列A，你需要进行Q次操作，第 $i$次操作由二元组 $(p,x)$组成，即先将 $A[p]$修改为x，然后求出序列A的 $mex$并输出。

思路：技巧

• 首先 $mex$一定是 $0\sim n$ 中的数！所以我们只需要统计出 $0\sim n$中每个数字在序列A中出现的次数和哪些数字从没出现过。
• 对于每一次操作，在修改 $A[p]$值的前后，分别对新旧 $A[p]$出现的次数进行修改，① 如果旧 $A[p]$在修改出现次数后变为0，则要重新添加至集合； ② 如果新 $A[p]$修改出现次数前是0，则要将其从集合中删除。

public static void solve() throws IOException {int n = readInt(), q = readInt();int[] a = new int[n], c = new int[n + 1];for (int i = 0; i < n; i++) {a[i] = readInt();if (a[i] <= n) {c[a[i]]++;}}TreeSet<Integer> set = new TreeSet<>();// 统计没有出现过的数字for (int i = 0; i <= n; i++) {if (c[i] == 0) set.add(i);}for (int i = 0; i < q; i++) {int p = readInt() - 1, x = readInt();if (a[p] <= n) {c[a[p]]--;if (c[a[p]] == 0) {// 原先的a[p]出现的次数减一后，出现次数变为0，就添加至 set集合set.add(a[p]);}}a[p] = x;if (a[p] <= n) {if (c[a[p]] == 0) {// 现在的a[p]原先不在set集合中，现在要移出，因为出现次数不为 0了set.remove(a[p]);}c[a[p]]++;}printWriter.println(set.first());}
}