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 --){ ...
Practice. A. Indirect Sort 题意 给定一个排列 \(a\)，定义操作如下： 选择三个下标 \(i, j, k\)，满足 \(1 \leq i < j < k \leq n\)； 若 \(a_i > a_k\)，将 \(a_i\) 替换为 \(a_i + a_j\)，否则将 \(a_j\) 和 \(a_k\) 交换。 输出是否可以将排列变为一个不递减序列。 思路 显然，当第一位不为 \(1\) 的时候，第一位无法减小，而由于 \(1\) 在序列的后面，所以一定存在一个递减的组合，而操作无法将选定的递减组合变为递增，所以无解。 相反地，当第一位为 \(1\) 时，我们只需选 \(i = 1\)，那么每次均可实现交换，从而交换成为一个不递减序列。 时间复杂度：\(O(1)\) 对应AC代码 #include<bits/stdc++.h> using namespace std; #define int long long const int N = 1e5 + 10, inf = 0 ...
Practice. 代码略去了快读模板 A. Two Permutations 题意 给定三个整数 \(n, a, b\)，构建两个长为 \(n\) 的排列，满足前 \(a\) 个数和后 \(b\) 个数一致。输出是否能构建出两个不同的排列。 特别地，当 \(n = a = b\) 时，输出 \(YES\)。 思路 如题。 时间复杂度：\(O(1)\) 对应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 Exception{ Console console = new Console(); int t = console.nextInt(); while(t -- > 0){ ...
Contestant. Rank 720. Unrated. 划水，打卡，三题，结束（（ A. Walking Boy 题意 给定一个升序排序的数组 \(a\)，\(a_i \in [0, 1440]\)，在数组第一位插入 \(0\)，最后一位插入 \(1440\)，输出是否有两个相邻数的差值大于等于 \(120\)。 思路 如题。 时间复杂度：\(O(n)\) 对应AC代码 #include<bits/stdc++.h> using namespace std; #define int long long const int N = 2e5 + 10, inf = 0x3f3f3f3f, mod = 998244353; int a[N]; signed main() { ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); int t, n; cin >> t; while(t --){ cin >> n; ...
Contestant. Rank 3650. Rating +66. A. Contest Result 题意 给定数组 \(a, b\)，输出 \(a_{b_i}\) 的总和。 思路 如题。 时间复杂度：\(O(n)\) 对应AC代码 #include<bits/stdc++.h> using namespace std; #define int long long const int N = 1e5 + 10, inf = 0x3f3f3f3f, mod = 998244353; int a[N]; signed main() { ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); int n, m; cin >> n >> m; for(int i = 1;i<=n;i++) cin >> a[i]; int ans = 0; for(int i=0;i<m;i++){ int p; ...