Contestant. Rank 4776. Rating -20 (+30 -50). A. Parallel Projection 题意 给定一个长方体，在长方体的顶部和底部各取一个点，一只蚂蚁只能在平面上向平行于边的方向移动，求出蚂蚁从一个点移动到另一个点的最短路径。 思路 从四个方向分别模拟一下求最小值即可。 时间复杂度：\(O(1)\) 对应AC代码 import java.util.*; public class Main { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int t = scanner.nextInt(); while(t -- > 0){ int w = scanner.nextInt(), d = scanner.nextInt(), h = scanner.nextInt(); ...
Practice. A. Everybody Likes Good Arrays! 题意 给定一个数组 \(a\)，定义一次操作为将奇偶性相同的相邻元素相乘并合并为一个元素，输出让数组 \(a\) 满足所有相邻数奇偶性不同的最小操作数量。 思路 显然，奇偶性相同的两个数相乘后奇偶性是不变的，那么我们只需统计有多少组相邻元素的奇偶性相同即可。 时间复杂度：\(O(n)\) 对应AC代码 import java.math.BigInteger; import java.util.*; public class Main{ public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int t = scanner.nextInt(); while(t -- > 0){ int n = scanner.nextInt(); i ...
Contestant. Unrated, with problem C removed. A. Hayato and School 题意 给定一个数组 \(a\)，输出一对下标，满足下标对应的元素的和为奇数。保证数组 \(a\) 至少有 \(3\) 个元素。 思路 分类讨论： 奇数元素数量大于 \(3\)，直接输出前三个奇数。 偶数只有 \(1\) 个，或者没有奇数，无解。 输出一对”奇，偶，偶“即可。 时间复杂度：\(O(n)\) 对应AC代码 #include <bits/stdc++.h> using namespace std; const int N = 310; pair<int, int> a[N], b[N]; #define ll long long int main() { ios::sync_with_stdio(false), cin.tie(0), cout.tie(0); int t; cin >> t; while(t --){ ...
Contestant. Rank 6984. Rating -84 (+16 -100). A1. Gardener and the Capybaras (easy version) 题意 给定一个由 \(a\) 和 \(b\) 构成的字符串，将其分成三部分 \(a,b,c\)，输出一种分法，让 \(b\) 成为三者中的最值。 对于两个字符串 \(x\)，\(y\)，若 \(x < y\)，当且仅当下面任意一个条件成立： \(x\) 是 \(y\) 的前缀，但\(x \neq y\)； \(x_1='a',y_1='b'\)。 思路 我们分成两个情况考虑： 遍历 \([2,n-1]\)，若出现 \(a\)，那么让 \('a'\) 单独成为中间的字符，这样中间的字符一定是最小的，直接输出即可。 如果不存在，那么我们让 \([2,n-1]\) 的所有字符作为中间的字符串，因为第一位为 \(b\)，且足够长，一定可以保证其为最大。 时间复杂度：\(O(n)\) 对应AC代码 im ...
Contestant. Rank 3946. Rating +15 (+165 -150). A. Make it Beautiful 题意 给定一个数组 \(a\)，将其重新排列，使其满足对于任意 \(a_i\)，均满足前缀和 \(sum_{i-1} \neq a_i\)。 思路 将数组降序排列即可。 需要特判一种情况，当降序排列后，第一个数和第二个数重复，那么需要向后枚举，找到第一个不一样的数，将其和第一个数交换即可。若没有这个数，输出 \(NO\)。 时间复杂度：最坏\(O(n)\) 对应AC代码 import java.util.*; public class Main { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int t = scanner.nextInt(); nxt:while(t -- > 0){ in ...
Contestant. Rank 2570. Rating +70. A. GamingForces 题意 给定一个数组 \(a\)，定义操作可任选其一： 将其中两个元素减 \(1\) 将某个元素减为 \(0\) 输出最少的操作数，使 \(a\) 的所有元素都减为 \(0\)。 思路 将所有为 \(1\) 的元素配对，扣去偶数个 \(1\) 后，剩下的元素全都执行操作 \(2\) 即可。 时间复杂度：最坏\(O(n)\) 对应AC代码 import java.util.*; public class Main{ public static void main(String[] args){ Scanner scanner = new Scanner(System.in); int t = scanner.nextInt(); while(t -- > 0){ int n = scanner.nextInt(); ...
Contestant. Rank 7746. Rating -64 (+186 -250). A. Greatest Convex 题意 给定 \(k\)，输出满足条件的 \(x\)，使 \(x!+(x-1)!\) 为 \(k\) 的倍数。 思路 \(x!+(x-1)!=(x-1)!(x+1)\)，显然，令 \(x+1=k\) 即可，答案即为 \(k-1\)。 时间复杂度：\(O(1)\) 对应AC代码 import java.util.*; public class Main { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int t = scanner.nextInt(); while(t -- > 0){ System.out.println(scanner.nextInt() - 1); } ...
Contestant. Rank 3574. Rating +50 (+400 -350). A. Hall of Fame 题意 给定一个只有 \(L\) 和 \(R\) 的长度为 \(n\) 的字符串，对于第 \(i\) 个字符，\(L\) 表示将 \([1,i-1]\) 照亮，\(R\) 表示将 \([i+1,n]\) 照亮。对于该字符串，允许选择一个 \(i\)，将 \(i\) 和 \(i+1\) 对应的字符交换，该操作最多可执行一次。判断是否可以将所有点照亮。若无需交换，输出 \(0\)；若交换后才满足条件，输出 \(i\)；若无法满足条件，输出 \(-1\)。 思路 很显然，只要出现 \(R,...,L\) 的排列，就一定可以满足条件。 那么，我们首先可以寻找第一个 \(R\) 之后有没有 \(L\)，只要找到了 \(L\) 就直接输出 \(0\) 即可。 否则，我们就需要寻找 \(LR\)，并将其交换，并输出 \(L\) 对应的下标。 否则，输出 \(-1\) 即可。 时间复杂度：\(O(n)\) 对应AC代码 import ja ...
Rank 196/3562. AC 7/11. 这标题显然是参考了arcaea的final verdict包的剧情，对吧 A. 不断减损的时间 题意 给定一个数组，数值可以为负数。对于无限次的操作，你可以任选一个偶数并将其除以 \(2\)，输出最后总和的最大值。 思路 将所有正偶数暴力除到奇数为止，并求和即可。 时间复杂度：\(O(n)\) 对应AC代码 import java.util.*; public class Main{ public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int n = scanner.nextInt(); long ans = 0; for(int i=0;i<n;i++){ int a = scanner.nextInt(); if(a <= 0) ...