Practice. A. Destroyer 题意 定义每个机器人具有一个参数：它的前面有多少机器人。 机器人可以排成很多行，因而我们可以得到最后的参数序列。 现在，给定打乱后的参数序列，输出是否合法。 思路 很显然，我们只需统计每个参数的出现次数，按照参数升序排序后，如果出现次数不递减，那么就是合法的，否然不合法。 时间复杂度：\(O(n \log n)\) 对应AC代码 #include <bits/stdc++.h> using namespace std; #define int long long #define pii pair<int, int> #define ppii pair<int, pii> #define pci pair<char, int> #define fs first #define sc second #define pb emplace_back #define all(x) x.begin(),x.end() const int N = 2e5 + 10, mod = 9982443 ...
Contestant'. Rank 753. Rating +35. A. Unit Array 题意 给定一个由 \(1, -1\) 组成的数组 \(a\)，定义操作为选择一个元素，并将其改为它的相反数。 现在，输出最小的操作数，使最后的数组满足下面的条件： \(a_1 + a_2 + \ldots + a_n \ge 0\) \(a_1 \cdot a_2 \cdot \ldots \cdot a_n = 1\) 思路 我们简化一下条件： \(1\) 的个数大于等于 \(-1\) 的个数； \(-1\) 的个数为偶数 因而，我们分讨即可。 时间复杂度：\(O(n)\) 对应AC代码 #include <bits/stdc++.h> using namespace std; #define int long long #define pii pair<int, int> #define ppii pair<int, pii> #define pci pair<char, int> #define ...
Contestant(alt). Rank 459. Rating +64. A. Sasha and Array Coloring 题意 给定一个序列，将其用任意数量的颜色染色，染色后，统计每一种颜色中最大值和最小值的差，取和后得到结果。输出最大的结果。 思路 很显然，直接排个序，然后不断将两头的元素取出作为一种颜色做差即可。 时间复杂度：\(O(n \log n)\) 对应AC代码 #include <bits/stdc++.h> using namespace std; #define int long long #define pii pair<int, int> #define ppii pair<int, pii> #define pci pair<char, int> #define fs first #define sc second #define pb emplace_back #define all(x) x.begin(),x.end() const int N = 2e5 + 10, mod = 998 ...
Contestant(alt). Rank 209. Rating +155. A. Cipher Shifer 题意 给定一个字符串，定义操作如下： 选择一个字符； 在该字符后面插入若干和该字符不一样的字符； 将选择的字符插入 如，对于 \(a\)，我们可以操作为 \(abcda\)，\(a, bcd, a\) 对应上面的三个操作。 现在，给出操作后的字符串，还原为原字符串。 思路 既然不会出现一样的字符，那么我们直接暴力枚举，配对头和尾即可。 时间复杂度：\(O(n)\) 对应AC代码 #include <bits/stdc++.h> using namespace std; #define int long long #define pii pair<int, int> #define pci pair<char, int> #define fs first #define sc second #define pb emplace_back #define all(x) x.begin(),x.end() co ...
Practice. A. Game with Board 题意 给定 \(n\) 个 \(1\)，定义操作为选定至少两个相同的数，将其从序列中移除，并插入他们的和。 对于 \(Alice\) 和 \(Bob\) 之间的博弈，规定 \(Alice\) 先手，当某个玩家 无法 执行操作时，该玩家 获胜。 输出最后获胜的玩家。 思路 首先，如果 \(n\) 比较大的时候，\(Alice\) 就可以选择 \(n - 2\) 个 \(1\)，这样 \(Bob\) 只能将剩余的两个 \(1\) 选上，最后序列剩余两个不同的数，从而 \(Alice\) 必胜。 上面的必胜策略需要保证 \(n - 2 > 2\)，也就是 \(n > 4\) 的时候 \(Alice\) 有必胜策略。 我们不难发现，当 \(2 \leq n \leq 4\) 的时候，无论 \(Alice\) 怎么选，最后 \(Bob\) 一定会无法操作，因而 \(Bob\) 必胜。 因而，判断 \(n\) 的大小即可。 时间复杂度：\(O(1)\) 对应AC代码 #includ ...
Contestant'. Rank 785. Rating +41. A. The Good Array 题意 定义满足下面条件的二进制数组 \(a\) 是好的： 枚举 \(i \in [1, n]\)，前 \(i\) 个数至少有 \(\lceil \frac{i}{k} \rceil\) 个为 \(1\)，后 \(i\) 个数至少有 \(\lceil \frac{i}{k} \rceil\) 个为 \(1\)。 给定 \(k\)，输出好数组中 \(1\) 的最少个数。 思路 首先，第一个和最后一个一定是 \(1\)。 那么，对于前 \(n - 1\) 个数，至少有 \(\lceil \frac{n - 1}{k} \rceil\) 个 \(1\)。 因此，答案即为 \(\lceil \frac{n - 1}{k} \rceil + 1\)。 时间复杂度：\(O(1)\) 对应AC代码 #include <bits/stdc++.h> using namespace std; #define int long long #define ...
Contestant'. Rank 1872. Rating -13. 罚时吃饱了 A. Blackboard List 题意 有一块黑板，初始状态下只有两个数字。 定义操作为任选黑板上的两个数字，将两者的差的绝对值写到黑板上。 现在，给定打乱顺序后的黑板上的数字序列，输出其中任意一个初始状态的数字。 思路 首先，因为我们写上去的数字一定是非负数，所以如果序列中有负数，那直接输出。 否则，那么不会出现正数减负数的情况，也就是说，我们写上去的数一定是小于初始状态下的最大数字的。 因此，如果序列都是非负数，最大值就是答案。 时间复杂度：\(O(n)\) 对应AC代码 #include <bits/stdc++.h> using namespace std; #define int long long #define pii pair<int, int> #define pci pair<char, int> #define fs first #define sc second #define pb emplace_back #def ...
Contestant'. Rank 1013. Rating +32. A. Twin Permutations 题意 给定一个排列 \(a\)，构造另一个排列 \(b\)，满足 \(a_i + b_i\) 不递减。 思路 那也就可以是相等。 因为是长度相等的排列，因而一定可以得到 \(n\) 个和为 \(n + 1\) 的组合。 因而，输出 \(n - a_i + 1\) 即可。 时间复杂度：\(O(n)\) 对应AC代码 #include <bits/stdc++.h> using namespace std; #define int long long #define pii pair<int, int> #define pci pair<char, int> #define fs first #define sc second #define pb emplace_back #define all(x) x.begin(),x.end() const int N = 2e5 + 10, mod = 998244353, ...
Contestant'. Rank 1622. Rating +15. A. Grasshopper on a Line 题意 给定一个数轴，终点 \(x\) 以及一个整数 \(k\)，定义一次操作为从当前位置向右移动 \(p\) 格，满足 \(p\mod k \neq 0\)。输出从原点走到 \(x\) 所需的最小的操作数以及方案。 思路 如果 \(x\) 不能被整除，一步即达。 可以被整除的话，\(x - 1\) 肯定不会被整除（互质），因此选择先走一格再走 \(x - 1\) 格。 时间复杂度：\(O(1)\) 对应AC代码 #include <bits/stdc++.h> using namespace std; #define int long long #define pii pair<int, int> #define pci pair<char, int> #define fs first #define sc second #define pb emplace_back #define all(x) x.begi ...