Contestant~. Rank 1938. Rating -45. 掉分日记.md A. United We Stand 题意 给定一个数组 \(a\)，将其分成两个非空数组 \(b, c\)，满足任意一个 \(c\) 中的元素都不是任意一个 \(b\) 中的元素的约数。 思路 很显然，若 \(x > y\)，则 \(x\) 一定不可能是 \(y\) 的约数。 因而，找出数组中最大值，并将等于最大值的所有数都放到 \(c\) 中，剩余的放到 \(b\) 中即可。 显然，若 \(a\) 中所有元素都相同，那么无解，否则必有解。 时间复杂度：\(O(n) - O(n \log n)\) 对应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 ppii pa ...
Contestant_. Rank 230. Rating +111 (+461 -350). 不小心给sqrt传了double，爆精度被叉了一题qaq A. Array Coloring 题意 给定一个序列，将其分成非空两堆，并给两堆数染上不同颜色。 输出是否存在一种分配方式，使两堆数总和的奇偶性相等。 题意 显然，奇偶性相同的两个数相加，得到偶数。 所以总和为偶数就存在，否则不存在。 时间复杂度：\(O(n)\) 对应AC代码 //Code template from Floating Ocean. #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 ppii pair<int, pii> #define pci pair<char, int> #defin ...
Contestant~. Rank 707. Rating +20. A. Tales of a Sort 题意 给定一个序列 \(a\)，定义一次操作为将所有数改为 \(\max(0, a_i - 1)\)。 输出让序列 \(a\) 不递减的最小操作数。 思路 既然我们要让序列不递减，那么如果出现了相邻不递减的元素，我们就必须将其减到 \(0\)。 那么，我们就直接枚举所有 \(i \in [1, n - 1]\)，找出所有满足 \(a_i > a_{i + 1}\) 的元素 \(a_i\)，计算 \(\max(a_i)\)。 时间复杂度：\(O(n)\) 对应AC代码 //Code template from Floating Ocean. #include <bits/stdc++.h> using namespace std; //#define FLOATING_OCEAN #define int long long #define pii pair<int, int> #define pipi pair< ...
Contestant~. Rank 316. Rating +66. A. Dalton the Teacher 题意 给定一个序列，定义一次操作为任意交换两个数。 输出让所有 \(a_i \neq i\) 的最小操作数。 思路 显然，我们直接统计 \(a_i = i\) 的个数，这些数就是参与交换的。 我们推一下式子，最后答案就是 \(\frac{cnt + 1}{2}\)。 时间复杂度：\(O(n)\) 对应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 ppii pair<int, pii> #define pci pair<char, int> #define fs first #define sc second #define pb e ...
Contestant~. Rank 856. Rating +27 (+77 -50). A. Morning Sandwich 题意 规定三明治的顶部和底部分别是两块面包片，中间由若干层火腿肠或芝士组成，每层之间由面包片分隔。 现在，给定面包片，芝士和火腿肠的数量，输出最大的层数。 思路 如题，推一个式子即可。 时间复杂度：\(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 ppii pair<int, pii> #define pci pair<char, int> #define fs first #define sc second #define pb emplace_back #define rall(x) x.rbegin( ...
Contestant_. Rank 240. Rating +152 (+652 -500). A. Escalator Conversations 题意 给定 \(m\) 个台阶，以及相邻两个台阶的平面所在的高度差 \(k\)。 另给定 \(n\) 个人，每个人的高度是 \(h_i\)。 若两个人站在两个不同的台阶上，且 两个人的身高差 等于 这两个台阶的高度差，那么他们可以一起聊天。 给定 \(A\) 的身高 \(H\)，输出他可以和多少人聊天。 思路 题意简化为：遍历 \(h_i\)，设 \(x = abs(H - h_i)\)，记录满足 \(x | k\) 且 \(1 \leq \frac{x}{k} \leq m - 1\) 的个数。 时间复杂度：\(O(n)\) 对应AC代码 #include <bits/stdc++.h> using namespace std; //#define FLOATING_OCEAN #define int long long #define pii pair<int, int> # ...
Contestant~. Rank 1116. Rating -8(+92 -100). A. Desorting 题意 给定一个序列 \(a\)，定义操作如下： 选择一个下标 \(i \in [1, n - 1]\)； 将 \(a_1, a_2, \ldots, a_i\) 中所有元素 \(+1\)； 将 \(a_{i+1}, a_{i+2}, \ldots, a_n\) 中所有元素 \(-1\) 输出使序列 \(a\) 不是不递减序列的最小操作数。 思路 显然，我们只需贪心地认为序列中某两个相邻数满足 \(a_i > a_{i + 1}\)，就可以判定其不是不递减序列。 那么，我们先判断给定序列是否是不递减序列，如果不是，直接输出 \(0\)； 否则，我们找出相邻差值的最小值 \(d\)，答案即为 \(\frac{d}{2} + 1\)。 时间复杂度：\(O(n)\) 对应AC代码 #include <bits/stdc++.h> using namespace std; //#define FLOATING_ ...
Contestant~. Rank 96. Rating +99. (+249 -150). 终于ak一场div4了 A. To My Critics 题意 给定三个数，输出最大两个数的和是否 \(\geq 10\)。 思路 如题。 方便写的话可以考虑存到数组里。 时间复杂度：\(O(n \log n)?\) 对应AC代码 #pragma GCC optimize(2) #include <bits/stdc++.h> using namespace std; #define int long long #define pii pair<int, int> #define pipi pair<pii, pii> #define ppii pair<int, pii> #define pci pair<char, int> #define fs first #define sc second #define pb emplace_back #define rall(x) x.rbegin(),x.rend() #def ...
Contestant. Rank 1293. Rating +429. 待更新. A. Order Something Else 题意 给定一个需要购买的物品的原价和促销价。 促销价需要多买一个其他物品，需在 \(n\) 个物品中选一个，并支付额外费用。 输出最少开支。 思路 从额外需购买的物品中找出最小价格，并和促销价求和，最后和原价取最小值。 时间复杂度：\(O(n)\) 对应AC代码 #include <bits/stdc++.h> using namespace std; #define int long long #define pii pair<int, int> #define pipi pair<pii, pii> #define ppii pair<int, pii> #define pci pair<char, int> #define fs first #define sc second #define pb emplace_back #define all(x) x.begin(),x.end() ...