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() ...
Practice. A. Colored Balls: Revisited 题意 给定 \(n\) 个染有颜色的球，定义操作为选定两个不同颜色的球并将两个球拿走。 在满足总和为奇数的情况下，输出只剩下一种颜色的球后，球的颜色编号。 思路 显然，我们将数量小的和数量次小的球拿走，最后肯定会剩下数量最多的那个颜色。 时间复杂度：\(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 all(x) x.begin(),x.end() const int N = 110, inf = 0x3f3f3f3f3f3f3f3f; void solve(){ int n; cin >> n; v ...
Contestant'. Rank 1390. Rating +9(+109 -100). A. Divisible Array 题意 给定整数 \(n\)，构造一个长度为 \(n\) 的数组 \(a\)，满足 \(a_i \bmod i = 0\)，且总和 \(sum\) 满足 \(sum \bmod n = 0\)。 思路 构造一个 \(2, 4, \ldots, 2n\) 的数组，\(sum = \frac{(2 + 2n)n}{2} = n(n + 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( ...
Contestant'. Rank 1580. Rating +23(+173 -150). A. New Palindrome 题意 给定一个回文串，输出是否可以将其重新排序，变成另一个回文串。 思路 只要回文串中有两种不同的字符，且这两个字符出现次数都大于 \(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 = 110, inf = 0x3f3f3f3f3f3f3f3f; void solve(){ string s; cin >> s; ...
Contestant'. Rank 1357. Rating +14 (+264 -250). A. LuoTianyi and the Palindrome String 题意 给定一个字符串，输出最长的非回文子串的长度。 思路 很显然，如果整个字符串是回文串，那么我们拿掉一个字符即可，长度为 \(n - 1\)； 如果不是，那么整个字符串就是非回文串，长度为 \(n\)。 当然，如果整个字符串都是由一个字母组成的，那么无法将其变为非回文，无解输出 \(-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() ...