D. Same Count One(Polynomial Round 2022 (Div. 1 + Div. 2, Rated, Prizes!))
题意
给定 \(n\) 个长度为 \(m\) 的 01 序列,每次操作可以选择两个序列 a1 , a2 ,并选择一个 \(pos\) , std::swap(a1[pos], a2[pos]) , 求是每个序列中的 \(1\) 的个数都相等所需的最小操作数。
思路
可以发现 ( \(1\) 的总数 ) \(\bmod \ n \neq 0\) 时, 是无解的。
令 \(avg =\) ( \(1\) 的总数 ) \(/ n\) , 我们可以把这 \(n\) 个序列分为两类,严格小于 \(avg\) 的 和严格大于 \(avg\) 的,其他的序列可以丢掉。
严格大于 \(avg\) 的序列都可以为 严格小于 \(avg\) 的序列补充 \(1\) , 直到 严格大于 \(avg\) 的序列 \(1\) 的个数等于 \(avg\) 或者 严格小于 \(avg\) 的序列 \(1\) 个数等于 \(avg\) 。
直接模拟即可。
实现
void solve_problem() { int n, m; std::cin >> n >> m; std::vector a(n, std::vector<int>(m, 0)); int avg = 0; for (int i = 0;i < n; i++) { for (int j = 0; j < m; j++) { std::cin >> a[i][j]; avg += a[i][j]; } } if (avg % n == 0) { if (n == 1) { std::cout << 0 << "\n"; return; } avg /= n; std::vector<std::pair<int,int>> q1, q2; for (int i = 0; i < n; i++) { int cnt = 0; for (int j = 0; j < m; j++) { cnt += a[i][j]; } if(cnt < avg) q1.push_back({cnt, i}); else if (cnt > avg) q2.push_back({cnt, i}); } int ans1 = 0; std::vector<std::array<int, 3>> ans2; for (int i = 1; i <= n; i++) { if (q1.empty() || q2.empty()) break; auto [c1, i1] = q1[0]; auto [c2, i2] = q2[0]; int d = avg - c1; for (int j = 0; j < m; j++) { if (d == 0 || c2 == avg) { break; } if (a[i2][j] == 1 && a[i1][j] == 0) { std::swap(a[i2][j], a[i1][j]); c1++; c2--; d--; ans2.push_back({i2 + 1, i1 + 1, j + 1}); ans1++; } } q1[0] = {c1, i1}; q2[0] = {c2, i2}; if (c1 == avg) q1.erase(q1.begin()); if (c2 == avg) q2.erase(q2.begin()); } std::cout << ans1 << "\n"; for (auto [x, y, z] : ans2) { std::cout << std::max(x, y) << " " << std::min(y, x) << " " << z << "\n"; } } else { std::cout << -1 << "\n"; } }
D. Watch the Videos(2022-2023 ICPC, NERC, Southern and Volga Russian Regional Contest (Online Mirror, ICPC Rules, Preferably Teams))
题意
有 \(n\) 个大小随意的视频和 \(1\) 个大小为 \(m\) 的磁盘,视频要下载到磁盘中才可以开始观看,下载第 \(i\) 个视频花费 \(a_i\) 的时间,开始下载第 \(i\) 个视频时,磁盘中要至少有 \(a_i\) 的空间才可以开始,下载完成需要花费 \(1\) 的时间观看完,看完之后视频立刻被从磁盘中删除,求看完所有视频需要的时间。(一次只能下载一个视频,观看视频的时候可以开始下载视频)
思路
最坏的答案(每次看完一个视频后才开始下载下一个视频), 计算方法为:
\[ans = n + \sum_{i = 1}^n a_i \]
可以发现如果在观看视频时下载视频,答案就可以 \(-1\) 。
要想使答案最小,只需要尽可能多的在观看视频时开始下载视频即可。
假设视频序列 \(a\) 从小到大排序, 那么可以找到一个最大的 \(pos (1\leq pos \leq n)\) , 使得序列
\[[a_{pos},a_1,a_{pos-1},a_2,a_{pos-2},a_3,\cdots] \]
相邻两个数的和小于等于 \(m\) 。
按照这个序列观看,有 \(pos - 1\) 个视频是在正在观看视频时开始下载的。可以使答案减少 \(pos - 1\) 。
\(pos\) 是满足单调性的,因此可以二分来找到最大的 \(pos\) 。
实现
void solve_problem() { int n, m; std::cin >> n >> m; std::vector<int> a(n); for (auto &x : a) { std::cin >> x; } std::sort(a.begin(), a.end()); auto check = [&](int x) { int l = 0, r = x - 1; while (l < r) { if (a[r] > m - a[l]) return false; r--; l++; } return true; }; int l = 1, r = n, ans = 0; while (l <= r) { int mid = (l + r) >> 1; if (check(mid)) { ans = mid; l = mid + 1; } else { r = mid - 1; } } std::cout << std::accumulate(a.begin(), a.end(), 0LL) + (n - ans + 1) << "\n"; }
D. Range = √Sum(Codeforces Round #836 (Div. 2))
题意
构造一个长度为 \(n\) 的数组 \(a_1,a_2, a_3, \dots,a_n\) ,使 \(a_i\) 各不相同,且 \(max(a_1,a_2, a_3, \dots,a_n) - min(a_1,a_2, a_3, \dots,a_n) = \sqrt{a_1,a_2, a_3, \dots,a_n}\) 。
思路
当 \(n\) 为偶数时, 数组为:
\[\frac{n}{2},\frac{n}{2} + 1,\cdots ,n,n + 1,n + 2,n + \frac{n}{2}. \]
数组可以被分成 \(\frac{n}{2}\) 组,每组的和都为 \(2n\) 。
当 \(n\) 为奇数时,我们尝试 \(max(a) - max(b) = n + 1\) , 因此数组的和应为 \(n^2 + 2n + 1\) 。
尝试使用 \(n - 1\) 个数分为 \(\frac{n-1}{2}\) 组,每组和为 \(2(n+1)\) , 组成的数组和为 \(n^2 - 1\) 。
此时这 \(n - 1\) 个数为:
\[\frac{n - 1}{2} + 2,\frac{n - 1}{2} + 3,\cdots,\frac{n - 1}{2} + \frac{n - 1}{2},n + 2,n + 3,\cdots,n + \frac{n - 1}{2} + 1 \]
知道了最小项,最大项也可以计算出来 \(n + \frac{n - 1}{2} + 3\) 。
这时数组的和为:
\[n^2 - 1 + n + \frac{n - 1}{2} + 3 = n^2 + n + \frac{n - 1}{2} + 2 \]
距离 \(n^2 + 2n + 1\) 还需要:
\[\begin{aligned} (n^2 + 2n + 1) - (n^2 + n + \frac{n - 1}{2} + 2) &= n - \frac{n - 1}{2} - 1\\ &=\frac{2n - n + 1 - 2}{2}\\ &=\frac{n - 1}{2} \end{aligned} \]
我们可以让 第 \(\frac{n - 1}{2} + 1\) 项到第 \(n - 1\) 项都 \(+1\) 来抵消掉 \(\frac{n - 1}{2}\) 。
因为第 \(n - 1\) 项 \(n + \frac{n - 1}{2} + 1\) 与 第 \(n\) 项 \(n + \frac{n - 1}{2} + 3\) 相差 \(2\) ,所以 \(+1\) 操作不会使数组产生重复的数。
此时我们的数组已经构造完成:
\[\frac{n - 1}{2} + 2,\frac{n - 1}{2} + 3,\cdots,\frac{n - 1}{2} + \frac{n - 1}{2},n + 3,n + 4,\cdots,n + \frac{n - 1}{2} + 2,n + \frac{n - 1}{2} + 3 \]
实现
void solve_problem() { int n; std::cin >> n; if (n % 2 == 0) { for (int i = 0; i < n/2; i++) std::cout << (n/2 + i) << " "; for (int i = 1; i <= n/2; i++) std::cout << (n + i) << " "; std::cout << "\n"; } else { for (int i = 1; i <= (n - 1) / 2; i++) std::cout << (n - 1) / 2 + i + 1 << " "; for (int i = 1; i <= (n - 1) / 2; i++) std::cout << n + i + 2 << " "; std::cout << n + (n - 1) / 2 + 3<< "\n"; } }
查看更多关于CF构造题1600-1800(1)的详细内容...