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; ...
Contestant. Rank 3721. Rating +41. A. Many A+B Problems 题意 给定 \(a, b\)，输出 \(a + b\)。 思路 如题 时间复杂度：\(O(1)\) 对应AC代码 #include <bits/stdc++.h> using namespace std; #define int long long signed main() { ios::sync_with_stdio(0); int t; cin >> t; while(t --){ int a, b; cin >> a >> b; cout << a + b << '\n'; } return 0; } 怎么会是呢 B. Qualification Contest 题意 给定 \(n\) 个由小写字母组成的字符串，输出字典序升序排序的前 \(k\) 个字符 ...
Contestant. Rank 2199. Rating +10. A. Two Towers 题意 给定由两种不同颜色的元素叠成的塔，定义操作为将一个塔上的顶部元素移动到另一个塔，在若干次操作后，输出是否可以让两个塔的元素颜色相间。 思路 显然，这个问题可以抽象为：给定一个元素序列，找出一个点，将序列分成两半，使分割后的序列颜色相间。 那么，我们需要满足两个条件： 序列内没有连续 \(3\) 个及以上相同元素相邻； 序列内连续 \(2\) 个及以上相同元素相邻的组的个数最多只有 \(1\)。 时间复杂度：\(O(n)\) 对应AC代码 #include<bits/stdc++.h> using namespace std; #define int long long const int N = 1010, inf = 0x3f3f3f3f; signed main() { ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); int t; cin ...
Practice. A. The Ultimate Square 题意 给定 \(n\) 个方块，第 \(i\) 个方块的宽度为 \(1\)，长度为 \(\lceil \frac{i}{2} \rceil\)。选取一些方块横向拼接成一个正方形，输出正方形的最大边长。 思路 显然，当 \(n\) 为奇数的时候，我们一定能将所有方块都用上，拼成一个长为 \(\frac{n + 1}{2}\) 的正方形；当 \(n\) 为偶数的时候，一个大方块将会多出来，而剩余的方块按照奇数的情况处理即可。 时间复杂度：\(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); int t, n; cin >> t; while(t --){ cin >> ...
Practice. A. Yes-Yes? 题意 给定一个字符串，判断其是否是 \(YESYESYES...\) 的连续子串。 思路 判断多出的前缀是否满足条件，若满足条件，以 \(3\) 个字符为一组匹配 \(YES\)。剩余的后缀特判即可。 时间复杂度：\(O(n)\) 对应AC代码 #include<bits/stdc++.h> using namespace std; #define int long long signed main() { ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); int t; cin >> t; while(t --){ int n; string s; cin >> s; n = (int) s.size(); int i = 0; if(s[i] != 'Y'){ if(s[i] ...
Practice A. Medium Number 题意 给定三个数，输出中位数。 思路 排序，输出中间的。 时间复杂度：\(O(1)\) (确信) 对应AC代码 #include<bits/stdc++.h> using namespace std; #define int long long signed main() { ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); int t; cin >> t; while(t --){ int a[3]; for(int i=0;i<3;i++) cin >> a[i]; sort(a, a + 3); cout << a[1] << '\n'; } return 0; } 过于打卡 B. Atilla's Favorite Problem 题意 给定 ...