Contestant~. Rank 313. Rating +53. 这场的 \(E\) 难度感觉很有争议，感觉放 \(C\) 都不过分（个人看法 A. green_gold_dog, array and permutation 题意 给定一个序列 \(a\)，构造一个排列 \(b\)，使所有 \(a_i - b_i\) 中不同值的个数最大，并输出方案。 思路 显然地，因为我们可以减到负数，那么我们用大数减小数的方式，一定可以构造出尽可能多的 \(a_i - b_i\)。 时间复杂度：\(O(n)\) 对应AC代码 #define chatgpt3_5 "bits/stdc++.h" #define chatgpt4 "bits/extc++.h" #include chatgpt3_5 using namespace std; //#define FLOATING_OCEAN #define int long long #define pii pair<int, int> #define pipi pair<pii, pi ...
Contestant~. Rank 257. Rating +51. A. Make It Zero 题意 给定一个序列，定义一次操作为选定一个区间，并将区间内的所有数全都替换为他们的异或总和。 输出不超过 \(8\) 次操作后，让整个序列变为 \(0\) 的一种方案。 思路 我们分奇偶性来考虑： 如果序列长度为偶数，显然偶数个相同的元素异或和为 \(0\)，那么我们只要对整个序列进行异或，然后再重复一次操作即可； 如果序列长度为奇数，那么我们同上，对前 \(n - 1\) 个元素执行两次操作。因为任何数和 \(0\) 异或都是它本身，因而我们对最后两个元素操作两次即可。 时间复杂度：\(O(1)\) 对应AC代码 #define chatgpt3_5 "bits/stdc++.h" #define chatgpt4 "bits/extc++.h" #include chatgpt3_5 using namespace std; //#define FLOATING_OCEAN #define int long long #def ...
Contestant_. Rank 344. Rating +183. A. Two Vessels 题意 给定两个水槽，初始状态下有 \(a, b\) 单位的水。现在给定一个容量为 \(c\) 的水杯，输出最少需要舀几次水，让两个水槽的水体积相等 思路 显然我们缺少 \(\frac{abs(a- b)}{2}\)，设其为 \(p\)，那么我们需要舀 \(\lceil \frac{p}{c} \rceil\) 次。 时间复杂度：\(O(1)\) 对应AC代码 #define chatgpt3_5 "bits/stdc++.h" #define chatgpt4 "bits/extc++.h" #include chatgpt3_5 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 881. Rating +7. A. Prime Deletion 题意 给定 \(\{0, 1, \ldots, 9\}\) 的一种排列，定义一次操作为在排列剩余元素个数 大于2 的条件下，任意删去一个数字。 任意次操作后，输出排列拼接而成的数字，并满足该数字是质数。 思路 因为 \(13, 31\) 都是质数，并且 \(1\) 一定在 \(3\) 的左边或者右边，因而判一下 \(1\) 的位置即可。 时间复杂度：\(O(n)\) 对应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 #defi ...
Contestant~. Rank 1909. Rating -24. A. Channel 题意 定义每个人上线都会阅读所有帖子。 现在，\(A\) 发布了一篇文章，发布的时候。 给定由 "+", "-" 组成的字符串，分别代表该时刻有一个人上线/下线，按照下面的方式输出答案： 所有人都阅读过该文章，输出 \(YES\)； 有可能所有人都阅读过该文章，输出 \(MAYBE\)； 所有人都不可能阅读过该文章，输出 \(NO\) 思路 所有人都阅读过的条件是假设下线后上线的是同一个人，有可能所有人都阅读过的条件是假设下线后上线的是不同的人。 否则就是不可能。 时间复杂度：\(O(n)\) 对应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< ...
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 ...