Contestant'. Rank 785. Rating +41. A. The Good Array 题意 定义满足下面条件的二进制数组 \(a\) 是好的： 枚举 \(i \in [1, n]\)，前 \(i\) 个数至少有 \(\lceil \frac{i}{k} \rceil\) 个为 \(1\)，后 \(i\) 个数至少有 \(\lceil \frac{i}{k} \rceil\) 个为 \(1\)。 给定 \(k\)，输出好数组中 \(1\) 的最少个数。 思路 首先，第一个和最后一个一定是 \(1\)。 那么，对于前 \(n - 1\) 个数，至少有 \(\lceil \frac{n - 1}{k} \rceil\) 个 \(1\)。 因此，答案即为 \(\lceil \frac{n - 1}{k} \rceil + 1\)。 时间复杂度：\(O(1)\) 对应AC代码 #include <bits/stdc++.h> using namespace std; #define int long long #define ...
Contestant'. Rank 1872. Rating -13. 罚时吃饱了 A. Blackboard List 题意 有一块黑板，初始状态下只有两个数字。 定义操作为任选黑板上的两个数字，将两者的差的绝对值写到黑板上。 现在，给定打乱顺序后的黑板上的数字序列，输出其中任意一个初始状态的数字。 思路 首先，因为我们写上去的数字一定是非负数，所以如果序列中有负数，那直接输出。 否则，那么不会出现正数减负数的情况，也就是说，我们写上去的数一定是小于初始状态下的最大数字的。 因此，如果序列都是非负数，最大值就是答案。 时间复杂度：\(O(n)\) 对应AC代码 #include <bits/stdc++.h> using namespace std; #define int long long #define pii pair<int, int> #define pci pair<char, int> #define fs first #define sc second #define pb emplace_back #def ...
Contestant'. Rank 1013. Rating +32. A. Twin Permutations 题意 给定一个排列 \(a\)，构造另一个排列 \(b\)，满足 \(a_i + b_i\) 不递减。 思路 那也就可以是相等。 因为是长度相等的排列，因而一定可以得到 \(n\) 个和为 \(n + 1\) 的组合。 因而，输出 \(n - a_i + 1\) 即可。 时间复杂度：\(O(n)\) 对应AC代码 #include <bits/stdc++.h> using namespace std; #define int long long #define pii pair<int, int> #define pci pair<char, int> #define fs first #define sc second #define pb emplace_back #define all(x) x.begin(),x.end() const int N = 2e5 + 10, mod = 998244353, ...
Contestant'. Rank 1622. Rating +15. A. Grasshopper on a Line 题意 给定一个数轴，终点 \(x\) 以及一个整数 \(k\)，定义一次操作为从当前位置向右移动 \(p\) 格，满足 \(p\mod k \neq 0\)。输出从原点走到 \(x\) 所需的最小的操作数以及方案。 思路 如果 \(x\) 不能被整除，一步即达。 可以被整除的话，\(x - 1\) 肯定不会被整除（互质），因此选择先走一格再走 \(x - 1\) 格。 时间复杂度：\(O(1)\) 对应AC代码 #include <bits/stdc++.h> using namespace std; #define int long long #define pii pair<int, int> #define pci pair<char, int> #define fs first #define sc second #define pb emplace_back #define all(x) x.begi ...
One contestant of team004. Rank 1. Solved 7/12. A. Tree Destruction 图论+组合数，待补充 B. Encore 计算几何，待补充 C. Konnakol 题意 无穷次重复斐波那契数列的前八项，构成一个序列。 给定整数 \(n, k\)，提取出前 \(n\) 个数，输出第 \(k\) 个数。 思路 首先，\(n\) 是没用的。 其次，取模即可。 时间复杂度：\(O(1)\) 对应AC代码 #include <bits/stdc++.h> using namespace std; #define int long long #define pii pair<int, int> #define pci pair<char, int> #define fs first #define sc second #define pb emplace_back #define all(x) x.begin(),x.end() const int N = 2e5 + ...
Contestant'. Rank 847. Rating +31(+81 -50). 又一次成为痛苦号（ A. Musical Puzzle 题意 给定一个字符串，输出所有相邻两个字符组成的不同字符串的个数。 思路 如题，用 \(map\) 即可。 时间复杂度：\(O(n \log n)\) 对应AC代码 #include <bits/stdc++.h> using namespace std; #define int long long #define pii pair<int, int> #define pci pair<char, int> #define fs first #define sc second #define pb emplace_back #define all(x) x.begin(),x.end() const int N = 2e5 + 10, mod = 1e9 + 7; void solve(){ int n; cin >> n; string s; c ...
Prime 题意 给定一个数 \(a\)，按照算术基本定理分解后给出指数序列，输出最小的 \(n\)，满足 \(n! \bmod a = 0\)。 思路 首先，指数序列的长度很小，不妨直接打表（不打表的话无脑线性筛筛一下即可）。 其次，既然需要被 \(p\) 整除，那么阶乘中就需要有对应数量的因子。 举个例子，如果 \(p\) 的质因子 \(7\) 的指数为 \(4\)，那么阶乘中就最好有 \(1 \times 7, 2 \times 7, 3 \times 7, 4 \times 7\)，也就是说，我们期望 \(n\) 至少为 \(28\)。 想到这里，数据量比较特殊的时候，底数和指数乘积的最大值就是答案。 那么，如果指数大于等于底数呢？就像上述例子，出现 \(7 \times 7\) 的时候，我们需要的 \(7\) 的个数就小于等于指数的大小了，因此我们不能直接取底数和指数的乘积。 这边有两个思路： 数位 \(dp\) 线性预处理； 设底数为 \(x\)，指数为 \(p\)，对于所需的最大 \(x \times p\)，二分 \(p\)。 ...
Practice. A. Madoka and Strange Thoughts 题意 给定整数 \(n\)，输出二元组 \((a, b)\) 的个数，满足 \(\frac{\operatorname{lcm}(a, b)}{\operatorname{gcd}(a, b)} \leq 3\)。 思路 我们不妨打个表： n cnt 1 1 2 3 3 3 4 3 5 1 6 5 7 1 8 3 9 3 10 3 11 1 12 5 13 1 ... ... 不难发现出现了循环。 更具体地说，令 \(sum = \{0, 1, 4, 7, 10, 11\}\)，那么答案就是 \(16(\frac{n}{6}) + sum[n \% 6]\)。 时间复杂度：\(O(1)\) 对应AC代码 #include <bits/stdc++.h> usin ...
Practice. A. Mainak and Array 题意 给定一个序列 \(a\)，定义操作为选定一个连续字符列，并将其旋转任意次，输出恰好进行一次操作后 \(a_n - a_1\) 的最大值。 思路 首先，如果选定整个序列作为旋转序列，那么显然对于两个相邻的数，前者减后者就可以作为执行操作后的 \(a_n - a_1\)，取最大值即可。 其次，我们可以固定头或者尾，如果固定头，我们就可以旋转除头以外的其他元素，将最大值旋转到 \(a_n\)，反之同理，最后再取最大值即可。 时间复杂度：\(O(n)\) 对应AC代码 #include <bits/stdc++.h> using namespace std; #define int long long #define pii pair<int, int> #define pci pair<char, int> #define fs first #define sc second #define pb emplace_back #define all(x) x.begin() ...