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 ...
Contestant. Rank 1877. Rating +196. A. camel Case 题意 给定一个由一个大写字母和若干个小写字母组成的字符串，输出大写字母的位置。 思路 如题，很签到。 时间复杂度：\(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 = 0x3f3f3f3f; signed main() { ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr); string s; cin >> s; for(int i=0;i<s.size();i++){ if(s[0] >= 'A' && s[i] <= 'Z'){ ...
Contestant. Rank 1936. Rating +9. A. Serval and Mocha's Array 题意 给定一个数组 \(a\)，将其重新排序，满足对于所有前缀，如前 \(i\) 个数，满足它们的 \(gcd \leq i\)。 思路 首先，最优的方法当然是互质，只要把互质的两个数放到第一个，那么后面的 \(gcd\) 全都是 \(1\) 了。 其次，前两个数可以有公约数 \(2\)，这是毋庸置疑的。但是，若我们继续下去，前 \(3\) 个数可以有公约数 \(3\)，...，前 \(6\) 个数可以有公约数 \(6\)。停，不对劲：既然有公约数 \(2,3\)，那么一定能被 \(6\) 整除，那么前两个数的 \(gcd\) 一定至少是 \(6\) 了，产生了矛盾。 所以，我们只需找出一对数，满足 \(gcd \leq 2\) 即可。 时间复杂度：\(O(n ^ 2)\) 对应AC代码 #include <bits/stdc++.h> using namespace std; #define int long l ...
Practice. A. Factorise N+M 题意 给定一个质数，输出一个质数，使两者相加不是质数。 思路 除 \(2\) 之外，偶数都不是质数，所以直接加上 \(3\) 即可。 若为 \(2\)，那么加上 \(2\) 即可。 时间复杂度：\(O(1)\) 对应AC代码 #include <bits/stdc++.h> using namespace std; #define int long long const int N = 2e5 + 10; signed main() { ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr); int t; cin >> t; while(t --){ int n; cin >> n; cout << (n % 2 == 0 ? 2 : 3) << '\n'; } } ...
Practice. 什么陈年老题目（（ A. Interview 题意 给定两个长度相等的序列，任选一段区间，输出区间内各序列值进行按位或之后的和。 思路 考虑到数据范围，直接暴力即可。 时间复杂度：\(O(n ^ 2)\) 对应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]; signed main() { ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr); int n; cin >> n; for(int i=0;i<n;i++) cin >> a[i]; for(int i=0;i<n;i++) cin >> b[i]; ...
Practice. A. Two Groups 题意 给定一个数组 \(a\)，可以为负数，从数组 \(a\) 中取出某些数作为序列 \(s_1\)，剩余作为序列 \(s_2\)，输出 \(|sum(s_1)| - |sum(s2)|\) 的最大值。序列可以为空。 思路 考虑到 \(|sum(s_1)| - |sum(s2)| \leq |sum(s_1) + sum(s2)| = |sum(a_i)|\)，我们可以发现原数组的总和的绝对值即为最大值。 时间复杂度：\(O(n)\) 对应AC代码 #include <bits/stdc++.h> using namespace std; #define int long long const int N = 2e5+10; signed main(){ ios::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL); int t; cin >> t; while(t --){ ...