Rank 264/3889. Solved 6/11. 写完 \(6\) 题后干活去了，结果发现还有个不太难的题（ A. 柠檬可乐 题意 给定三个整数 \(a, b, k\)，判断 \(a \geq k \times b\) 是否成立。 思路 如题。 时间复杂度：\(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, int> #define fs first #define sc second #define pb emplace_back #define ep emplace #de ...
Rank 114/3990. Solved 10/13. 罚时爆炸场 A. 智乃与瞩目狸猫、幸运水母、月宫龙虾 题意 给定两个字符串 \(s, t\)，判断他们的首字母在不区分大小写的情况下是否相等。 思路 如题。可以使用 \(\mathtt{toupper}\) 之类的函数。 时间复杂度：\(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, int> #define fs first #define sc second #define pb emplace_back #defin ...
Rank 220/4526. AC 8/13. 迟到了 \(20\) 分钟，赛后 \(8\) 分钟就把 \(A, B\) 切了（ A. Tokitsukaze and Bracelet 题意 给定三种加成的属性值，根据属性值，有下面的加成规则： 对于第一种属性值 \(a\)：\(a=100\) 时 \(+0\)，\(a=150\) 时 \(+1\)，\(a=200\) 时 \(+2\)； 对于后两种属性值 \(b, c\)：值为 \(\{29, 30, 31, 32\}\) 时 \(+0\)，值为 \(\{34, 36, 38, 40\}\) 时 \(+1\)，值为 \(45\) 时 \(+2\) 输出总加成。 思路 如题，模拟即可。 时间复杂度：\(O(1)\) 对应AC代码 #define chatgpt3_5 "bits/stdc++.h" #define chatgpt4 "bits/extc++.h" #include chatgpt3_5 using namespace std; //#define FLOATING_OC ...
Rank 192/4984. AC 9/13. 被B题搞了，于是开摆 A. DFS搜索 题意 判断给定字符串是否包含子序列 \(\mathtt{DFS}\)，以及是否包含子序列 \(\mathtt{dfs}\)。用二进制给出两个判断结果。 思路 以第一个 \(\mathtt{D}\) 为起点往后找，然后将第一个 \(\mathtt{F}\) 作为起点继续找，如果能找到 \(\mathtt{S}\) 则包含子序列 \(\mathtt{DFS}\)。 小写同理。 时间复杂度：\(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> #define t ...
Personal solution. A. A Mistaken Input 题意 输出字符串中有多少个 \(1\)。 思路 签到题。 如题。 时间复杂度：\(O(n)\) 对应AC代码 #include <bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(false), cin.tie(0), cout.tie(0); int n; cin >> n; string s; cin >> s; int cnt = 0; for(auto e : s){ if(e == '1') cnt ++; } cout << cnt << '\n'; } 取材于现实（ B. Backpack of Capoo 题意 给定 \(n\) 个物品，每个物品具有体积 \(v_i\) 和价值 \(w_i\)。 ...
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 ...