Contestant~. Rank 1201. Rating +25. A. Increasing and Decreasing 题意 给定三个整数 \(x, y, n\)，构造一个长为 \(n\) 的序列 \(a\)，满足： \(a_1 = x, a_n = y\)； \(a_1 < a_2 < \ldots < a_n\)； 记 \(b_i = a_{i + 1} - a_i\)，\(b_1 > b_2 > \ldots > b_{n - 1}\) 如果无法构造，输出 \(-1\)。 思路 既然要尽可能构造出来，那么我们就尽可能缩小相邻 \(b_i\) 的差值，也就是说，\(b_{n - 1} = 1, b_{n - 2} = 2, \ldots\)。 我们令 \(a_n = y\)，然后递推到 \(a_1\)，最后比较一下 \(a_1\) 和 \(x\) 的大小。 显然，如果 \(a_1 > x\)，那么无解，否则就可以满足 \(a_2 - x \geq a_2 - a_1 = b_ ...
Contestant_. Rank 245. Rating +76 (+326 -250). A. Gift Carpet 题意 给定一个 \(n \times m\) 的字符矩阵，判断是否能找出四列，满足这四列按顺序分别包含 "v,i,k,a"。 思路 既然要按顺序，那么我们直接从左向右遍历，从 上一次找到的列 之后 开始 找下一个字符第一次出现的列 即可。 时间复杂度：\(O(nm)\) 对应AC代码 #define chatgpt "bits/stdc++.h" #include chatgpt using namespace std; //#define FLOATING_OCEAN #define int long long #define pii pair<int, int> #define pipi pair<pii, pii> #define tpi tuple<int, int, int> #define fs first #define sc second #define pb emplace_back #de ...
Contestant~ Rank 1115. Rating +1. 又是一个疯狂叉人场 A. Not a Substring 题意 给定一个长为 \(n\) 的 不一定合法的 括号字符串 \(S\)，构造一个长为 \(2n\) 的 合法 括号字符串 \(T\)，满足 \(S\) 不是 \(T\) 的子串。 思路 可以发现，只要 \(S\) 中存在连续的 \(((\) 或者 \())\)，我们就只需构造 \(()()()\ldots\)。 如果 \(S\) 不满足上述的条件，那么我们就构造存在连续 \(((\) 或者 \())\) 的 \(T\)，即 \((((\ldots)))\ldots\)。 显然，只有 \(()\) 无法构造。 上述操作也可以更改为： 特判 \(()\)； 构造 \((((\ldots)))\ldots\)； 判断是否为子串； 是则输出，否则改为 \(()()()\ldots\)。 至于判断子串，直接判断 \(S\) 是否是由连续的 \((((\ldots\) 和连续的 \()))\ldots\) 拼接而成 ...
Contestant~. Rank 955. Rating +11. 有种瓶颈期的美 A. Buttons 题意 给定三种只能按一次的按钮，按钮 \(a\) 只能被 \(First\) 按，按钮 \(b\) 只能被 \(Second\) 按下，按钮 \(c\) 能被两个人按下。 无法按按钮的玩家输。输出赢者。 思路 \(First\) 能按 \(a + \lceil \frac{c}{2} \rceil\) 个按钮，\(Second\) 能按 \(b + \lfloor \frac{c}{2} \rfloor\) 个按钮，比较大小即可。 时间复杂度：\(O(1)\) 对应AC代码 #include <bits/stdc++.h> using namespace std; //#define FLOATING_OCEAN #define int long long #define pii pair<int, int> #define pipi pair<pii, pii> #define tpi tuple<int, int ...
Contestant~. Rank 1938. Rating -45. 掉分日记.md A. United We Stand 题意 给定一个数组 \(a\)，将其分成两个非空数组 \(b, c\)，满足任意一个 \(c\) 中的元素都不是任意一个 \(b\) 中的元素的约数。 思路 很显然，若 \(x > y\)，则 \(x\) 一定不可能是 \(y\) 的约数。 因而，找出数组中最大值，并将等于最大值的所有数都放到 \(c\) 中，剩余的放到 \(b\) 中即可。 显然，若 \(a\) 中所有元素都相同，那么无解，否则必有解。 时间复杂度：\(O(n) - O(n \log n)\) 对应AC代码 #include <bits/stdc++.h> using namespace std; //#define FLOATING_OCEAN #define int long long #define pii pair<int, int> #define pipi pair<pii, pii> #define ppii pa ...
Contestant_. Rank 230. Rating +111 (+461 -350). 不小心给sqrt传了double，爆精度被叉了一题qaq A. Array Coloring 题意 给定一个序列，将其分成非空两堆，并给两堆数染上不同颜色。 输出是否存在一种分配方式，使两堆数总和的奇偶性相等。 题意 显然，奇偶性相同的两个数相加，得到偶数。 所以总和为偶数就存在，否则不存在。 时间复杂度：\(O(n)\) 对应AC代码 //Code template from Floating Ocean. #include <bits/stdc++.h> using namespace std; //#define FLOATING_OCEAN #define int long long #define pii pair<int, int> #define pipi pair<pii, pii> #define ppii pair<int, pii> #define pci pair<char, int> #defin ...
Contestant~. Rank 707. Rating +20. A. Tales of a Sort 题意 给定一个序列 \(a\)，定义一次操作为将所有数改为 \(\max(0, a_i - 1)\)。 输出让序列 \(a\) 不递减的最小操作数。 思路 既然我们要让序列不递减，那么如果出现了相邻不递减的元素，我们就必须将其减到 \(0\)。 那么，我们就直接枚举所有 \(i \in [1, n - 1]\)，找出所有满足 \(a_i > a_{i + 1}\) 的元素 \(a_i\)，计算 \(\max(a_i)\)。 时间复杂度：\(O(n)\) 对应AC代码 //Code template from Floating Ocean. #include <bits/stdc++.h> using namespace std; //#define FLOATING_OCEAN #define int long long #define pii pair<int, int> #define pipi pair< ...
Contestant~. Rank 316. Rating +66. A. Dalton the Teacher 题意 给定一个序列，定义一次操作为任意交换两个数。 输出让所有 \(a_i \neq i\) 的最小操作数。 思路 显然，我们直接统计 \(a_i = i\) 的个数，这些数就是参与交换的。 我们推一下式子，最后答案就是 \(\frac{cnt + 1}{2}\)。 时间复杂度：\(O(n)\) 对应AC代码 #include <bits/stdc++.h> using namespace std; //#define FLOATING_OCEAN #define int long long #define pii pair<int, int> #define pipi pair<pii, pii> #define ppii pair<int, pii> #define pci pair<char, int> #define fs first #define sc second #define pb e ...
Contestant~. Rank 856. Rating +27 (+77 -50). A. Morning Sandwich 题意 规定三明治的顶部和底部分别是两块面包片，中间由若干层火腿肠或芝士组成，每层之间由面包片分隔。 现在，给定面包片，芝士和火腿肠的数量，输出最大的层数。 思路 如题，推一个式子即可。 时间复杂度：\(O(1)\) 对应AC代码 #include <bits/stdc++.h> using namespace std; //#define FLOATING_OCEAN #define int long long #define pii pair<int, int> #define pipi pair<pii, pii> #define ppii pair<int, pii> #define pci pair<char, int> #define fs first #define sc second #define pb emplace_back #define rall(x) x.rbegin( ...