当前位置: 首页 > news >正文

Codeforces Round 1052 (Div. 2)


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;
}
http://www.hskmm.com/?act=detail&tid=12673

相关文章:

  • uboot启动流程
  • 内存泄漏
  • Context Engineering
  • ios在wifi模式下设置http代理
  • 面试官问:请画出 MySQL 架构图!这种变态问题都能问的出来
  • 基于协方差交叉(CI)的多传感器融合算法matlab仿真,对比单传感器和SCC融合
  • github/网盘/公众号信息收集
  • AtCoder Regular Contest 206 (Div. 2) 部分题解
  • Grafana 和 Openssh 高危漏洞修复
  • 基于双PI控制器和三电平SVPWM交流同步直线电机矢量控制系统的simulink建模与仿真
  • 学习日报(补发)
  • Influxdb 得模糊查询总结
  • 多表关系和多表查询
  • 6
  • 【反比例函数】【做题笔记】【图形存在性】题目合集
  • 20250920 嘉定江桥---江苏吴江区太湖 往返160KM骑行小记
  • 工作队列(Work Queues)与消息确认(Ack)
  • React18新增的hook useId
  • 十年架构演进史:从臃肿war包到云原生,我们终于解放了!
  • week1作业
  • 6-5 汇聚层
  • 从IpadOS 26 Beta版切换成IpadOS 26 正式版
  • 2025.9.21总结
  • 6-4 多输入多输出通道
  • 6-6 卷积神经网络LeNet
  • 5-5读写文件
  • 6-2图像卷积
  • 二叉树的高度和判断平衡二叉树
  • 20250921 之所思 - 人生如梦
  • UE5 Cook数据结构