A. Equal Occurrences
题意：求\(a\)的一个最长子序列，使得每个数出现的次数相同。
记录每个数出现的次数，排序后从小到大枚举出现次数，那么比它多的数都可以选。
点击查看代码
#include <bits/stdc++.h>using i64 = long long;void solve() {int n;std::cin >> n;std::vector<int> a(n);for (int i = 0; i < n; ++ i) {std::cin >> a[i];}std::vector<int> cnt(n + 1);for (auto & x : a) {++ cnt[x];}std::ranges::sort(cnt);int ans = 0;for (int i = 1; i <= n; ++ i) {ans = std::max(ans, cnt[i] * (n - i + 1));}std::cout << ans << "\n";
}int main() {std::ios::sync_with_stdio(false), std::cin.tie(0), std::cout.tie(0);int t = 1;std::cin >> t;while (t -- ) {solve();}return 0;
}
B. Merging the Sets
题意：若干个集合，你可以选择一些使得它们的并集里\([1, m]\)里的数都出现过。求有没有至少三种选法。
如果所有集合的并集都不行，则无解。
否则选择所有集合是一种选法，然后我们枚举集合，如果删掉这个集合还是合法的，就多一种选法。只需要记录每个数出现的次数就能判断。
点击查看代码
#include <bits/stdc++.h>using i64 = long long;void solve() {int n, m;std::cin >> n >> m;std::vector<int> cnt(m + 1);std::set<int> s;std::vector<std::vector<int>> a(n);for (int i = 0; i < n; ++ i) {int k;std::cin >> k;a[i].assign(k, 0);for (int j = 0; j < k; ++ j) {std::cin >> a[i][j];s.insert(a[i][j]);++ cnt[a[i][j]];}}if(s.size() < m) {std::cout << "NO\n";return;}int tot = 0;for (int i = 0; i < n; ++ i) {bool flag = true;for (auto & x : a[i]) {if ( -- cnt[x] <= 0) {flag = false;}}if (flag) {++ tot;}for (auto & x : a[i]) {++ cnt[x];}}if (tot >= 2) {std::cout << "YES\n";} else {std::cout << "NO\n";}
}int main() {std::ios::sync_with_stdio(false), std::cin.tie(0), std::cout.tie(0);int t = 1;std::cin >> t;while (t -- ) {solve();}return 0;
}
C. Wrong Binary Search
题意：一个二分查找代码，每次在\([l, r]\)里随机一个数\(m\)，如果\(p[m] == x\)返回\(m\)，p[m] < x\(则\)r = m - 1\(，否则\)l = m + 1$。构造一个排列，需要你有些数能正确找到有些不能。
如果一个数不能被正确找到，那么它前面或者后面肯定不是有序的。
那么对于\(s_i = 1\)的位置\(p_i = i\)。对于使得\(i \in [l, r]\)的\(s_i = 0\)的区间\([l, r]\)，从大到小填就行。\(l = r\)无解。
点击查看代码
#include <bits/stdc++.h>using i64 = long long;void solve() {int n;std::cin >> n;std::string s;std::cin >> s;std::vector<int> ans(n);for (int i = 0; i < n; ++ i) {if (s[i] == '1') {ans[i] = i;} else {int j = i;while (j + 1 < n && s[j + 1] == '0') {++ j;}if (i == j) {std::cout << "NO\n";return;}for (int k = i, x = j; k <= j; ++ k) {ans[k] = x -- ;}i = j;}}std::cout << "YES\n";for (int i = 0; i < n; ++ i) {std::cout << ans[i] + 1 << " \n"[i == n - 1];}
}int main() {std::ios::sync_with_stdio(false), std::cin.tie(0), std::cout.tie(0);int t = 1;std::cin >> t;while (t -- ) {solve();}return 0;
}
D1 && D2. Max Sum OR
题意：一个长度为\(n = r - l + 1\)的数组，\(a_i = i + l, i \in [1, n]\)，将它重新排列，使得\(\sum_{i=1}^{n} a_i | (i + l)\)最大，其\(|\)是位运算或。
用\(01trie\)存\([l, r]\)的每一个数，然后贪心查询每个数在剩下的数里和它或起来最大的数。如果两个数互相和对方或起来最大，就让他们匹配，然后把这两个数从字典树里删掉。一直到匹配完就行。不会证明，赛时猜的。
点击查看代码
#include <bits/stdc++.h>using i64 = long long;const int N = 2e5 + 5;int Tr[N * 30][2], cnt[N * 30];
struct Trie {int idx;Trie() {idx = 0;Tr[0][0] = Tr[0][1] = 0;cnt[idx] = 0;}int new_node() {++ idx;Tr[idx][0] = Tr[idx][1] = 0;cnt[idx] = 0;return idx;}void insert(i64 x) {int p = 0;for (i64 i = 29; i >= 0; -- i) {i64 s = x >> i & 1;if (!Tr[p][s]) { Tr[p][s] = new_node();}p = Tr[p][s];++ cnt[p];}}i64 query(i64 x) {i64 res = 0;int p = 0;for (i64 i = 29; i >= 0; -- i) {i64 s = x >> i & 1;if (s == 0) {if (Tr[p][1] && cnt[Tr[p][1]]) {res += 1ll << i;p = Tr[p][1];} else {p = Tr[p][0];}} else {if (Tr[p][0] && cnt[Tr[p][0]]) {p = Tr[p][0];} else {res += 1ll << i;p = Tr[p][1];}}}return res;}void del(i64 x) {int p = 0;for (i64 i = 29; i >= 0; -- i) {i64 s = x >> i & 1;p = Tr[p][s];-- cnt[p];}}
};void solve() {i64 l, r;std::cin >> l >> r;int n = r - l + 1;i64 ans = 0;Trie tr;for (i64 i = l; i <= r; ++ i) {tr.insert(i);}std::vector<i64> a(n + 1, -1);while (1) {std::vector<i64> p(n + 1, -1);bool flag = false;for (i64 i = l; i <= r; ++ i) {if (a[i - l] == -1) {p[i - l] = tr.query(i);flag = true;}}if (!flag) {break;}for (i64 i = l; i <= r; ++ i) {if (p[i - l] == -1) {continue;}if (i == p[p[i - l] - l]) {a[i - l] = p[i - l];tr.del(i);}}}for (i64 i = l; i <= r; ++ i) {ans += a[i - l] | i;}std::cout << ans << "\n";for (i64 i = l; i <= r; ++ i) {std::cout << a[i - l] << " \n"[i == r];}
}int main() {std::ios::sync_with_stdio(false), std::cin.tie(0), std::cout.tie(0);int t = 1;std::cin >> t;while (t -- ) {solve();}return 0;
}