Contestant~. Rank 1733. Rating +45(+295 -250). 乱猜结论场，猜不出来坐牢场 A. Subtraction Game 题意 给定两个人之间的博弈：每个人可以选择拿走 \(a\) 或 \(b\) 个石头。 输出后手有必胜策略的石头的总数。 思路 很经典的博弈。 如果先手拿走 \(x\) 个石头后，后手都能拿走 \(n - x\) 个石头，那么后手必胜。 那么，\(n = a + b\)。 时间复杂度：\(O(1)\) 对应AC代码 #include <bits/stdc++.h> using namespace std; #define int long long #define pii pair<int, int> #define pipi pair<pii, pii> #define ppii pair<int, pii> #define pci pair<char, int> #define fs first #define sc second #define pb ...
Contestant~. Rank 538. Rating +59 (+409 -350). A. Rudolph and Cut the Rope 题意 给定 \(n\) 个钉子，第 \(i\) 个钉子钉在离地面 \(a_i\) 的位置，并连有 \(b_i\) 长的绳子。所有钉子的另外一端连着同一个糖果。 输出需要剪断多少根绳子，让糖果掉到地上。 思路 画个图即可，我们不难发现最后的结果就是 \(a_i > b_i\) 的钉子个数。 时间复杂度：\(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 fs first #define sc second #define pb emplace_back #define all(x) x ...
Contestant~. Rank 596. Rating +153 (+653 - 500). A. The Man who became a God 题意 给定数组 \(a\)，定义 \(f(l,r) = |a_l - a_{l+1}| + |a_{l + 1} - a_{l + 2}| + \ldots + |a_{r-1} - a_r|\)。 将数组 \(a\) 划分为 \(k\) 段，输出各段 \(f\) 值之和的最小值。 思路 不难发现，划分等价于删除一个 \(|a_i - a_{i + 1}|\)。 那么，我们将所有 \(|a_i - a_{i + 1}|\) 排个序，删去前 \(k - 1\) 个大的，然后求和即可。 时间复杂度：\(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, p ...
Practice. A. Echo 题意 给定一个字符串，遍历所有字符，并按顺序输出两个。 如 \(abc \rightarrow aabbcc\)。 思路 如题。 时间复杂度：\(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 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() { int n; string s; cin >> ...
Contestant. Rank 1438. Rating +51. A. Weekly Records 题意 给定 \(14\) 个数字，输出前 \(7\) 个和后 \(7\) 个数的总和。 思路 如题。 时间复杂度：\(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 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() { int n; ...
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 ...