Contestant'. Rank 472. Rating +58 (+408 -350). 这场没WA!!! 开心捏 A. Love Story 题意 对于字符串 "codeforces"，给定一个与其长度相等的字符串，按位遍历，输出不同位置的个数。 思路 如题，暴力即可。 时间复杂度：\(O(n)\) 对应AC代码 #include <bits/stdc++.h> using namespace std; #define int long long #define pii pair<int, int> #define fs first #define sc second #define pb emplace_back #define all(x) x.begin(), x.end() #define r_all(x) x.rbegin(), x.rend() const int inf = 0x3f3f3f3f3f3f3f3f; void solve(){ string s; cin >> s; s ...
Contestant'. Rank 1818. Rating +61(+561 -500). A. Trust Nobody 题意 定义一群人中有一定数量的人撒谎。对于每个人 \(i\)，会给出他所说的撒谎的人至少有 \(a_i\) 人。输出撒谎的人的数量。 思路 我们直接遍历撒谎的人的数量 \(x\)，然后枚举 \(a_i > x\) 的数量，从而如果数量和 \(x\) 一致，我们就找到了答案。 时间复杂度：\(O(n ^ 2)\) 对应AC代码 #include <bits/stdc++.h> using namespace std; #define int long long #define pii pair<int, int> #define fs first #define sc second #define pb emplace_back #define all(x) x.begin(), x.end() const int N = 2e6, mod = 1e9 + 7; void solve(){ i ...
Practice. A. Two Elevators 题意 给定两个电梯，电梯从一层移动到相邻层需要一秒。当前人位于第一层；第一个电梯位于 \(a\) 层；第二个电梯位于 \(b\) 层，但是该电梯会先前往 \(c\) 层。 输出最先到达第一层的电梯的耗时。 思路 第一个电梯耗时 \(a - 1\)，第二个梯子耗时 \(abs(b - c) + c - 1\)。 取最小值即可。 时间复杂度：\(O(1)\) 对应AC代码 #include <bits/stdc++.h> using namespace std; #define int long long #define pii pair<int, int> #define pdd pair<double, double> #define fs first #define sc second void solve() { int a, b , c; cin >> a >> b >> c; int p = abs(a - 1), q = abs( ...
Contestant. Rank 474. Rating +86. A. Politics 题意 对于 \(n\) 个人，有 \(m\) 个意见，每个人需要对意见做表率（\(+\)表示同意，\(-\) 表示不同意）。 在对一个意见做完表率后，如果同意的人多，那么不同意的人将会离开；如果不同意的人多，那么同意的人将会离开；如果人数一样多，那么所有人都离开。 规定可以在所有人表率前，拿掉一些人。设第一个人为自己，那么输出自己能留到最后的条件下最后剩余的人数的最大值。 思路 首先，如果有其他人的任意一个意见的表率和自己不一样，那么最后自己或者那个不一样的人会离开，所以，所有意见的表率和自己都相同的人的个数加上 \(1\) 就是答案。 时间复杂度：\(O(n)\) 对应AC代码 #include <bits/stdc++.h> using namespace std; #define int long long #define pii pair<int, int> #define fs first #define sc second const ...
Contestant. Rank 1585. Rating +7. A. A-characteristic 题意 给定一个由 \(±1\) 组成的数组 \(a\)，定义特征 \(A\) 为数组 \(a\) 中满足 \(a \leq i < j \leq n\) 且 \(a_i \cdot a_j = 1\) 的个数。 给定个数，构造这个数组。 思路 直接暴力枚举 \(-1\) 的个数，因为可以无视顺序，我们直接在输出 \(-1\) 后剩下的全填上 \(1\) 即可。 因为 \((-1) \cdot (-1) = 1, 1 \cdot 1 = 1\)，所以我们不妨初始化 \(p\) 数组，其中 \(p_i = p_{i - 1} + i - 1\)，那么 \(p_i + p_{n - i} = k\) 时就找到了答案。 时间复杂度：\(O(n)\) 对应AC代码 #include <bits/stdc++.h> using namespace std; #define int long long #define pii pair ...
Contestant(alt). Rank 1774. Rating +20. A. TubeTube Feed 题意 给定两个序列 \(a, b\)，选择 \(a_i\) 的代价为 \(a_i + i\) (从 \(0\) 开始)，价值为 \(b_i\)。输出代价不超过 \(t\) 的条件下的最大价值。 思路 我们找出所有代价不超过 \(t\) 的价值，并遍历这些价值，找出最大值即可。 时间复杂度：\(O(n)\) 对应AC代码 #include <bits/stdc++.h> using namespace std; #define int long long #define pii pair<int, int> #define fs first #define sc second const int N = 110, inf = 0x3f3f3f3f3f3f3f3f; void solve(){ int n, t; cin >> n >> t; vector<int> p; vecto ...
Contestant. Rank 2617. Rating -37. A. Matching 题意 给定一个匹配字符串，包含 \(?\) 和 \([0, 9]\) 内的数字，\(?\) 可用任意数字替换。 输出字符串可以代表的数字的总数，其中数字不可以出现前导 \(0\)。 思路 很显然，难点在最后一句话，但这只和第一个字符是不是 \(?\) 有关。 如果不是 \(?\)，那么显然不会出现前导 \(0\)，最后的答案就是 \(10 ^ x\)，其中 \(x\) 是 \(?\) 的个数。 如果是 \(?\)，那么该位不可以出现 \(0\)，而其余位置是否为 \(0\) 我们无需考虑，所以最后的答案是 \(\frac{9}{10} 10 ^ x\)。 不过当然，如果第一位是 \(0\)，那么一个符合条件的数都没有了。 时间复杂度：\(O(n)\) 对应AC代码 #include <bits/stdc++.h> using namespace std; #define int long long #define pii pair<int ...
Practice. A. Consecutive Sum 题意 给定一个序列 \(a\)，以及整数 \(k\)，定义操作为选择 \(i, j\)，满足 \(i \bmod k = j \bmod k\)，并将 \(a_i\) 和 \(a_j\) 交换。 输出任意次操作后，所有长为 \(k\) 的连续子序列的和的最大值。 思路 我们直接枚举 \(p \in [0, k - 1]\)，并求出所有 \(i \bmod k = p\) 位置上 \(a_i\) 的最大值，并输出总和即可。 时间复杂度：\(O(n)\) 对应AC代码 #include <bits/stdc++.h> using namespace std; #define int long long #define pii pair<int, int> #define fs first #define sc second const int N = 110, inf = 0x3f3f3f3f3f3f3f3f; void solve(){ int n, k; ...
Practice. A. Select Three Sticks 题意 给定 \(n\) 根火柴，定义操作为选定一根火柴，并将其长度加 \(1\) 或减 \(1\)。输出最小的操作数，使得所有火柴中有至少三根火柴的长度相等。 思路 很显然，我们只需将火柴按长短升序排序，然后枚举所有相邻的三元组，找出 将 左右两个元素 加减 到 与中间的元素相同 所需的操作数 的最小值 即可。 时间复杂度：\(O(n \log n)\) 对应AC代码 #include <bits/stdc++.h> using namespace std; #define int long long #define pii pair<int, int> #define fs first #define sc second const int N = 110, inf = 0x3f3f3f3f3f3f3f3f; void solve(){ int n; cin >> n; vector<int> a(n); for(in ...