浙江龙网

  1. 首页 > 生活百科 > >

Div. 2 Codeforces Round #829 A-E

生活百科

比赛链接
A题解知识点：枚举 。
只要一个Q后面有一个A对应即可，从后往前遍历，记录A的数量，遇到Q则数量减一，如果某次Q计数为0则NO 。
时间复杂度 \(O(n)\)
空间复杂度 \(O(1)\)
代码#include <bits/stdc++.h>#define ll long longusing namespace std;bool solve() {int n;cin >> n;string s;cin >> s;s = "?" + s;int cnt = 0;for (int i = n;i >= 1;i--) {if (s[i] == 'Q') {if (cnt == 0) return false;cnt--;}else cnt++;}cout << "YES" << '\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;}B题解知识点：构造 。
可以证明 \(\lfloor \frac{n}{2} \rfloor\) 是最优答案 。交错构造，\(i+\lfloor \frac{n}{2} \rfloor\) 和 \(i\) ， 注意 \(i\) 从 \(1\) 到 \(\lfloor \frac{n}{2} \rfloor\) ，在最后如果 \(n\) 是奇数则补一个 \(n\)。
【Div. 2 Codeforces Round #829A-E】时间复杂度 \(O(n)\)
空间复杂度 \(O(1)\)
代码#include <bits/stdc++.h>#define ll long longusing namespace std;bool solve() {int n;cin >> n;for (int i = 1;i <= n / 2;i++) {cout << i + n / 2 << ' ' << i << ' ';}if (n & 1) cout << n << ' ';cout << '\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题解知识点：构造 。
可以两两构造 。找到一对非 \(0\) 数 \(a[i],a[j]\) ，当 \(a[i] = a[j]\)，如果 \(i,j\) 奇偶性相同则 \([i,i],[i+1,j]\)，否则分段 \([i,j]\) ；当 \(a[i] \neq a[j]\) ，如果 \(i,j\) 奇偶性相同则 \([i,j]\) ，否则 \([i,i],[i+1,j]\)。
注意两对之间以及首尾可能会存在空隙，最后要把上面答案遍历一遍 ， 填补空隙 。
时间复杂度 \(O(n)\)
空间复杂度 \(O(n)\)
代码#include <bits/stdc++.h>#define ll long longusing namespace std;int a[200007];bool solve() {int n;cin >> n;vector<int> pos;for (int i = 1;i <= n;i++) cin >> a[i];for (int i = 1;i <= n;i++) {if (a[i]) pos.push_back(i);}if (pos.size() & 1) return false;if (!pos.size()) {cout << 1 << '\n';cout << 1 << ' ' << n << '\n';return true;}vector<pair<int, int>> v;for (int i = 0;i < pos.size();i += 2) {if (a[pos[i]] == a[pos[i + 1]]) {if ((pos[i] & 1) == (pos[i + 1] & 1)) {v.push_back({ pos[i], pos[i] });v.push_back({ pos[i] + 1,pos[i + 1] });}else v.push_back({ pos[i],pos[i + 1] });}else {if ((pos[i] & 1) != (pos[i + 1] & 1)) {v.push_back({ pos[i], pos[i] });v.push_back({ pos[i] + 1,pos[i + 1] });}else v.push_back({ pos[i],pos[i + 1] });}}vector<pair<int, int>> ans;int prer = 0;for (auto [i, j] : v) {if (i != prer + 1) ans.push_back({ prer + 1, i - 1 });ans.push_back({ i,j });prer = j;}if (ans.back().second != n) ans.push_back({ ans.back().second + 1,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 << -1 << '\n';}return 0;}D题解知识点：数论 ， 贪心 。
记录每个数字出现的次数，尝试从小到大合成出 \(x\)。从 \(1\) 开始往后遍历，每次将 \(i\) 合成 \(i+1\) ，显然 \(i+1\) 个 \(i\) 将产生 \(1\) 个 \(i+1\)。如果出现非 \(x\) 的数 \(i\) 不能全部使用，那么整个式子就无法被 \(x!\) 整除 。
时间复杂度 \(O(n)\)
空间复杂度 \(O(1)\)
代码#include <bits/stdc++.h>using namespace std;int cnt[500007];int main() {std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);int n, x;cin >> n >> x;for (int i = 1;i <= n;i++) {int tmp;cin >> tmp;cnt[tmp]++;}for (int i = 1;i < x;i++) {if (cnt[i] % (i + 1)) {cout << "NO" << '\n';return 0;}cnt[i + 1] += cnt[i] / (i + 1);}cout << "YES" << '\n';return 0;}E题解知识点：概率dp 。
设 \(f[i]\) 代表将 \(i\) 个还没排好的 \(1\) （如 1100101 有 \(2\) 个 \(1\) 没排好）排好的期望步数 。
对于 \(f[i]\) ，下一步排好一个 \(1\) （即到达 \(i-1\) 状态）的概率是 \(\dfrac{i^2}{C_n^2}\)，下一步啥都没变的概率就是 \(1-\dfrac{i^2}{C_n^2}\)，于是有：
\[\begin{aligned} f[i] &= (f[i-1]+1) \cdot \dfrac{i^2}{C_n^2} + (f[i]+1) \cdot (1-\dfrac{i^2}{C_n^2})\\ \dfrac{i^2}{C_n^2} \cdot f[i] &= \dfrac{i^2}{C_n^2} \cdot f[i-1] + 1\\ f[i] &= f[i-1] + \dfrac{C_n^2}{i^2}\end{aligned}\]即一步到达 \(i-1\) 后再排完的期望乘这步的概率加一步啥也没干的期望乘这步的概率就是 \(f[i]\)。

推荐阅读


上一篇：四 Selenium4.0+Python3系列 - 常见元素操作（含鼠标键盘事件）

下一篇：DevOps | 如何快速提升团队软件开发成熟度，快速提升研发效能？