失败不可避免，唯有继续努力。这本来是一场普通的 div3，本来应该是上分的好机会，至少也是信心场。虽然上不了打分，但是至少分数也不会变化太多。但是我显然高估了我自己的能力。
A
一道模拟题，非常简单。当我看到这道题目时，我只觉得这是一场非常普通的 div3 的模拟题。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 |
#include <bits/stdc++.h> void solve() { int n, m; std::cin >> n >> m; std::string s; std::cin >> s; std::string t = "ABCDEFG"; std::map<char, int> cnt; for (auto ch : s) { cnt[ch] ++; } int res = 0; for (auto ch : t) { if (cnt[ch] >= m) continue; res += m - cnt[ch]; } std::cout << res << '\n'; } int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); std::cout.tie(nullptr); int T; std::cin >> T; while (T --) { solve(); } } |
B
二分查找数的范围，也很简单，只是需要加一点讨论。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 |
#include <bits/stdc++.h> void solve() { int n, f, k; std::cin >> n >> f >> k; std::vector<int> a(n + 1); for (int i = 1; i <= n; ++ i) { std::cin >> a[i]; } int val = a[f]; std::sort(a.begin() + 1, a.end(), std::greater<int>()); int l = std::lower_bound(a.begin() + 1, a.end(), val, std::greater<int>()) - a.begin(); int r = std::upper_bound(a.begin() + 1, a.end(), val, std::greater<int>()) - a.begin() - 1; // [l, r] [1, k] if (k >= r || (k == l && k == r)) { std::cout << "YES\n"; } else if (k < l) { std::cout << "NO\n"; } else { std::cout << "MAYBE\n"; } } int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); std::cout.tie(nullptr); int T; std::cin >> T; while (T --) { solve(); } } |
C
这题开始不对劲了，至少我觉得这是一道大模拟，但是调试了 2 个小时才过的这道题，其中直接重构了四五次代码。
第一次的代码没有考虑到要按照给的顺序做，WA。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 |
#include <bits/stdc++.h> bool solve() { int n; std::cin >> n; std::vector<int> a(n + 1), b(n + 1); std::map<int, int> cnt2, uniqueB; for (int i = 1; i <= n; ++ i) { std::cin >> a[i]; } for (int i = 1; i <= n; ++ i) { std::cin >> b[i]; cnt2[b[i]] ++; if (a[i] != b[i]) uniqueB[b[i]] ++; } int m; std::cin >> m; std::vector<int> d(m + 1); std::map<int, int> cnt3; for (int i = 1; i <= m; ++ i) { std::cin >> d[i]; cnt3[d[i]] ++; } for (auto [val, cnt] : uniqueB) { if (cnt > cnt3[val]) return false; cnt3[val] -= cnt; if (cnt3[val] == 0) cnt3.erase(val); } for (auto [val, cnt] : cnt3) { if (cnt2[val]) return true; } return false; } int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); std::cout.tie(nullptr); int T; std::cin >> T; while (T --) { std::cout << (solve() ? "YES" : "NO") << '\n'; } } |
第二次，改了一下代码把操作序列构造出来，但是这个构造不是最优所以 WA 了。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 |
#include <bits/stdc++.h> using PII = std::pair<int, int>; bool solve() { int n; std::cin >> n; std::vector<int> a(n + 1), b(n + 1); std::map<int, std::vector<int>> cntUnique2; std::map<int, int> pos; for (int i = 1; i <= n; ++ i) { std::cin >> a[i]; } for (int i = 1; i <= n; ++ i) { std::cin >> b[i]; pos[b[i]] = i; if (a[i] != b[i]) { cntUnique2[b[i]].push_back(i); } } int m; std::cin >> m; std::vector<int> d(m + 1); std::map<int, std::vector<int>> cnt3; for (int i = 1; i <= m; ++ i) { std::cin >> d[i]; cnt3[d[i]].push_back(i); } bool flag1 = false; for (auto &[val, cnt] : cntUnique2) { if (not cnt3.count(val)) { return false; } if (cnt.size() > cnt3[val].size()) { return false; } flag1 = true; } int flag2 = -1; for (auto &[val, cnt] : cnt3) { if (cntUnique2.count(val) and cnt.size() == cntUnique2[val].size()) continue; if (pos.count(val)) { flag2 = val; break; } } if (not flag1 and flag2 == -1) { return false; } std::vector<PII> op(n + 1, {-1, -1}); auto update = [&](int x, PII y) { if (op[x].first == -1) { op[x] = y; return; } if (y.second > op[x].second) { op[x] = y; } }; // 最后一个将数字改为 val // 非法数字都在 pos of val 上操作 int posVal = flag1 ? cntUnique2.begin()->second.back() : pos[flag2]; for (auto &[val, cnt]: cnt3) { int times = cnt.size() - cntUnique2[val].size(); for (int i = 0; i < times; ++ i) { update(posVal, {val, cnt.back()}); cnt.pop_back(); } } if (not flag1) { if (op[posVal].first != b[posVal]) { cntUnique2[b[posVal]].push_back(posVal); } } for (auto &[val, cnt] : cntUnique2) { auto &toPos = cnt3[val]; if (cnt.size() > toPos.size()) { return false; } for (int i = 0; i < cnt.size(); ++ i) { update(cnt[i], {val, toPos[i]}); } if (cnt.empty()) continue; int backPos = cnt.back(); for (int i = cnt.size(); i < toPos.size(); ++ i) { update(backPos, {val, toPos[i]}); } } for (int i = 1; i <= n; ++ i) { if (op[i].first != -1) { a[i] = op[i].first; } if (a[i] != b[i]) { return false; } } return true; } int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); std::cout.tie(nullptr); int T; std::cin >> T; while (T --) { std::cout << (solve() ? "YES" : "NO") << '\n'; } } |
然后调细节一直调到一点半才把正解调出来。简单说一下我的思路：从后向前做，如果可以把非法的部分变为合法的，那么直接操作；如果不行，在合法的部分中找到不影响的部分；如果找不到就在上一次操作的位置做，因为从后向前做的时候那个值已经固定了，所以可以这么操作。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 |
#include <bits/stdc++.h> using PII = std::pair<int, int>; bool solve() { int n; std::cin >> n; std::vector<int> a(n + 1), b(n + 1); std::map<int, std::vector<int>> idxUnique2, idxSame2; for (int i = 1; i <= n; ++ i) { std::cin >> a[i]; } for (int i = 1; i <= n; ++ i) { std::cin >> b[i]; if (a[i] != b[i]) { idxUnique2[b[i]].push_back(i); } else { idxSame2[b[i]].push_back(i); } } int m; std::cin >> m; std::vector<int> d(m + 1); for (int i = 1; i <= m; ++ i) { std::cin >> d[i]; } auto changeUnique = [&](int x) -> int { auto &vec = idxUnique2[x]; int idx = vec.back(); vec.pop_back(); if (vec.empty()) { idxUnique2.erase(x); } if (x != b[idx]) idxUnique2[x].push_back(idx); else idxSame2[x].push_back(idx); return idx; }; auto changeSame = [&](int x) -> int { auto &vec = idxSame2[x]; int idx = vec.back(); vec.pop_back(); if (vec.empty()) { idxSame2.erase(x); } if (x != b[idx]) idxUnique2[x].push_back(idx); else idxSame2[x].push_back(idx); return idx; }; std::vector<int> vis(n + 1, -1); for (int i = m, last = -1; i; -- i) { int now = d[i]; if (idxUnique2.count(now)) { last = changeUnique(now); vis[last] = now; } else if (idxSame2.count(now)) { last = changeSame(now); vis[last] = now; } else if (last == -1) { return false; } } for (int i = 1; i <= n; ++ i) { if (vis[i] != -1) { a[i] = vis[i]; } if (a[i] != b[i]) { return false; } } return true; } int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); std::cout.tie(nullptr); int T; std::cin >> T; while (T --) { std::cout << (solve() ? "YES" : "NO") << '\n'; } } |
这题整整卡了我 2h 导致我这场 div3 只做了 2 题，又掉回绿名。但是这道题只有 1200 分，所以我需要拉响警钟，唯有努力。
D
模拟题，但是细节不少。枚举分割点：如果分割点在边界，那么就直接在原数组上检查有序性；如果在中间，则从两端向中间找到最大的有序部分，如果两个有序部分距离太远，那么非法，反之枚举所有可能的分界点，就可以得到答案。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 |
#include <bits/stdc++.h> int gcd(int a, int b) { return b ? gcd(b, a % b) : a; } void solve() { int n; std::cin >> n; std::vector<int> a(n + 1); for (int i = 1; i <= n; ++ i) std::cin >> a[i]; std::vector<int> b(n); // b[i] = gcd(a[i], a[i + 1]) // c[i] = gcd(a[i], a[i + 2]) for (int i = 1; i < n; ++ i) b[i] = gcd(a[i], a[i + 1]); if (std::is_sorted(b.begin() + 2, b.end()) or std::is_sorted(b.begin() + 1, b.end() - 1) ) { std::cout << "YES\n"; return; } // b[1,..,x-1] c[x] b[x+2,..,n-1] remove a[i+1] i\in[2,n-3] // remove a[1] => b[2,..,n-1] // remove a[n] => b[1,..,n-2] int l = 1, r = n - 1; while (l < b.size() and b[l + 1] >= b[l]) ++ l; while (r > 1 and b[r] >= b[r - 1]) -- r; if (r - 3 > l) { std::cout << "NO\n"; return; } // b[1,..,l] b[l]=gcd(a[l],a[l+1]) l+3=r // c[l+1] = gcd(a[l+1],a[l+3]) // b[r,..,n-1] b[r]=gcd(a[r],a[r+1]) auto check = [&](int l, int r) -> bool { if (r - l != 3) return false; int val = gcd(a[l + 1], a[l + 3]); if (l and b[l] > val) return false; if (r < n and val > b[r]) return false; std::cout << "YES\n"; return true; }; for (int i = std::max(0, r - 3); i <= l; ++ i) { if (check(i, std::min(i + 3, n))) return; } std::cout << "NO\n"; } int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); std::cout.tie(nullptr); int T; std::cin >> T; while (T --) { solve(); } } |
E
矩阵变换。用到一个线性代数中非常基本的结论。假设操作的过程为：
$$
P_nP_{n-1}\dots P_1AQ_1Q_2\dots Q_m=B
$$
其中 P、Q 都是初等行列交换。我们需要的做的就是找到一组 P、Q 满足上面的式子。实际上这等价于先做所有的行变换，在做所有的列变换，这由矩阵乘法的结合率可知。所以我们直接先把行按贪心做变换，再按照列贪心变换，如果合法，那么就可以构造出答案。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 |
#include <bits/stdc++.h> bool solve() { int n, m; std::cin >> n >> m; std::vector<std::vector<int>> a(n + 1, std::vector<int>(m + 1, 0)), b(n + 1, std::vector<int>(m + 1, 0)); std::vector<int> row(n * m + 1), col(n * m + 1); for (int i = 1; i <= n; ++ i) { for (int j = 1; j <= m; ++ j) { std::cin >> a[i][j]; row[a[i][j]] = i; col[a[i][j]] = j; } } for (int i = 1; i <= n; ++ i) { for (int j = 1; j <= m; ++ j) { std::cin >> b[i][j]; } } for (int i = 1; i <= n; ++ i) { int r = row[b[i][1]]; // 把b[i]行对应的a[r]行找出来 交换到对应b的位置也就是i行 std::swap(a[i], a[r]); // 交换之后列不变 维护行的对应关系 for (int j = 1; j <= m; ++ j) { row[a[i][j]] = i; row[a[r][j]] = r; } } for (int j = 1; j <= m; ++ j) { int c = col[b[1][j]]; // 把b[1]列对应的a[1]列找出来 交换到对应b的位置也就是j列 for (int i = 1; i <= n; ++ i) { std::swap(a[i][j], a[i][c]); // 交换之后行不变 维护列的对应关系 col[a[i][j]] = j; col[a[i][c]] = c; } } return a == b; } int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); std::cout.tie(nullptr); int T; std::cin >> T; while (T --) { std::cout << (solve() ? "YES" : "NO") << '\n'; } } |
以上，继续加训。
发表回复