Div. 1 + Div. 2, Rated, Prizes! CodeTON Round 3 A-D _生活百科

比赛链接
A题解知识点：贪心。
注意到 \(a[1] \neq 1\)，\(1\) 永远不可能换到前面；\(a[1] = 1\) 可以交换后面任意元素。
时间复杂度 \(O(n)\)
空间复杂度 \(O(n)\)
代码#include <bits/stdc++.h>#define ll long longusing namespace std;int a[20];bool solve() {int n;cin >> n;for (int i = 1;i <= n;i++) cin >> a[i];if (a[1] == 1) cout << "YES" << '\n';else cout << "NO" << '\n';return true;}int main() {std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);int t = 1;cin >> t;while (t--) {if (!solve()) cout << -1 << '\n';}return 0;}B题解知识点：贪心，枚举。
分两类，一种是纯 \(1\) 或 \(0\)，另一种是杂合。
显然后者的情况中，把所有数字全选了是最优的；前者枚举一下所有纯子串即可。两种情况，取最大值。
时间复杂度 \(O(n)\)
空间复杂度 \(O(n)\)
代码#include <bits/stdc++.h>#define ll long longusing namespace std;bool solve() {int n;cin >> n;string s;cin >> s;s = "?" + s;int cnt0 = 0, cnt1 = 0;for (int i = 1;i <= n;i++) {if (s[i] == '0') cnt0++;else cnt1++;}ll mx = 1LL * cnt0 * cnt1;int i = 1, j = 1;while (i <= n) {while (j <= n && s[j] == s[i]) j++;mx = max(mx, 1LL * (j - i) * (j - i));i = j;}cout << mx << '\n';return true;}int main() {std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);int t = 1;cin >> t;while (t--) {if (!solve()) cout << -1 << '\n';}return 0;}C题解知识点：构造。
注意到，只有 \(a=b\) 或者 \(a\) 每位都不等于 \(b\) 的对应位才可行。
考虑先把 \(a\) 串的 \(1\) 一个一个消掉，然后发现 \(b\) 会出现全 \(0\) 全 \(1\) 的情况，接下来分类讨论：

如果 \(a = b\)，那么 \(a\) 中 \(1\) 为偶数时得到的 \(b\) 是 \(0\)，否则是 \(1\)。
如果 \(a\) 每位都不等于 \(b\) 的对应位，那么消掉一个 \(1\) 以后又会回到情况1，因此和情况 \(1\) 相反。

全是 \(0\) 直接可以结束，全是 \(1\) 可以先把 \([1,n]\) 取反，然后选择 \([1,1],[2,n]\) 即可。
时间复杂度 \(O(n)\)
空间复杂度 \(O(n)\)
代码

#include <bits/stdc++.h>#define ll long longusing namespace std;bool solve() {int n;cin >> n;string a, b;cin >> a >> b;a = "?" + a;b = "?" + b;int cnt = 0;for (int i = 1;i <= n;i++) cnt += a[i] == b[i];if (cnt != 0 && cnt != n) return 0;bool flag = cnt == n ? 0 : 1;vector<pair<int, int>> ans;for (int i = 1;i <= n;i++) {if (a[i] == '1') {ans.push_back({ i, i });flag ^= 1;}}if (flag) {ans.push_back({ 1,n });ans.push_back({ 1,1 });ans.push_back({ 2,n });}cout << "YES" << '\n';cout << ans.size() << '\n';for (auto [i, j] : ans) cout << i << ' ' << j << '\n';return true;}int main() {std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);int t = 1;cin >> t;while (t--) {if (!solve()) cout << "NO" << '\n';}return 0;}

D题解知识点：质因数分解，容斥原理，数论。
题目要求我们每个 \(b_i\) 的方案数，然后得到总的方案数。
显然有 \(gcd(a_{i-1},b_i) = a_i\)，注意到 \(a_i\) 必须是 \(a_{i-1}\) 的因子否则不可能得到答案，因此特判一下 \(a_{i} | a_{i-1}\)。
于是，我们要找到所有的 \(b_i\)，满足 \(gcd(\frac{a_{i-1}}{a_i},\frac{b_i}{a_i}) = 1\) 且 \(a_i | b_i\)，其中 \(\frac{b_i}{a_i} \in [1,\frac{m}{a_i}]\)，即我们从 \([1,\frac{m}{a_i}]\) 整数中找到和 \(\frac{a_{i-1}}{a_i}\) 互素的个数。
这是一个典型的容斥问题。先对 \(\frac{a_{i-1}}{a_i}\) 分解素因数，得到其素因子种类。我们先计算出区间中包含 \(\frac{a_{i-1}}{a_i}\) 因子的数的个数，注意奇加偶减，然后用总数 \(\frac{m}{a_i}\) 减去个数，即与之互素的数的个数，于是我们就得到了 \(b_i\) 的种类。