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 ...
Contestant(alt). Rank 4431. Rating -40 (+310 -350). A. Recent Actions 题意 给定一个整数 \(n\)，以及 \(n\) 的排列，给定 \(m\) 个大于 \(n\) 的数，若这个数不在序列里，那么将整个序列右移一位，删去多出的元素，并将第一个空位放入该数。输出原排列的每一个数在第几个数放入的时候被移除。 思路 直接用 \(map\) 或者数组存一下是否在序列里即可，然后统计即可。 时间复杂度：\(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 = LONG_LONG_MAX, mod = 998244353; int a[N]; signed main() { ios::sync_with_stdio(false), cin. ...
Practice. A. Cowardly Rooks 题意 给定 \(n\) 个点的横纵坐标，输出是否可以将任意一个点移动，使每一行每一列都只有最多一个点。 思路 我们可以先将原来的所有点对应的横坐标和纵坐标对应的行和列进行统计，之后若能找出任意一行或者任意一列没有点，那么就可以移动到那里去。 时间复杂度：\(O(n)\) 对应AC代码 #include <bits/stdc++.h> using namespace std; #define int long long #define pii pair<int, int> const int N = 5e3 + 10, inf = 0x3f3f3f3f3f3f, mod = 998244353; signed main() { ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr); int q; cin >> q; while(q --){ i ...
Practice. A. Technical Support 题意 给定一个由 \(Q, A\) 组成的字符串，对于所有 \(Q\)，判断在下一次 \(Q\) 出现或遍历到结束前，是否有至少一个 \(A\) 与之对应。 思路 如题，配对即可。 时间复杂度：\(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 = LONG_LONG_MAX, mod = 998244353; signed main() { ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr); int q; cin >> q; while(q --){ int n; cin >> n; ...
Practice. A. Bestie 题意 给定一个数组 \(a\)，定义操作为将 \(a_i\) 改为 \(gcd(a_i, i)\)，代价为 \(n - i + 1\)，输出最小的操作代价总和，使所有数的最大公约数为 \(1\)。 思路 首先，这里有一个结论：相邻数字的最大公约数一定为 \(1\)。 所以，最多只需两次操作，即可满足题意。 所以，我们只需考虑 \(n\) 和 \(n - 1\) 对应的元素是否需要进行操作，以及对应的代价总和的最小值。 时间复杂度：\(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 = 0x3f3f3f3f; int a[N], b[N]; int gcd(int x, int y) { while (y != 0) { int ...