Contestant. Rank 1245. Rating +30. A. Walking Master 题意 给定两个点 \((a, b), (c, d)\)，定义对于点 \((x, y)\) 的操作为下面任选一： \(x + 1, y + 1\)； \(x - 1\) 输出从 \((a, b)\) 走到 \((c, d)\) 需要的最小操作数，无解输出 \(-1\)。 思路 画个图即可。 首先，我们需要向上移动 \(d - b\)，如果 \(d - b < 0\) 就是无解。 此时，横坐标变为 \(a + d - b\)，还需要向左移动 \(a + d - b - c\)，如果 \(a + d - b - c < 0\) 也是无解。 若有解，输出 \(d - b + a + d - b - c\)。 时间复杂度：\(O(1)\) 对应AC代码 #include <bits/stdc++.h> using namespace std; #define int long long #define pii ...
Contestant. Rank 1755. Rating +54. A. Lame King 题意 给定一个坐标系，其中 \(x \in [-100, 100], y \in [-100, 100]\)。给定一个坐标 \([s, t]\)，输出按规定从 \([0, 0]\) 走到 \([s, t]\) 需要的最短时间。 规定若需要连续从相同方向移动，需要间隔一秒。 思路 首先，若我们需要一直向右，那么停留一秒绝对比向垂直方向绕路快，所以，我们不妨以折线的方式移动，直到横坐标或纵坐标等于终点时，向同一方向间隔移动。 时间复杂度：\(O(1)\) 对应AC代码 #include <bits/stdc++.h> using namespace std; #define int long long #define pii pair<int, int> const int N = 2e5 + 10, inf = 0x3f3f3f3f3f3f3f3f, mod = 998244353; void init(){} voi ...
Virtual Participant. Unofficial Rank 382. Solved 4/7. A. Likes 题意 定义 \(a_i\) 为一个人对 \(|a_i|\) 的"喜欢"状态，当 \(a_i > 0\) 时，该人对 \(|a_i|\) 点了"喜欢"，否则将其撤回了"喜欢"。规定未点喜欢就不能撤回"喜欢"。 给定打乱顺序后的若干人的"喜欢"操作，定义 \(b_i\) 为进行第 \(i\) 次操作后得到的"喜欢"数量。将操作按一定方案排序，输出让每次操作得到的数量最大和最小的序列 \(b\)。 思路 首先，若要让数量最少，我们直接在点了"喜欢"后立刻取消即可，那么最后得到的答案会有 \(x\) 个 \(0\ 1\)，\(x\) 即为负数的个数。剩余的数只能让 \(b\) 严格递增 \(1\)。 若要让数量最多，那么我们只需在全部点完后再取消。这时得到一个先递增后递减的序列。 时间复杂度：\(O(n)\) 对应AC代码 #include <bits/stdc++.h> using namespace std; ...
Practice. A. Sum 题意 给定三个数，输出是否可以找出一个数，满足其为另外两个数的和。 思路 如题。 时间复杂度：\(O(1)\) 对应AC代码 #include <bits/stdc++.h> using namespace std; #define int long long #define pii pair<int, int> void solve(){ int a, b, c; cin >> a >> b >> c; cout << (a + b == c || a + c == b || b + c == a ? "YES\n" : "NO\n"); } signed main(){ ios::sync_with_stdio(false), cin.tie(0), cout.tie(0); int t; cin >> t; while(t --) solve(); } 如题 B. Increasin ...
Contestant. Rank 2467. Rating +89. A. Swap Odd and Even 题意 给定一个字符串，将所有 \(2x\) 和 \(2x+1\) 位字符交换位置，输出操作后的字符串。 思路 模拟即可。 时间复杂度：\(O(n)\) 对应AC代码 #include <bits/stdc++.h> using namespace std; #define int long long #define pii pair<int, int> const int N = 1e5 + 10, inf = 0x3f3f3f3f3f3f3f3f, mod = 998244353; void init(){} void solve() { string s; cin >> s; for(int i=0;i<s.size()/2;i++){ char t = s[2 * i]; s[2 * i ] = s[2 * i + ...
Practice. A. Number Replacement 题意 给定一个序列，一个字母可以映射到任意一个数字，但要求一个字母只能映射到一个数字，一个数字可以映射到多个字母。输出是否合法。 思路 简单，我们用哈希即可。用 \(map\) 即可解决本题。 时间复杂度：\(O(n \log n)\) 对应AC代码 #include <bits/stdc++.h> using namespace std; #define int long long #define pii pair<int, int> const int N = 1e6 + 10, inf = 0x3f3f3f3f3f3f3f3f, mod = 998244353; void solve() { int n; cin >> n; vector<int> a(n); for(int i=0;i<n;i++) cin >> a[i]; string s; cin >> s; map<int, ...
Contestant. Rank 1866. Rating -16. A. Prefix and Suffix Array 题意 给定一个字符串的所有前缀和后缀，如 \(a, ab, abc, bca, ca, a\)，不包含其本身，判断原字符串是否是回文字符串。 思路 既然是前后缀，并且回文字符串的判断只需比较 \([0, \frac{n}{2}]\) 和 \([n - \frac{n}{2} - 1, n - 1]\) 区间对应的子串即可，所以我们只需拿出长度为 \(\frac{n}{2}\) 的两个字符串，将一个字符串反转后和另一个比较，相等即回文。 时间复杂度：\(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 = 0x3f3f3f3f3f3f3f3f, mod = 998244353; void so ...
Contestant(alt). Rank 3678. Rating +62(+262 -200). A. Is It a Cat? 题意 给定一个字符串，转化为小写字母后，判断其是否由 \(m, e, o, w\) 组成，四个字母可以出现重复多个，但顺序不能改变，且每一个字母必须出现至少一次。如 \(MeOooOW\)。 思路 如题，我们只需用一个变量存储当前遍历到了哪个字母，若比较到某一个字母的时候，遍历的下标越界，那么输出 \(NO\)。否则，在最后判断一下四个字母是否都出现了至少一次，若满足那么 \(YES\)，否则 \(NO\)。 时间复杂度：\(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 = 0x3f3f3f3f3f3f3f3f, mod = 998244353; int a[N]; sign ...
Contestant. Rank 1837. Rating +17. 开局天崩场 A. Typical Interview Problem 题意 对于一个数字，如果它是 \(3\) 的倍数，那么它映射到字符串 \(F\)，如果它是 \(5\) 的倍数，那么映射到 \(B\)，如果是 \(15\) 的倍数，那么映射到 \(FB\)，否则映射到空字符串。给定一个字符串，输出它是否是一段连续区间内对应数字映射后拼接而成的。 思路 显然，\(15\) 一循环，且给定的字符串长度只有 \(10\)，所以我们只需暴力匹配即可。 有趣的是，\(FB\) 拆开不影响答案。 时间复杂度：\(O(n)\) 对应AC代码 import java.io.*; import java.math.*; import java.util.*; import java.util.concurrent.atomic.*; public class Main{ public static void main(String[] args) throws Excepti ...