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() ...
Contestant'. Rank 472. Rating +58 (+408 -350). 这场没WA!!! 开心捏 A. Love Story 题意 对于字符串 "codeforces"，给定一个与其长度相等的字符串，按位遍历，输出不同位置的个数。 思路 如题，暴力即可。 时间复杂度：\(O(n)\) 对应AC代码 #include <bits/stdc++.h> using namespace std; #define int long long #define pii pair<int, int> #define fs first #define sc second #define pb emplace_back #define all(x) x.begin(), x.end() #define r_all(x) x.rbegin(), x.rend() const int inf = 0x3f3f3f3f3f3f3f3f; void solve(){ string s; cin >> s; s ...
Contestant'. Rank 1818. Rating +61(+561 -500). A. Trust Nobody 题意 定义一群人中有一定数量的人撒谎。对于每个人 \(i\)，会给出他所说的撒谎的人至少有 \(a_i\) 人。输出撒谎的人的数量。 思路 我们直接遍历撒谎的人的数量 \(x\)，然后枚举 \(a_i > x\) 的数量，从而如果数量和 \(x\) 一致，我们就找到了答案。 时间复杂度：\(O(n ^ 2)\) 对应AC代码 #include <bits/stdc++.h> using namespace std; #define int long long #define pii pair<int, int> #define fs first #define sc second #define pb emplace_back #define all(x) x.begin(), x.end() const int N = 2e6, mod = 1e9 + 7; void solve(){ i ...
Practice. A. Two Elevators 题意 给定两个电梯，电梯从一层移动到相邻层需要一秒。当前人位于第一层；第一个电梯位于 \(a\) 层；第二个电梯位于 \(b\) 层，但是该电梯会先前往 \(c\) 层。 输出最先到达第一层的电梯的耗时。 思路 第一个电梯耗时 \(a - 1\)，第二个梯子耗时 \(abs(b - c) + c - 1\)。 取最小值即可。 时间复杂度：\(O(1)\) 对应AC代码 #include <bits/stdc++.h> using namespace std; #define int long long #define pii pair<int, int> #define pdd pair<double, double> #define fs first #define sc second void solve() { int a, b , c; cin >> a >> b >> c; int p = abs(a - 1), q = abs( ...
Contestant. Rank 474. Rating +86. A. Politics 题意 对于 \(n\) 个人，有 \(m\) 个意见，每个人需要对意见做表率（\(+\)表示同意，\(-\) 表示不同意）。 在对一个意见做完表率后，如果同意的人多，那么不同意的人将会离开；如果不同意的人多，那么同意的人将会离开；如果人数一样多，那么所有人都离开。 规定可以在所有人表率前，拿掉一些人。设第一个人为自己，那么输出自己能留到最后的条件下最后剩余的人数的最大值。 思路 首先，如果有其他人的任意一个意见的表率和自己不一样，那么最后自己或者那个不一样的人会离开，所以，所有意见的表率和自己都相同的人的个数加上 \(1\) 就是答案。 时间复杂度：\(O(n)\) 对应AC代码 #include <bits/stdc++.h> using namespace std; #define int long long #define pii pair<int, int> #define fs first #define sc second const ...
Contestant. Rank 1585. Rating +7. A. A-characteristic 题意 给定一个由 \(±1\) 组成的数组 \(a\)，定义特征 \(A\) 为数组 \(a\) 中满足 \(a \leq i < j \leq n\) 且 \(a_i \cdot a_j = 1\) 的个数。 给定个数，构造这个数组。 思路 直接暴力枚举 \(-1\) 的个数，因为可以无视顺序，我们直接在输出 \(-1\) 后剩下的全填上 \(1\) 即可。 因为 \((-1) \cdot (-1) = 1, 1 \cdot 1 = 1\)，所以我们不妨初始化 \(p\) 数组，其中 \(p_i = p_{i - 1} + i - 1\)，那么 \(p_i + p_{n - i} = k\) 时就找到了答案。 时间复杂度：\(O(n)\) 对应AC代码 #include <bits/stdc++.h> using namespace std; #define int long long #define pii pair ...