这是一个部署在 Github / Gitee / blog.flocean.top 上的基于 Hexo + Butterfly 的个人博客，目前涵盖部分算法竞赛平台的个人题解和思路。更多内容请查看文章原文...
Contestant. Rank 978. Rating -34. A. Cover in Water 题意 给定一个水槽，水槽中某些格子不可以放水，从而由 "每个格子是否可以放水" 构成给定字符串 \(s\)，\(s_i = \mathtt{.}\) 时即为可放水。 现在，需要将水槽填满水，并无视不可以放水的格子，有下面两种操作： 在指定格子上填水； 将某个格子的水取走，填入另一个格子中 定义若一个格子的两边都有水，那么这个格子也会自动被填上水。 输出操作 \(1\) 的最小次数。 思路 首先，只要能构成题意中的特殊情况，我们就有无限水了，从而不需要操作一。 那么，我们只需将字符串按照 非 \(\mathtt{.}\) 字符 分段，如果存在长度 \(\geq 3\) 的分段，那么我们就只需执行两次操作 \(1\)，否则所有空的位置都需要执行一次操作 \(1\) 才能填满。 从而，前者需要 \(2\) 次，后者的次数为字符串中 \(\mathtt{.}\) 的个数。 时间复杂度：\(O(n)\) 对应AC代码 #include ...
Rank 66/3225. Solved 9/11. 这次的标题是 Arcaea 主线2 的时代了！ A. 宇宙的终结 题意 给定两个正整数 \(l, r\)，找出 \([l, r]\) 中的一个数，满足其为三个不同素数的乘积。 思路 范围很小，直接打出 \(6\) 个素数然后暴力算一下就行。 时间复杂度：\(O(6^3)\) 对应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_b ...
Rank 44/3682. Solved 12/13. 简单题太多坑，难题都有点眼熟 A. mutsumi的质数合数 题意 给定一个数组 \(a_i\)，求数组中质数和合数的数量之和。 思路 只有 \(1\) 既不是质数也不是合数，所以答案为 \(n - cnt_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> #define tpi tuple<int, int, int> #define fs first #define sc second #define pb emplace_back #define e ...
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\)。 ...