题目链接:Codeforces AIM Tech Round 5
CF终于上分了QAQ
A – Find Square
模拟。
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 namespace std; typedef long long LL; const LL maxn = 115 + 1; LL n, m; char table[maxn][maxn]; pair <LL, LL> get_first() { for (LL i = 1; i <= n; ++i) { for (LL j = 1; j <= m; ++j) { if (table[i][j] == 'B') return make_pair(i, j); } } } int main() { ios::sync_with_stdio(false); cin >> n >> m; for (LL i = 1; i <= n; ++i) { for (LL j = 1; j <= m; ++j) { cin >> table[i][j]; } } auto f = get_first(); LL sx = f.first, sy = f.second; LL ex = sx, ey = sy; while (table[ex][sy] == 'B') { ++ex; if (ex > n) break; } --ex; while (table[sx][ey] == 'B') { ++ey; if (ey > m) break; } --ey; cout << (sx + ex) / 2 << " " << (sy + ey) / 2 << endl; return 0; } |
B – Unnatural Conditions
这是一个构造题,假设$S(a),S(b)$都非常非常大,则可以满足$S(a) \geq n, S(b) \geq n$,那么什么情况下是$S(a+b)$会非常小(小于m)呢?很显然是在有进位的时候——如果所有的位全部进位成0,只留下第一位是1,这种情况一定满足$S(a+m) \leq m$。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
#include <bits/stdc++.h> using namespace std; typedef long long LL; LL n, m; int main() { ios::sync_with_stdio(false); cin >> n >> m; for (LL i = 1; i <= n; ++i) { cout << 1; } cout << endl; for (LL i = 1; i <= n; ++i) { cout << (i == n ? 9 : 8); } cout << endl; return 0; } |
C – Rectangles
题目保证了$n$个矩形中有$n-1$个有公共点,也即是说去掉其中一个矩形就可以得到$n-1$个矩形的公共交,在这个公共交里随便找个点输出就是最后的答案。
我们需要确认是去掉那个矩形,假设第$i$个矩形是一个异类,那么它前面所有的矩形一定和后面所有的矩形有公共交,否则前面所有矩形和后面所有矩形求公共交为空集,所以维护前缀交和后缀交即可。
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 |
#include <bits/stdc++.h> using namespace std; typedef long long LL; struct coordinate { LL x, y; coordinate(LL x_, LL y_): x(x_), y(y_) {} coordinate() {} }; struct rectangle { coordinate bl, ur; rectangle(LL x1_, LL y1_, LL x2_, LL y2_) { bl = coordinate(x1_, y1_); ur = coordinate(x2_, y2_); } rectangle(coordinate bl_, coordinate ur_): bl(bl_), ur(ur_) {} rectangle() {} inline bool empty() { return bl.x == INT_MAX && bl.y == INT_MAX && ur.x == INT_MAX && ur.y == INT_MAX; } }; rectangle get_intersection(const rectangle &r1, const rectangle &r2) { coordinate ret_bl, ret_ur; ret_bl.x = max(r1.bl.x, r2.bl.x); ret_bl.y = max(r1.bl.y, r2.bl.y); ret_ur.x = min(r1.ur.x, r2.ur.x); ret_ur.y = min(r1.ur.y, r2.ur.y); if (ret_bl.x <= ret_ur.x && ret_bl.y <= ret_ur.y) return rectangle(ret_bl, ret_ur); else return rectangle(INT_MAX, INT_MAX, INT_MAX, INT_MAX); } const LL maxn = 132674 + 5; rectangle pre[maxn], suf[maxn], ori[maxn]; LL tx1, ty1, tx2, ty2, n; void read(LL &x) { x = 0; char ch = getchar(); LL sgn = 1; while (ch < '0' || ch > '9') { if (ch == '-') sgn = -1; ch = getchar(); } while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); } x *= sgn; } rectangle get_ans() { rectangle ans; for (LL i = 1; i <= n; ++i) { ans = get_intersection(pre[i - 1], suf[i + 1]); if (!ans.empty()) break; } return ans; } int main() { read(n); for (LL i = 1; i <= n; ++i) { read(tx1); read(ty1); read(tx2); read(ty2); ori[i] = rectangle(tx1, ty1, tx2, ty2); } pre[0] = rectangle(-INT_MAX, -INT_MAX, INT_MAX, INT_MAX); for (LL i = 1; i <= n; ++i) { pre[i] = get_intersection(pre[i - 1], ori[i]); } suf[n + 1] = rectangle(-INT_MAX, -INT_MAX, INT_MAX, INT_MAX); for (LL i = n; i >= 1; --i) { suf[i] = get_intersection(suf[i + 1], ori[i]); } rectangle ans = get_ans(); printf("%lld %lld\n", ans.bl.x, ans.bl.y); return 0; } |
D – Order book
我们先在草稿纸上列一些数据。如果所有ADD对应的p所组成的有序集合是这样的:
$$\{1,2,3,5,6,7,8,9,11\}$$
那么假如2是Best Buy,那么Best Sell 一定是3,并且2前面的一定是buy,3后面的一定是sell。所以我们解题关键就是维护这个分解位置,即Best Sell和Best Buy。然后对于每个ACCEPT,要分类讨论:
- $b_{buy} = p$ 说明这个ACCEPT一定是Buy
- $b_{sell} = p$ 说明这个ACCEPT一定是Sell
- $b_{buy} < p < b_{sell}$ 说明这个ACCEPT可能是Buy可能是Sell
- $b_{buy} > p | p > b_{sell}$ 非法ACCEPT
这样只有第三种情况需要把最后的可能性翻倍。对于每一次操作,删除ACCEPT的p并且将Best Buy和Best Sell设为最接近p的上下两个值。(这里就用到了set迭代器的给力功能)
最终我们可以确定Best Buy和它的左边都是Buy,Best Sell和它的右边都是Sell,那么中间还有未确定的元素,根据记数原理,如果还剩下$m$个数,则需要把可能性乘以$m+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 47 48 49 50 51 52 |
#include <bits/stdc++.h> using namespace std; typedef long long LL; const LL MOD = 1000000000 + 7; set <LL> s; LL ans, pr, n; string op; int main() { s.insert(INT_MAX); s.insert(-INT_MAX); LL best_buy = -INT_MAX, best_sell = INT_MAX; ans = 1; ios::sync_with_stdio(false); cin >> n; for (LL i = 1; i <= n; ++i) { cin >> op >> pr; if (op == "ADD") { s.insert(pr); } else { auto pos = s.find(pr); auto up = pos, down = pos; ++up; --down; if (pos == s.end()) { cout << 0 << endl; return 0; } else if (pr > best_buy && pr < best_sell) { ans = ans * 2 % MOD; best_buy = *down; best_sell = *up; s.erase(pr); } else if (pr == best_buy) { best_buy = *down; best_sell = *up; s.erase(pr); } else if (pr == best_sell) { best_buy = *down; best_sell = *up; s.erase(pr); } else { cout << 0 << endl; return 0; } } } LL undetermined = 0; for (auto const &x: s) { if (x > best_buy && x < best_sell) ++undetermined; } ans = ans * (undetermined + 1) % MOD; cout << ans << endl; return 0; } |
E – Restore Array
硬核构造题,按照官方的题解补了下题,但是有些细节还是不能理解。
找到一个最大的元素作为$b_n$(即$b$数列的最后一个元素,如果不是最后一位则可以通过切割移动来实现),然后$a_i = \sum_{j = i}^{n – 1} b_j + 2\cdot b_n $ 。
我觉得出题人是想试图把 $b_i = a_i \mod a_{i + 1}$ 转化成$b_i = a_i – a_{i + 1} \quad (b_i < a_{i + 1})$,所以当$a_i > b_{max}$ 的时候可以满足这个条件,当然$b_i$不能全为0。我不能理解的有两点,第一是为什么是加上$2 \cdot b_n$,第二点是为什么$a_n = b_n$,这两点之间可能存在联系,也就是更改$a_n$之后$2 \cdot b_n$这一项也会随之更改?
有几个点要注意的是最大值的前一位如果和最大值相等,这个最大值是不能取的,因为此时$a_n – 1 = 3 \cdot b_n, b_{n – 1} \neq a_{n – 1} \mod a_n = 0 $。所以面对这种情况需要单独判断,此时又要分两种情况,一种是全为0,这是可构造的,否则是不可构造的。
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 |
#include <bits/stdc++.h> using namespace std; typedef long long LL; const LL maxn = 140582 + 5; LL pre[maxn], b[maxn], tb[maxn], a[maxn], ta[maxn], n; LL max_ele, max_pos; int main() { ios::sync_with_stdio(false); cin >> n; for (LL i = 1; i <= n; ++i) { cin >> b[i]; } max_ele = *max_element(b + 1, b + n + 1); max_pos = 0; for (LL i = 1; i <= n; ++i) { if (max_ele == b[i] && max_ele != b[(i - 1 >= 1 ? i - 1 : n)]) { max_pos = i; break; } } if (max_pos == 0) { if (max_ele == 0) { cout << "YES" << endl; for (LL i = 1; i <= n; ++i) { cout << "1" << (i == n ? "\n" : " "); } } else { cout << "NO" << endl; } return 0; } for (LL i = 1; i <= n; ++i) tb[i] = (i <= n - max_pos ? b[i + max_pos] : b[i - (n - max_pos)]); for (LL i = 1; i <= n; ++i) pre[i] = pre[i - 1] + tb[i]; for (LL i = 1; i <= n - 1; ++i) { ta[i] = pre[n - 1] - pre[i - 1] + max_ele * 2; } ta[n] = tb[n]; for (LL i = 1; i <= n; ++i) a[i] = (i <= max_pos ? ta[i + (n - max_pos)] : ta[i - max_pos]); cout << "YES" << endl; for (LL i = 1; i <= n; ++i) cout << a[i] << (i == n ? "\n" : " "); return 0; } |
F,G,H
待填坑。
说点什么