Practice. A. New Scheme 题意 给定一个长度为 \(8\) 的序列 \(S\)，判断是否满足下面的条件： 不递减 \(100 \leq S_i \leq 675\) 为 \(25\) 的倍数 思路 如题 时间复杂度：\(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 psi pair<string, 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, inf = 0x3f3f3f3f3f3f3f3f; void solve() ...
Contestant. Rank 1719. Rating -8. 被诈骗咯 A. Forbidden Integer 题意 给定三个整数 \(n, k, x\)，在 \([1, k]\) 中任选除了 \(x\) 之外的其他数字，使所选数字的总和为 \(n\)。 思路 我们进行分讨。 首先，如果 \(k = 1\)，那么一定无解。 其次，如果 \(k = 2\)，那么我们分讨一下 \(x = 1, 2\) 的时候的情况，此时如果 \(n\) 为奇数，而 \(x = 1\)，那么无解。 最后，如果 \(k > 2\)，那么我们分讨一下： \(x = 1\)，那么我们放 \(\frac{n}{2} - 1\) 个 \(2\)，然后再放上剩下的数即可等于 \(n\)； 否则，输出 \(n\) 个 \(1\)。 时间复杂度：\(O(n)\) 对应AC代码 #include <bits/stdc++.h> using namespace std; #define int long long #define pii pair ...
Practice. A. Spell Check 题意 给定一个字符串，判断其是否为字符串 \(\mathtt{Timur}\) 任意排列后的字符串。 思路 我们用 \(map\) 存一下这 \(5\) 个字符的出现次数，如果都出现一次，并且长度为 \(5\)，即可。 时间复杂度：\(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 psi pair<string, 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, inf = 0x3f3f3f3f3f3f3f3f; v ...
Contestant. Rank 2247. Rating -18. 好久没有这么坐牢了 qaq A. Tenzing and Tsondu 题意 给定两个长度相等的序列，作为 \(A, B\) 的每个怪物的血量。每一回合，两个人以最优策略派出两个怪物，若两个怪物的血量为 \(x, y\)，那么回合结束后，两个怪物的血量变为 \(\max(x - y, 0), \max(y - x, 0)\)，血量为 \(0\) 的怪物死亡。 若某一玩家的怪物全部死亡，那么判定为输，输出最后的赢家。 思路 首先，我们可以根据数据乱猜，我们只需比较两个玩家的怪物总血量，血量一致就是平局，否则，血量多的一方胜出。 下面给出官方题解的解释： 注意，\(\max(x - y, 0) = x - \min(x, y), \max(y - x, 0) = y - \min(x, y)\)，因而每一回合两个玩家扣除的血量都是相同的，因而只和总血量有关。 时间复杂度：\(O(n)\) 对应AC代码 #include <bits/stdc++.h> using n ...
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 ...