这是一个部署在 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 ...
Solved 9 of 12. 年度鸡场 A. 复制鸡 题意 对于一个数组，定义一次操作为选择一个连续子序列，并将每个数复制一份加在原数后面。给定任意次操作后的数组，输出原数组的最小长度。 思路 问题等价为求数组最少可以被划分为多少段，满足每段内元素相同。 也就是说，答案是拐点 \(+1\)。 时间复杂度：\(O(n)\) 对应AC代码 void solve() { int n; cin >> n; vector<int> a(n + 1); for(int i=1;i<=n;i++) cin >> a[i]; int ans = 0; for(int i=1;i<=n;i++) { if(a[i] != a[i - 1]) ans ++; } cout << ans << '\n'; } 唯一有用的是pdf欸！ B. 好伙计猜拳 题意 定义对于一个长为 \(p\) 的整数二元 ...
Solved 9 of 12. 坑一堆（ A. 小L的三则运算 题意 给定一个大于 \(1\) 的正整数 \(x\) 和一个二元运算符（加减乘之一），输出两个正整数，满足使用该二元运算符计算得到的结果为 \(x\)。 思路 钦定其中一个正整数为 \(1\) 即可。 时间复杂度：\(O(1)\) 对应AC代码 void solve() { int x; string op; cin >> x >> op; if(op == "*") cout << x << ' ' << 1 << '\n'; else if(op == "+") cout << x - 1 << ' ' << 1 << '\n'; else cout << x + 1 << ' ' << 1 << '\n'; } 签到 B. 小L出师了 题意 给定三个正整数 ...
Solved 10 of 12. 欸我去出题人怎么是go批，欸我去mygo还在追我 A. Tokitsukaze and Absolute Expectation 题意 对于一个长为 \(n\) 的序列 \(a\)，第 \(i\) 个元素 \(a_i\) 的值将会从 \([l_i, r_i]\) 中独立等概率生成。定义： \(\displaystyle \text{val}(a) = \sum_{i=2}^n |a_{i - 1} - a_i|\) 求 \(\text{val}(a)\) 的期望。 思路 首先，因为每个元素值生成的事件是相互独立的，所以根据期望的可加性，将式子化简如下： \(E(\text{val}(a)) = E(\displaystyle \sum_{i=2}^n |a_{i - 1} - a_i|) = \displaystyle \sum_{i=2}^n E(|a_{i - 1} - a_i|)\) 对于 \(E(|a_{i - 1} - a_i|)\)，记 \(a_{i - 1} \in [l_1, r_1], a_i ...
Solved 8 of 13. 难度偏大场 A. 智乃的博弈游戏 题意 给定 \(n\) 个石子。对于两个人的博弈，每轮可拿走与当前石子个数互质数量的石子，剩余 \(1\) 个石子时玩家获胜。判断先手是否必胜。 思路 经典猜猜题，不过也是一个比较经典的博弈。 可以发现，\(1\) 和所有数都互质，那么我们从必胜态往后推。 首先，显然 \(1\) 为必胜态，\(2\) 因为可以拿走 \(1\) 个石子所以成为必败态。对于 \(3\) 来说，可以拿走 \(1\) 或 \(2\) 个石子，显然当拿走 \(1\) 个石子时可以达到必败态，所以 \(3\) 也是一个必胜态。 如上进行递推，可以归纳总结出：奇数时必胜，偶数时必败。 时间复杂度：\(O(1)\) 对应AC代码 void solve() { int x; cin >> x; cout << (x % 2 == 0 ? "No" : "Yes") << '\n'; } 主打一个手速 B. 能去你家蹭口饭吃吗 ...
Solved 9 of 13. 退役老登来凑个热闹 A. 一起奏响历史之音！ 题意 给定 \(7\) 个数，判断是否由 \(1, 2, 3, 5, 6\) 组成。 思路 如题，模拟即可。 时间复杂度：\(O(n)\) 对应AC代码 void solve() { int n = 7; bool ok = true; while(n --) { int x; cin >> x; if(x == 4 || x == 7) ok = false; } cout << (ok ? "YES" : "NO") << '\n'; } 主打一个手速 B. 能去你家蹭口饭吃吗 题意 给定长为 \(n\) 的序列 \(a\)。记 \(x\) 小于序列 \(a\) 中至少 \(\lfloor \frac{n}{2} \rfloor + 1\) 个数字，求 \(x\) 的最大值。 思路 只需小于序列 \(a ...
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 ...