最近事情太多有点累了，没发博客，现在补上。
CF-round951(Div. 2)
真红温这场。
A
简单贪心，但是赛后看到有人写暴力被×了。
|
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 |
#include <bits/stdc++.h> void solve() { int n; std::cin >> n; std::vector<int> a(n + 1); for (int i = 1; i <= n; ++ i) std::cin >> a[i]; int res = 1e9; for (int i = 1; i < n; ++ i) { int mx = std::max(a[i], a[i + 1]); res = std::min(res, mx - 1); } 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
真红，这道题，找规律找了 70 分钟。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
316560849 14570961 316560848 316560851 316560850 316560853 316560852 316560855 316560854 316560857 316560856 316560859 316560858 316560861 316560860 316560863 316560862 316560833 316560832 316560835 316560834 316560837 316560836 316560839 316560838 316560841 316560840 316560843 316560842 316560845 316560844 316560847 316560846 316560881 316560880 316560883 316560882 316560885 316560884 316560887 316560886 316560889 14570960 14570963 14570962 14570965 14570964 14570967 14570966 14570969 14570968 14570971 14570970 14570973 14570972 14570975 14570974 14570945 14570944 14570947 14570946 14570949 14570948 14570951 14570950 14570953 14570952 14570955 14570954 14570957 14570956 14570959 14570958 14570993 14570992 14570995 14570994 14570997 14570996 14570999 14570998 14571001 -1 2 1 4 3 6 5 8 7 10 9 12 11 14 13 -16 -17 -14 -15 -12 -13 -10 -11 -8 -9 -6 -7 -4 -5 -2 -3 32 31 34 33 36 35 38 37 40 -1 2 1 4 3 6 5 8 7 10 9 12 11 14 13 -16 -17 -14 -15 -12 -13 -10 -11 -8 -9 -6 -7 -4 -5 -2 -3 32 31 34 33 36 35 38 37 40 0 1 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 0 3 2 5 4 7 6 9 8 11 10 13 12 15 14 17 16 19 18 21 20 23 22 25 24 27 26 29 28 31 30 33 32 35 34 37 36 39 38 41 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 -1 2 1 4 3 6 5 8 7 10 9 12 11 14 13 16 15 18 17 20 19 22 21 24 23 26 25 28 27 30 29 32 31 34 33 36 35 38 37 40 12 4 13 14 15 8 9 10 11 4 5 6 7 0 1 2 3 28 29 30 31 24 25 26 27 20 21 22 23 16 17 18 19 44 45 46 47 40 41 42 43 36 5 6 7 0 1 2 3 12 13 14 15 8 9 10 11 20 21 22 23 16 17 18 19 28 29 30 31 24 25 26 27 36 37 38 39 32 33 34 35 44 1 2 3 -4 -3 -2 -1 -8 -7 -6 -5 -12 -11 -10 -9 16 17 18 19 12 13 14 15 8 9 10 11 4 5 6 7 32 33 34 35 28 29 30 31 24 1 2 3 -4 -3 -2 -1 8 9 10 11 4 5 6 7 16 17 18 19 12 13 14 15 24 25 26 27 20 21 22 23 32 33 34 35 28 29 30 31 40 |
当时打完表对着这个文本发呆了好久。赛后看了 qfl 佬的视频才想明白。
|
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> using LL = long long; void solve() { int x, y; std::cin >> x >> y; std::function<bool(int)> check = [&](int mid) { if (mid <= 0) return mid == 0; int d1 = (mid ^ x) - x; int d2 = (mid ^ y) - y; return d1 == d2 and check(mid >> 1); }; int l = 0, r = std::max(x, y); while (l < r) { int mid = (LL)l + r + 1 >> 1; if (check(mid)) l = mid; else r = mid - 1; } std::cout << l + 1 << '\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
写了一个莫名其妙的二分答案过了。
|
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> using LL = long long; 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> ans; auto check = [&](LL sum) -> bool { std::vector<int> tmp(n + 1); LL now_sum = 0; for (int i = 1; i <= n; ++ i) { tmp[i] = (sum + a[i]) / a[i]; now_sum += tmp[i]; } if (now_sum > sum) return false; ans = std::move(tmp); return true; }; LL l = 0, r = 1e9; while (l < r) { LL mid = l + r + 1 >> 1; if (check(mid)) { l = mid; break; } else r = mid - 1; } if (check(l)) { for (int i = 1; i <= n; ++ i) { std::cout << ans[i] << " \n"[i == n]; } } else { std::cout << -1 << '\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(); } } |
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 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 |
#include <bits/stdc++.h> using LL = long long; using PII = std::pair<int, int>; int solve() { int n, k; std::cin >> n >> k; std::string s; std::cin >> s; int cnt1 = 0, cnt0 = 0; for (auto c : s) { if (c == '1') { ++ cnt1; } else { ++ cnt0; } } if (cnt1 % k != 0 or cnt0 % k != 0) { return -1; } s = " " + s; std::vector<PII> segMore, segLess; int type = -1; for (int i = 1; i <= n; ++ i) { int j = i + 1; while (j <= n and s[j] == s[i]) ++ j; int len = j - i; if (len == k) { i = j - 1; continue; } if (type == -1) { type = s[i] - '0'; } else if (type != s[i] - '0') { return -1; } if (len > k) { segMore.push_back({i, j - 1}); } else { segLess.push_back({i, j - 1}); } // sum>2 or segMore.size()>1 if (segMore.size() + segLess.size() > 2 or segMore.size() > 1) { return -1; } i = j - 1; } // sum==0 if (segMore.size() + segLess.size() == 0) return n; // brute force check auto check = [&](int p) -> int { std::string t = " " + s.substr(p + 1) + s.substr(1, p); std::reverse(t.end() - p, t.end()); for (int i = 2; i <= k; ++ i) { if (t[i] != t[i - 1]) return -1; } for (int i = 1; i <= n - k; ++ i) { if (t[i + k] == t[i]) return -1; } return p; }; // sum==1 segMore.size()==1 segLess.size()==0 if (segMore.size() + segLess.size() == 1) { if (segLess.size() == 1) return -1; auto [l, r] = segMore[0]; int p = l + k - 1; return check(p); } // sum==2 segMore.size()==1 segLess.size()==1 if (segMore.size() == 1) { auto seg1 = segMore[0]; auto seg2 = segLess[0]; if (seg2.second != n) return -1; auto [l, r] = seg1; int p = r - k; return check(p); } // sum==2 segLess.size()==2 auto seg1 = segLess[0]; auto seg2 = segLess[1]; if (seg2.second != n) return -1; auto [l, r] = seg1; int p = r; return check(p); } 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() << '\n'; } } |
百度之星初赛2
2 前缀和
|
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 |
#include <bits/stdc++.h> using LL = long long; int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); std::cout.tie(nullptr); int n, k; std::cin >> n >> k; std::vector<LL> a(n + 10, 0); while (k --) { int l, r; std::cin >> l >> r; a[l] ++, a[r + 1] --; } for (int i = 1; i <= n; ++ i) a[i] += a[i - 1]; std::sort(a.begin() + 1, a.begin() + 1 + n); std::cout << a[(n + 1) / 2] << '\n'; } |
4 括号序列
|
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 |
#include <bits/stdc++.h> template<typename T> void chkmax(T &a, const T &b) { if (a < b) a = b; } template<typename T> void chkmin(T &a, const T &b) { if (a > b) a = b; } int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); std::cout.tie(nullptr); std::string s; std::cin >> s; if (s.size() == 1) { std::cout << 0; return 0; } int n = s.size(); s = " " + s; std::vector<int> a(n + 1, 0); bool flag = true; for (int i = 1; i <= n; ++ i) { a[i] = a[i - 1] + (s[i] == '(' ? 1 : -1); if (a[i] < 0) flag = false; } flag = flag && a[n] == 0; if (flag) { std::cout << 0; return 0; } std::vector<int> sufmin(n + 1); sufmin[n] = a[n]; for (int i = n - 1; i; -- i) { sufmin[i] = std::min(sufmin[i + 1], a[i]); } int cnt = 0; bool flagpre = false; for (int i = 1; i <= n and not flagpre; ++ i) { int to = (s[i] == '(' ? -1 : 1); int del = to * 2; if (a[n] + del == 0 and a[i] + del >= 0) { if (i == n) cnt ++; else if (i == 1) cnt += (to >= 0); else cnt += (sufmin[i + 1] + del >= 0); } if (a[i] < 0) flagpre = true; } std::cout << cnt << '\n'; } |
1 汉诺塔
|
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 |
#include <bits/stdc++.h> using three = std::tuple<char, char, char>; // 考虑维护(from, by, to)信息[从from柱借助by柱移动到to柱] // 对于n个盘子我们会按顺序做以下三类操作 // (1) 1~n-1 号盘子递归移动 from->by // (2) n号盘子从 from->to // (3) 1~n-1 号盘子递归移动 by->to // 从最高位开始考虑 假设当前位为n // 1. 如果为1, 说明操作(1)(2)都肯定能做完了, 那么n移动到to // =>那么对于之前[1,n)来说还要做操作(3)=>(from,by,to)更新为(by,from,to) // 2. 如果为0, 说明只会做(1)操作, 那么n最后的位置为from // =>那么之前只会做操作(1)=>(from,by,to)更新为(from,to,by) // 做完之后n的位置就确定了, 再对n-1做以上的操作 int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); std::cout.tie(nullptr); int n; std::cin >> n; std::string s; std::cin >> s; s = " " + s; std::vector<char> ans(n + 1); three info {'A', 'B', 'C'}; for (int i = n; i; -- i) { // 从最后一个开始确定 auto [from, by, to] = info; if (s[n + 1 - i] == '1') { // 最后一位对应最高位 ans[i] = to; info = {by, from, to}; } else { ans[i] = from; info = {from, to, by}; } } for (int i = 1; i <= n; ++ i) { std::cout << ans[i]; } } |
5 线段树
|
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 129 130 131 132 |
#include <bits/stdc++.h> struct node { int l, r; std::vector<int> to; // 转换为第一个为0/1的操作数 bool tag; // 子区间是否翻转 node() : l(0), r(0), to({0, 0}), tag(false) {} node(int l, int r, int to0, int to1, bool tag) : l(l), r(r), to({to0, to1}), tag(tag) {} int is_odd_len() { return (r - l + 1) & 1; } void update(node &a, node &b) { for (int i : {0, 1}) { // 如果a是奇数长度则b开头不同 to[i] = a.to[i] + b.to[i ^ a.is_odd_len()]; } } }; struct segmentTree { #define ls(x) (x << 1) #define rs(x) (x << 1 | 1) #define p tr[u] #define pl tr[ls(u)] #define pr tr[rs(u)] std::vector<node> tr; segmentTree(int n) : tr(n << 2) {} void push_up(int u) { p.update(pl, pr); } void push_down(int u) { if (p.tag) { std::swap(pl.to[0], pl.to[1]); pl.tag ^= 1; std::swap(pr.to[0], pr.to[1]); pr.tag ^= 1; p.tag = false; } } void build(int u, int l, int r, std::string &a) { p.l = l, p.r = r; if (l == r) { for (int i : {0, 1}) p.to[i] = (a[l] - '0') ^ i; return; } int mid = l + r >> 1; build(ls(u), l, mid, a); build(rs(u), mid + 1, r, a); push_up(u); } void modify(int u, int l, int r) { if (l <= p.l and p.r <= r) { std::swap(p.to[0], p.to[1]); p.tag ^= 1; return; } push_down(u); int mid = p.l + p.r >> 1; if (l <= mid) modify(ls(u), l, r); if (r > mid) modify(rs(u), l, r); push_up(u); } int query(int u, int l, int r, int ask) { if (l <= p.l and p.r <= r) return p.to[ask]; push_down(u); int mid = p.l + p.r >> 1; int res = 0; if (l <= mid) res += query(ls(u), l, r, ask); if (r > mid) res += query(rs(u), l, r, ask ^ pl.is_odd_len()); return res; } int query(int u, int l, int r) { int query0 = query(u, l, r, 0); int len = r - l + 1; return std::min(query0, len - query0); } #undef ls #undef rs #undef p #undef pl #undef pr }; void solve() { int n, m; std::cin >> n >> m; std::string s; std::cin >> s; s = " " + s; segmentTree tr(n + 10); tr.build(1, 1, n, s); while (m --) { int op, l, r; std::cin >> op >> l >> r; if (op == 1) tr.modify(1, l, r); else std::cout << tr.query(1, l, r) << '\n'; } } int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); std::cout.tie(nullptr); freopen("5.in", "r", stdin); freopen("5.out", "w", stdout); int T = 1; std::cin >> T; while (T --) { solve(); } } |
发表回复