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 ...
Contestant. Rank 900. Rating +46. A. Ian Visits Mary 题意 给定一个点 \((a, b)\)，最多另找一个点作为支点，满足原点到该点的连线不经过其他点，或者原点到支点、支点到该点的连线都不经过其他点。 输出该点，或者支点和该点。 思路 （怎么解释得这么抽象） \((0, 0) \rightarrow (a - 1, 1) \rightarrow (a, b)\) 时间复杂度：\(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; void init(){} void solve() { int a, b; ...
Practice. A. Immobile Knight 题意 规定一个棋子只能沿着 \(1 \times 2\) 矩形的对角线行走。 给定一个棋盘的尺寸，输出让棋子无法行走的点的位置。如果点不存在，输出任意点。 思路 能走的尺寸数量有限，我们直接分类讨论，这边定义较短边为 \(n\)，较长边为 \(m\)。 \(n = 1\)，那么随便哪个点都是答案； \(n = 2或3, m = 3\)，那么中心点就是答案 其余情况，随便输出即可。 注意，输出的点一定要在棋盘内，否则是无效答案。 时间复杂度：\(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; void init(){& ...
Contestant. Rank 1053. Rating +125. A. Double Click 题意 定义两个点击时刻 \(s_1, s_2\) 的差小于等于某个值 \(D\) 时视为在靠后的时间点 \(s_2\) 时触发双击。 给定一个点击时刻的序列，判断哪个时刻触发了第一次双击。无双击输出 \(-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 int N = 2e5 + 10, inf = 0x3f3f3f3f3f3f3f3f, mod = 1e9 + 7; void init(){} void solve() { int n, d; cin >> n >> d; i ...
Practice. A. Working Week 题意 给定 \(n\) 个格子，规定第 \(1\) 个格子不能标记，第 \(n\) 个格子一定被标记。按照要求标记三个点后，格子被划分成三段，记长度为 \(l_1, l_2, l_3\)。 输出 \(\min(|l_1 - l_2|, |l_2 - l_3|, |l_3 - l_1|)\) 的最大值。 思路 显然，我们可以在第二个点做上标记，这样就可以让差值尽可能大。 那么，我们来考虑剩下那个点。因为对称性，我们不妨令 \(l_2 \leq l_3\)。 很明显，\(\min(|l_1 - l_2|, |l_2 - l_3|, |l_3 - l_1|) = \min(l_2 - 1, n - 4 - 2l_2)\) 如果前者更小，那就需要满足 \(l_2 \leq \frac{n}{3} - 1\)，那么 \(l_2 - 1\) 的最大值就是 \(\frac{n}{3} - 2\)。 如果后者更小，那就需要满足 \(l_2 \geq \frac{n}{3} - 1\)，那么 \(n - 4 ...