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 ...
Practice. A. Make A Equal to B 题意 给定两个长度为 \(n\) 的二进制序列 \(a, b\)，定义操作如下： 选择任意 \(i\)，将 \(a_i\) 改为 \(1 - a_i\)； 任意排序 \(a\) 输出操作数的最小值。 思路 很显然，我们直接统计两个序列中 \(0, 1\) 的个数，然后在 将 \(0\) 的个数变为一致需要的操作数 和 将 \(1\) 的个数变为一致需要的操作数 中取最小值即可。此时，答案为最小操作数 \(+ 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 ...
Contestant. Rank 1888. Rating +1. 查重后刚好加了一分（跟白打没区别 A. Li Hua and Maze 题意 给定一个 \(n \times m\) 的矩阵以及两个点 \((x_1, y_1), (x_2, y_2)\)。其中，两点满足 \(|x_1-x_2|+|y_1-y_2|\geq 2\)。在矩阵中插入若干个障碍，使得两点不连通。 输出需要插入的最少障碍数。 思路 很显然，我们把起点或者终点包起来即可。 不要写错就是 \(win\)。 时间复杂度：\(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 = 1e9 + 7; void init()&# ...
Practice. A. Compare T-Shirt Sizes 题意 比较 \(T\) 恤的尺码。 其中，\(XXL > XL, XXS < XS\)。 思路 我们记 \(M = 0\)，其余的按照 \(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; void init(){} void solve() { string a, b; cin >> a >> b; int na = a.size(), nb = b.size(); map<char, int> mp = ...
Contestant. Rank 3437. Unrated. A. Coins 题意 给定 \(n, k\)，输出是否可以找到一对整数 \(x, y\)，满足 \(2 \cdot x + k \cdot y = n\)。 思路 移项可得，\(x = \frac{n - ky}{2}\)。 那么，只要分母是偶数即可。 也就是说，我们考虑 \(n, k\) 的奇偶性：当 \(n\) 为奇数，\(k\) 为偶数的时候就无法满足。 时间复杂度：\(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 = 1e9 + 7; void init(){} void solve() & ...
Contestant(alt). Rank 993. Rating +168. A. Insert Digit 题意 给定一个数 \(a\)，以及一个 \([0, 9]\) 的数 \(b\)，将 \(b\) 插入 \(a\)，输出最大的数。 思路 我们从后往前找出最后一个小于 \(b\) 的数，放在这个数前面就可以让结果最大。 当然，如果没有比它小的数，直接放在最后即可。 时间复杂度：\(O(n)\) #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; char d; string ...