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 ...
Practice. A. Planets 题意 对于一个序列，定义操作为下面二选一： 序列的其中一个元素减一，代价为 \(1\)； 将某一个元素改为 \(0\)，代价为 \(c\)。 现在，给定一个序列 \(a\)，根据 \(a_i\) 的值出现的次数构造新的序列 \(c\) (\(c_i\) = \(cnt_i\))，输出将序列 \(c\) 所有元素修改为 \(0\) 所需的最小代价。 思路 判断每个元素的大小与 \(c\) 的关系，答案就是 \(\displaystyle{\sum_{i=1}^n min(cnt_i, c)}\)。 时间复杂度：\(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; void solve(){ in ...
Practice. A. 签到啦~ 题意 给定一个序列以及一个整数 \(d\)，输出总和大于等于 \(d\) 的元素的数量的最小值。 思路 排序+枚举。 时间复杂度：\(O(n \log n)\) 对应AC代码 #include <bits/stdc++.h> using namespace std; #define int long long #define pii pair<int, int> void solve(){ int n, w; cin >> n >> w; vector<int> a(n); for(int i=0;i<n;i++) cin >> a[i]; sort(a.rbegin(), a.rend()); int ans = 0; for(int i=0;i<n;i++){ ans ++; w -= a[i]; if(w <= 0) break; } ...
Practice. A. Job Interview 题意 给定一个由 \(o, -, x\) 构成的字符串，判断字符串是否至少含有一个 \(o\)，且不包含 \(x\)。 思路 如题。 时间复杂度：\(O(1)\) 对应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 = 2e5 + 10, inf = 0x3f3f3f3f3f3f3f3f, mod = 998244353; void init(){} void solve() { int n; cin >> n; string s; cin >> s; bool ans1 = false, ans2 = false; for(char e : s){ ...
Contestent. Rank 1674. Rating -30. 开局爽翻，越打越坐牢（ A. Yura's New Name 题意 给定一个由 "^" 和 "_" 构成的字符串，输出至少需要插入多少个 "^" 或 "_"，使字符串可被划分为若干个个 "^^" 和 "^_^"。 思路 首先，我们可以确定开头和结尾一定是 "^"，那么如果不是，统计数量。 其次，我们两个两个遍历，如果出现了两个 "_"，那么中间一定要插一个 "^"，连续的 "^" 我们不用管。 当然，我们需要特判一下只有一个 "^" 的情况（不难发现上面的做法恰好只漏了这个条件），这个情况只需补上一个 "^" 即可。 时间复杂度：\(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 = 2e5 + 10 ...
Practice. A. Password 题意 给定 \([0, 9]\) 中的几个元素，按照升序排列给出。排除这些元素后，剩余的元素可作为密码的一部分。 其中，密码为 \(4\) 位数，只包含两种数字，且每种数字出现两次。 输出密码可行解的个数。 思路 首先，我们假设只包含数字 \(a, b\)，那么有 \(aabb, abba, bbaa, abab, baba\) 这 \(6\) 种可行解。 其次，我们统计出剩余 \(k\) 种数字，那么选两个的方案数就是 \(C^2_k\)。 因此，答案就是 \(6C^2_k\)。 不过，既然元素个数已经告诉我们了，那么 \(k = 10 - n\)。 因此我们完全不用管元素是什么。 时间复杂度：\(O(n)\) 对应AC代码 #include <bits/stdc++.h> using namespace std; #define int long long #define pii pair<int, int> const int N = 2e5 + 10, inf = 0 ...