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) ...
Rank 906/3920. AC 5/12. A. Tokitsukaze and a+b=n (easy) 题意 在两个闭区间 \([L1, R1]\) 和 \([L2, R2]\) 之间取两个数 \(a\)，\(b\)，满足 \(a+b=n\)。\(a \neq b\) 时交换两者可算作两种选法。输出选法总数。 思路 暴力枚举 \(a\)，\(b\)。快速签到。 时间复杂度：\(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(); int l1 = scanner ...
Rank 449/4376. AC 7/13. A. World Final? World Cup! (I) 题意 \(A\)队与\(B\)队轮流点球，\(A\)先手，判断\(10\)场内是否有某队必胜，输出该场次，或者输出\(-1\) 思路 对于第 \(i\) 场 \((i \in [0,9])\) ，剩余 \(left=10-i-1\) 场未打。 分开判断\(A\)队和\(B\)队， 对于\(A\)队，还有 \(left/2+(1-i\%2)\) 场； 对于\(B\)队，还有 \(left/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( ...
Practice. Solved 3 of 6. A. Hossam and Combinatorics 题意 定义数对 \((a_i,a_j)\) 满足 \(i \neq j\)。给定数组 \(a\)，输出满足 \(|a_i-a_j|\) 最大的数对数量。 思路 既然要找出 \(\max(|a_i-a_j|)\)，那么我们就需要先把它求出来。更具体地说，我们在读入数组 \(a\) 的时候可以顺便记录下来最大值 \(maxx\) 和最小值 \(minn\)，方便后续操作。 考虑到我们不可能再对数组进行多次遍历，我们可以在读入数组 \(a\) 的时候也记录一下每个数字出现的次数 \(cnt\)，为节省空间我们可以用 \(map\) 存储。 令 \(maxx-minn=dist\)，那么对于一个数对 \((a_i,a_j)\)，我们只需满足 \(|a_i-a_j|=dist\)，去掉绝对值，我们便可以得到两个式子：\(a_j=a_i-dist\)，\(a_j=a_i+dist\)。不妨记此时的 \(a_j\) 为左值和右值，那我们就只需遍历所有 \(a_ ...
Contestant. Rank 9289. Rating -54 (+446 -500). A. Koxia and Whiteboards 题意 给定序列 \(a\) , \(b\) , 执行 \(m\) 次操作，对于第 \(j\) 次操作，将序列 \(a\) 中任意数值修改为 \(b_j\) ，输出操作之后序列 \(a\) 的总和的最大值。 思路1 注意到题目所给 \(n\) 和 \(m\) 很小，因而我们可以遍历 \(b_j\)，在每次替换前 \(sort\) 一遍 \(a\) 数组，然后替换 \(a_0\) 即可。 一句话，暴力+模拟。 时间复杂度：\(O(mn \log n)\) 当然也可以用优先队列优化时间复杂度，不过优化后差不多，所以不放代码了。 对应AC代码 import java.util.*; public class Main{ public static void main(String[] args){ Scanner scanner = new Scanner(System.i ...