Codeforces Round 905 (Div. 3) 题解 A-E

本文主要是介绍Codeforces Round 905 (Div. 3) 题解 A-E，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

A - Morning

原题链接

题目描述
给你一个模板字符串1234567890，在每一步操作中，1. 你可以让光标移动至相邻的数字(但是 $1$ 相邻的数字只有 $2$ ， $0$ 相邻的数字只有 $9$ ) 2. 或者你可以打印当前光标指向数字。起初光标指向 $1$ 的位置，现给定一个长度为 $4$ 的密码串，要求你进行最少的操作打印这个密码串。

思路：模拟

用一个Map存下对应字符的位置，然后枚举密码串，模拟移动的步数即可。

public static void solve() throws IOException{String s = readString();Map<Character, Integer> map = new HashMap<>();int p = 1;for (char ch = '1'; ch <= '9'; ch++) {map.put(ch, p++);}map.put('0', p);int cnt = 0;char cur = '1';// 当前光标指向的字符for (int i = 0; i < s.length(); i++) {if (s.charAt(i) != cur) {cnt += Math.abs(map.get(cur) - map.get(s.charAt(i)));// 移动cur = s.charAt(i);}cnt++;// 打印}printWriter.println(cnt);
}

B - Chemistry

原题链接

题目描述
给定一个长度为 $n$ 的字符串 $s$ 和一个整数 $k$ ，问是否能从 $s$ 中删除 $k$ 个字符使得 $s$ 为回文字符串，删除 $k$ 个字符后的 $s$ 可以任意排列。

思路：分类讨论

统计 $s$ 中所有字符出现的次数，如果全部都为偶数次或者只有一个字符出现的次数为奇数次，那么一定可以构成回文串，否则需要将(odd - 1)个出现的次数为奇数次的字符删除，例如ecadc，只需要将ead中任意两个字符删去即可构成回文串。

public static void solve() throws IOException{int n = readInt(), k = readInt();String s = readString();Map<Character, Integer> map = new HashMap();for (int i = 0; i < s.length(); i++) {char ch = s.charAt(i);map.put(ch, map.getOrDefault(ch, 0) + 1);}int odd = 0;for (int val : map.values()) {if ((val & 1) == 1) {odd++;}}if (odd == 1) {printWriter.println("YES");} else {k -= (odd - 1);if (k >= 0 && k < (n - (odd - 1))) {printWriter.println("YES");} else {printWriter.println("NO");}}
}

C - Raspberries

原题链接

题目描述
给定一个长度为 $n$ 的数组a和一个整数 $k$ ，在一次操作中，你可以选择任意位置让 $a_i$ = $a_i+1$ ，求使得数组 $a$ 所有数的乘积能整出 $k$ 的最少操作数。

思路：分类讨论

对 $k = 4$ 和 $\neq 4$ 的情况进行讨论
– 1. 如果 $k = 4$ ，那么判断有多少个数是 $2$ 的倍数，① 如果有至少 $2$ 个数是 $2$ 的倍数，那么最后乘积一定是 $4$ 的倍数，操作数为 $0$ ② 只有 $1$ 个数是 $2$ 的倍数，那么对其他任意数 $+ 1$ 即可，操作数为 $1$ ③ 没有数是 $2$ 的倍数，那么就看有没有 $3$ 或 $7$ ，如果有，只需要在 $3$ 或 $7$ 上面 $+ 1$ ,即构成 $4$ 的倍数，操作数为 $1$ ，如果没有，操作只数能为 $2$ 。
– 2. 如果 $\neq 4$ ，那么只需要构造出一个 $k$ 的倍数即可。

public static void solve() throws IOException{int n = readInt(), k = readInt();int[] a = utils.nextIntArray(n);int min = Integer.MAX_VALUE;if (k == 4) {int cnt = 0;int s = 0;// 3或 7出现的次数for (int i = 1; i <= n; i++) {if (a[i] == 3 || a[i] == 7) s++;while (a[i] % 2 == 0 && a[i] != 0) {cnt++;a[i] /= 2;}}if (cnt >= 2) {printWriter.println(0);} else {if (cnt == 1) {printWriter.println(1);} else {if (s >= 1) {// 出现了3或7printWriter.println(1);} else {printWriter.println(2);}}}} else {for (int i = 1; i <= n; i++) {int t = (a[i] + k - 1) / k * k;min = Math.min(min, Math.abs(t - a[i]));}printWriter.println(min);}
}

D - In Love

原题链接

题目描述
你有一个数轴，起初上面没有画任何线段，现在你要进行q次操作：

+ l r，在数轴上画一条[l,r]的线段
- l r，擦去一条数轴上[l,r]的线段

每次操作后，你需要判断数轴上是否存在两条不相交的线段。

思路：贪心

维护所有线段中最大的左端点 $L$ 和最小的右端点 $R$ 即可，如果存在最大的左端点大于最小的右端点，那么一定存在两条不相交的线段。

public static void solve() throws IOException{int n = readInt();TreeMap<Pair, Integer> map1 = new TreeMap<>(new Comparator<Pair>() {@Overridepublic int compare(Pair o1, Pair o2) {return o2.first - o1.first;// 维护最大的 L}});TreeMap<Pair, Integer> map2 = new TreeMap<>(new Comparator<Pair>() {@Overridepublic int compare(Pair o1, Pair o2) {return o1.first - o2.first;// 维护最小的 R}});for (int i = 1; i <= n; i++) {String s = readString();int a = Integer.parseInt(readString()), b = Integer.parseInt(readString());Pair pair1 = new Pair(a, b), pair2 = new Pair(b, a);if (s.equals("+")) {map1.put(pair1, map1.getOrDefault(pair1, 0) + 1);map2.put(pair2, map2.getOrDefault(pair2, 0) + 1);} else {map1.put(pair1, map1.getOrDefault(pair1, 0) - 1);map2.put(pair2, map2.getOrDefault(pair2, 0) - 1);if (map1.get(pair1) == 0) map1.remove(pair1);if (map2.get(pair2) == 0) map2.remove(pair2);}// 最大的 l大于最小的 rif (map1.size() > 0 && map2.size() > 0 && map1.firstEntry().getKey().first > map2.firstEntry().getKey().first) {printWriter.println("YES");} else {printWriter.println("NO");}}
}

E - Look Back

原题链接

题目描述
给你一个长度为 $n$ 的数组 $a$ ，你可以进行以下操作：设置 $a_i$ = $a_i*2$ ，你需要求出最少的操作数使得 $a$ 数组是一个不递减数组。

思路：模拟+技巧

暴力模拟时，很容易发现 $a_i$ 将会越来越大，从而导致超时。那么我们可以通过一个技巧，即当 $a_i$ 达到一定值时，限制他的大小在一个数的附近波动即可，从而降低时间复杂度。

public static void solve() throws IOException{int n = readInt();long[] a = utils.nextLongArray(n);long res = 0, pre = a[1], pow = 0;for (int i = 2; i <= n; i++) {long cnt = 0;while (a[i] < pre) {a[i] *= 2;cnt++;}res += cnt + pow;pre = a[i];while (pre > 1E10) {// 让a[i]在 1e10附近波动pre /= 2;pow++;}}printWriter.println(res);
}