1.小美的平衡矩阵
二维前缀和。
二维前缀和维护 \(1\) 的个数，枚举长度，然后 \(n^2\) 查找即可，复杂度 \(O(n^3)\)。
点击查看代码
#include <bits/stdc++.h>int main(){int n;std::cin >> n;std::vector<std::string> s(n);for(int i = 0;i < n;i += 1){std::cin >> s[i];}std::vector<std::vector<int>> sum(n + 1, std::vector<int>(n + 1));for(int i = 0;i < n;i += 1){for(int j = 0;j < n;j += 1){sum[i + 1][j + 1] += sum[i + 1][j] + sum[i][j + 1] - sum[i][j];sum[i + 1][j + 1] += s[i][j] == '1';}}auto get = [&](int l1, int r1, int l2, int r2)->int{return sum[l2][r2] - sum[l1 - 1][r2] - sum[l2][r1 - 1] + sum[l1 - 1][r1 - 1];};auto work = [&](int x)->int{int res = 0;for(int i = 1;i <= n;i += 1){for(int j = 1;j <= n;j += 1){if(i + x - 1 <= n && j + x - 1 <= n && get(i, j, i + x - 1, j + x - 1) == x * x / 2){res += 1;}}}return res;};for(int i = 1;i <= n;i += 1){if(i & 1){std::cout << 0 << "\n";}else{std::cout << work(i) << "\n";}}
}
2.小美的数组询问
模拟。
求一下和，然后看 \(0\) 的个数即可。
点击查看代码
#include <bits/stdc++.h>using i64 = long long;int main() {int n, m;std::cin >> n >> m;i64 ans = 0, cnt = 0;for(int i = 0;i < n;i += 1){int x;std::cin >> x;ans += x;cnt += x == 0;}while(m--){int l, r;std::cin >> l >> r;std::cout << ans + l * cnt << " " << ans + r * cnt << "\n";}
}
3.小美的 MT
模拟。
点击查看代码
#include <bits/stdc++.h>using i64 = long long;int main() {int n, m;std::cin >> n >> m;std::string s;std::cin >> s;int ans = 0;for(int i = 0;i < n;i += 1){ans += s[i] == 'M' || s[i] == 'T' || m-- > 0;}std::cout << ans << "\n";
}
4.小美的朋友关系
并查集。
正着是删边，反过来就是加边了，所以先判断哪些边是会在询问里删掉的，剩下的边连起来，然后反过来枚举询问，注意一条边可能会被多次删除，只有从后向前枚举到最后一次被删除的时候才可以把这条边加进去，然后 \(n\) 有 \(1\times 10^9\)，需要离散下，复杂度 \(O(\alpha (n)nlog n)\)。
点击查看代码
#include <bits/stdc++.h>using i64 = long long;int main() {int n, m, q;std::cin >> n >> m >> q;std::vector<int> fa(2 * m);std::iota(fa.begin(), fa.end(), 0);auto find = [&](auto&& self, int x)->int{return x == fa[x] ? x : fa[x] = self(self, fa[x]);};int cnt = 0;std::map<std::array<int, 2>, int> mp;std::map<int, int> id;for (int i = 0; i < m; i += 1) {int u, v;std::cin >> u >> v;if (u > v) std::swap(u, v);mp[ {u, v}] += 1;if (!id.count(u)) {id[u] = cnt ++;}if (!id.count(v)) {id[v] = cnt ++;}}std::vector<std::array<int, 3>> Q(q);for (auto &[op, u, v] : Q) {std::cin >> op >> u >> v;if (op == 1 && id.count(u) && id.count(v)) {int x = u, y = v;if (x > y) std::swap(x, y);mp[ {x, y}] -= 1;}}for (auto &[uv, f] : mp) {auto [u, v] = uv;if (f > 0) {u = find(find, id[u]), v = find(find, id[v]);fa[u] = v;}}std::vector<bool> ans(q);for (int i = q - 1; i >= 0; i -= 1) {auto [op, u, v] = Q[i];if (!id.count(u) || !id.count(v)) continue;if (op == 2) {u = find(find, id[u]), v = find(find, id[v]);ans[i] = u == v;} else {if (u > v) std::swap(u, v);if (mp.count({u, v})) {mp[ {u, v}] += 1;if (mp[ {u, v}] > 0) {u = find(find, id[u]), v = find(find, id[v]);fa[u] = v;}}}}for (int i = 0; i < q; i += 1) {if (Q[i][0] == 2) {std::cout << (ans[i] ? "Yes" : "No") << "\n";}}}
5.小美的区间删除
二分。
看末尾乘积 \(0\) 的个数，只需要看剩下的数字中因子 \(2\) 和 \(5\) 的最小值即可，因此可以前后缀和处理一下，然后枚举 \(l\)，二分 \(r\) 去找删除该区间后满足要求的最大长度，那么该长度内都可以作为答案。
点击查看代码
#include <bits/stdc++.h>using i64 = long long;int main() {int n, k;std::cin >> n >> k;std::vector<int> a(n);std::vector<std::array<int, 2>> pre(n + 1), suf(n + 1);for (int i = 0; i < n; i += 1) {std::cin >> a[i];pre[i + 1] = pre[i];int x = a[i];while (x % 2 == 0) {x /= 2;pre[i + 1][0] += 1;}while (x % 5 == 0) {x /= 5;pre[i + 1][1] += 1;}}for (int i = n - 1; i >= 0; i -= 1) {int x = a[i];while (x % 2 == 0) {x /= 2, suf[i + 1][0] += 1;}while (x % 5 == 0) {x /= 5, suf[i + 1][1] += 1;}suf[i] = suf[i + 1];}i64 ans = 0;for (int i = 1; i <= n; i += 1) {int lo = i - 1, hi = n;while (lo < hi) {int mid = lo + hi + 1 >> 1;std::array<int, 2> res{0, 0};if (i >= 1) {res = pre[i - 1];}if (mid + 1 <= n) {res[0] += suf[mid + 1][0];res[1] += suf[mid + 1][1];}if (std::min(res[0], res[1]) >= k) {lo = mid;} else {hi = mid - 1;}}if (lo >= i) {ans += lo - i + 1;}}std::cout << ans << "\n";return 0;
}