Personal solution. A. Yet another permutation problem 背景 来自 Codeforces Round 876 (Div. 2) D题。 *2100 dp. 题意 给定一个 \(n\) 的排列 \(a\)，对于整数 \(k\)，按照下面的操作进行排序： 在排列中任意添加 \(k\) 个 \(0\)； 在一次操作中，可选择一个和 \(0\) 相邻的元素，并将其移动到任何位置。 对于 \(k \in [1, n]\)，输出第二种操作最少需要几次，才能让排列升序。 思路 \(dp\)。 首先，既然需要最少操作，不妨找到最长递增子序列，因而我们会发现，我们只需用该序列的元素将排列分段，每一段放上一个 \(0\)，即可让需要的 \(0\) 个数最少。如果个数不够，那怎么去掉呢？如何优先选择呢？ 上面的思路很显然，但存在一种情况：有多个最长递增子序列。因而，这种 "暴力" 的方法不可行。 既然上面的子序列问题已经需要使用 \(dp\) 了，我们不妨想想如何用 \(dp\) 直接解决。 上面， ...
Contestant. Rank 309. Rating +66. A. Secret Sport 题意 对于两个人之间的博弈，定义一局中先赢了 \(X\) 次的玩家在该局中获胜，赢了 \(Y\) 局的玩家获得最后的胜利。 其中，若能确定最后的赢家，那么将立即停止博弈。 现在，在 \(X, Y\) 未知 的条件下，给定一次游戏中，每局获胜的玩家，输出最后的赢家。 思路 既然能确定最后的赢家，那么后面就不会有新的一局了。 换句话说，最后一局决定了当前的赢家。 显然，决定的条件只有一个：最后一个玩家赢了 \(X\) 次。那么，显然最后一局的赢家就是最后的赢家了。 因而，读入字符串后，输出最后一个字符即可。 时间复杂度：\(O(1)\) 对应AC代码 #include <bits/stdc++.h> using namespace std; //#define FLOATING_OCEAN #define int long long #define pii pair<int, int> #define pdd pair<dou ...
Contestant. Rank 761. Rating +41. A. Rigged! 题意 给定 \(n\) 个人的臂力 \(s_i\) 和耐力 \(e_i\)。若比赛的杠铃重量为 \(w\)，那么所有满足 \(s_i \geq w\) 的人都可以举起杠铃，且可以举起 \(e_i\) 次。 输出最小的 \(w\)，使第一个玩家能举起的次数严格最多。 思路 显然，我们要做的就是，让耐力大于等于第一个玩家的人都举不起杠铃。 那么，我们统计耐力大于等于第一个玩家的所有玩家的力量最大值，然后判断最大值是否小于第一个玩家的力量即可。 如果满足，那么 \(w = s_1\)，否则无解。 时间复杂度：\(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 ...
Contestant. Rank 728. Rating +14. A. Increasing Sequence 题意 给定一个长度为 \(n\) 的序列 \(a\)，构造一个满足下面条件的序列 \(b\)： 长度为 \(n\)； 严格递增； \(a_i \neq b_i\) 输出最小的满足条件的 \(b_n\)。 思路 显然，我们模拟一下构造即可。 我们从 \(1\) 开始向后枚举，如果当前位和 \(a_i\) 相等，那么我们就多加一个 \(1\)。 时间复杂度：\(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, pii> #def ...
Contestant^. Rank 154. Rating +119 (+469 -350). 不知道有没有可能在有生之年打到 cf 第1000场（ A. How Much Does Daytona Cost? 题意 给定一个序列 \(a\)，以及一个整数 \(k\)，判断 \(k\) 是否是 \(a\) 的任意子串中出现次数最多的字符。 思路 只要子串长度是 \(1\)，那么该字符就是出现次数最多的字符。 那么，问题就转化为判断 \(k\) 是否在 \(a\) 中出现了。 时间复杂度：\(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, pii> ...
Contestant^. Rank 132. Rating +86 (+336 -250). A. Don't Try to Count 题意 给定两个字符串 \(s, t\)，定义操作为将 \(s\) 本身拼接到 \(s\) 后面，操作非独立。 输出最小的操作次数，使 \(s\) 中包含子串 \(t\)。 思路 显然，数据范围小的离谱，那么我们直接暴力。 我们暴力拼接，然后用合适的复杂度下的字符串匹配即可。 可以发现，需要拼接的次数是很少的，此处用了最多 \(10\) 次，但应该不用这么多。 至于匹配，可以用 \(\mathtt{strstr}\) 函数，底层是用 \(\mathtt{KMP}\) 算法实现的，可以跑的飞快。 时间复杂度：\(O(不大)\) 对应AC代码 #define chatgpt3_5 "bits/stdc++.h" #define chatgpt4 "bits/extc++.h" #include chatgpt3_5 using namespace std; //#define FLOATING_OCEAN ...
Contestant. Rank 728. Rating +14. 罚时爆炸 A. Jellyfish and Undertale 题意 对于一个即将引爆的炸弹，给定 \(i\) 个工具，每个工具最多使用一次，使用时将会使炸弹的计时器 \(+x_i\) 个单位时间，但如果计时器的时间大于 \(a\)，它将会复位为 \(a\)。 找出一个方案，使计时器在归 \(0\) 前，时间尽可能长，并输出这个时间。 思路 显然，为了让时间尽可能长，我们一定会在计时器为 \(1\) 时使用工具，那么工具的使用顺序是无所谓的。 那么，我们只需将每个工具的 \(x_i\) 和 \(a - 1\) 取最小值，然后累加即可。 时间复杂度：\(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 l ...
Practice. A. Goals of Victory 题意 对于 \(n\) 只队伍，存在 \(\frac{n(n - 1)}{2}\) 个任意两只队伍间的比赛。每支队伍具有一个效率值，为队伍的所有比赛中自己的进球数减去其他队伍进球数的总和。 现在，给定 \(n - 1\) 个队伍的效率，求第 \(n\) 个队伍的效率。 思路 对于一场比赛，如果 \(A\) 赢，那么 \(A\) 的效率 \(+ 1\)，\(B\) 的效率 \(-1\)。 因而，所有队伍的效率和为定值 \(0\)。 那么，第 \(n\) 个队伍的效率为前 \(n - 1\) 个队伍的效率和的相反数。 时间复杂度：\(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 ...
Contestant. Rank 263. Rating +90. A. Sum of Three 题意 给定一个整数 \(n\)，构造一种方案，使得 \(n = x + y + z\)，且 \(x \neq y \neq z; x, y, z \not \equiv 0 \pmod 3\)。 思路 分类讨论。 首先，最小的构造是 \(x = 1, y = 2, z = n - 3\)，那么显然，\(n - 3 > 2\)，即 \(n \geq 6\)。 并且，因为 \(z\) 不可以是 \(3\) 的倍数，所以 \(n\) 也不可以是 \(3\) 的倍数。 那么，如果 \(n\) 是 \(3\) 的倍数，我们考虑次小的构造：\(x = 1, y = 4, z = n - 5\)，此时 \(n - 5 > 4\)，即 \(n \geq 10\)。 此时，可以发现 \(n - 5\) 不是 \(3\) 的倍数，从而符合要求。 时间复杂度：\(O(1)\) 对应AC代码 #define chatgpt3_5 "bits/stdc++.h" ...