eat shit 场，切了8题，手感火热的一场。（其实水平也就一般吧，哎~
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 |
for i in range(int(input())): a, b, c = map(int, input().split()) ans = 0 if a == 100: ans += 0 elif a == 150: ans += 1 else: ans += 2 if b in [29, 30, 31, 32]: ans += 0 elif b in [34, 36, 38, 40]: ans += 1 else: ans += 2 if c in [29, 30, 31, 32]: ans += 0 elif c in [34, 36, 38, 40]: ans += 1 else: ans += 2 print(ans) |
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 |
#include <bits/stdc++.h> using namespace std; const int N = 310; bool a[N][N]; int main() { cin.tie(0)->sync_with_stdio(0); int n, m, k; cin >> n >> m >> k; int ans = k * 4; while (k --) { int x, y; cin >> x >> y; a[x][y] = true; } for (int i = 1; i <= n; ++ i) for (int j = 1; j <= m; ++ j) { if (!a[i][j]) continue; if (a[i - 1][j]) ans --; if (a[i][j - 1]) ans --; } cout << ans; } |
E
双指针扫一遍，找到不同的答案+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 |
#include <bits/stdc++.h> using namespace std; void solve() { int n; cin >> n; vector<int> a(n); for (auto &x: a) cin >> x; int ans = 0; for (int i = a.size() - 1, j = i; i >= 0; i = -- j) { while (j >= 0 && a[j] == a[i]) -- j; // cout << j << ' ' << i << endl; // [j,i] if (j >= 0) ans ++; else ans += i + 1; } cout << ans << '\n'; } int main() { cin.tie(0)->sync_with_stdio(0); int T; cin >> T; while (T --) solve(); } |
F
考虑维护一个栈，存这个颜色对应最后的位置，每次都取出所有颜色中最小的最右边的数，然后把删掉的地方更新一下就好
赛后发现还有更简单的做法？好像双指针从后向前找k种数就可以，但是不知道为啥对的
|
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 |
#include <bits/stdc++.h> using namespace std; using PII = pair<int, int>; struct cmp { bool operator() (const PII &a, const PII &b) const { return a.first < b.first; } }; void solve() { int n; cin >> n; vector<int> a(n + 1); for (int i = 1; i <= n; ++ i) cin >> a[i]; vector<stack<int>> s(n + 1); for (int i = 1; i <= n; ++ i) { int col = a[i]; s[col].push(i); } set<PII, cmp> st; for (int i = 1; i <= n; ++ i) { if (s[i].size()) { st.insert({s[i].top(), i}); } } int ans = 0; while (n) { auto [pos, col] = *st.begin(); st.erase(st.begin()); set<int> moved; for (int i = n; i >= pos; -- i) { s[a[i]].pop(); moved.insert(a[i]); } for (auto &c: moved) { if (s[c].size()) st.insert({s[c].top(), c}); } n = pos - 1; ans ++; } cout << ans << '\n'; } int main() { cin.tie(0)->sync_with_stdio(0); int T; cin >> T; while (T --) solve(); } |
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 |
#include <bits/stdc++.h> using namespace std; using LL = long long; const int N = 2e5 + 10; int a[N]; void solve() { int n; cin >> n; for (int i = 1; i <= n; ++ i) cin >> a[i]; sort(a + 1, a + 1 + n); LL ans = 0; for (int i = 1; i <= n; ++ i) { ans += (LL)a[i] * (n - 1); } for (int i = 1; i < n; ++ i) { ans += (LL)(n - i) * i * (a[i + 1] - a[i]); } cout << ans * 2 << '\n'; } int main() { cin.tie(0)->sync_with_stdio(0); int T; cin >> T; while (T --) solve(); } |
J
别被绝对值吓到，打开绝对值化简一下就可以发现边权就是$2min(a_u,a_v)$
那么考虑最短路，观察样例，我们可以发现可以让两点通过一个权很小的点来减少路径，我们很容易想到要找权值最小的点。
那么答案就出来了，就是比较一下直接走还是通过点权最小的点。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
#include <bits/stdc++.h> using namespace std; using LL = long long; const int N = 2e5 + 10; int a[N]; void solve() { int n; cin >> n; for (int i = 1; i <= n; ++ i) cin >> a[i]; sort(a + 1, a + 1 + n); LL ans = 0; for (int i = 1; i < n; ++ i) { ans += (LL)min(a[1] * 4, a[i] * 2) * (n - i); } cout << ans * 2 << '\n'; } int main() { cin.tie(0)->sync_with_stdio(0); int T; 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 |
#include <bits/stdc++.h> using namespace std; using LL = long long; using PLI = pair<LL, int>; constexpr int N = 5e3 + 10, M = 5e6 + 10; constexpr LL INF = 0x3f3f3f3f3f3f3f3f; int h[N], e[M], ne[M], w[M], idx; LL dist[N]; bool st[N]; void add(int a, int b, int c) { e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++; } void init(int n) { memset(h, -1, sizeof h); idx = 0; } LL dijkstra(int s, int n) { memset(dist, 0x3f, sizeof dist); memset(st, false, sizeof st); priority_queue<PLI, vector<PLI>, greater<PLI>> q; dist[s] = 0; q.push({0, s}); while (q.size()) { auto [d, v] = q.top(); q.pop(); if (st[v]) continue; st[v] = true; for (int i = h[v]; ~i; i = ne[i]) { int j = e[i]; if (dist[j] > d + w[i]) { dist[j] = d + w[i]; q.push({dist[j], j}); } } } return dist[n - 1]; } void solve() { int n, m, k; cin >> n >> m >> k; init(n); for (int i = 1; i <= m; ++ i) { int a, b; cin >> a >> b; for (int j = 0; j < n; ++ j) { add(j, (j + a) % n, b); } } LL t = dijkstra(k - 1, n); if (t == INF) cout << "-1\n"; else cout << t << '\n'; } int main() { cin.tie(0)->sync_with_stdio(0); int T; cin >> T; while (T --) solve(); } |
K
虽然是考场上最后一道做出来的（之后没时间了），但是难度并非很大，注意题目的数据范围，字母最多四种，下划线最多一个，所以暴搜就可以过
|
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 |
#include <bits/stdc++.h> using namespace std; constexpr int mod = 1e9 + 7; constexpr int N = 15; int t[N], cnt, to[N]; int n, y, ans; bool st[N], has_; char s[N]; void dfs(int u) { if (u == cnt + 1) { for (int i = 0; i <= 9 * has_; ++ i) { int num = 0; bool lead = false; for (int j = 0; j < n; ++ j) { int now; if (isdigit(s[j])) now = s[j] - '0'; else if (islower(s[j])) now = t[to[s[j] - 'a']]; else now = i; if (now == 0 && j == 0 && n > 1) { lead = true; break; } num = num * 10 + now; } if (!lead && num <= y && num % 8 == 0) { ans ++; // cout << num << endl; } } } else { for (int i = 0; i < 10; ++ i) { if (!st[i]) { st[i] = true; t[u] = i; dfs(u + 1); t[u] = 0; st[i] = false; } } } } int solve() { memset(s, 0, sizeof s); cin >> n >> s >> y; cnt = ans = has_ = 0; memset(to, 0, sizeof to); for (int i = 0; i < n; ++ i) { char c = s[i]; if (islower(c)) { to[c - 'a'] = 1; } else if (c == '_') { has_ = true; } } for (int i = 0; i < 4; ++ i) { if (to[i]) to[i] = ++ cnt; } dfs(1); return ans; } int main() { cin.tie(0)->sync_with_stdio(0); int T; cin >> T; while (T --) cout << solve() << '\n'; } |
G
|
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 |
#include <bits/stdc++.h> using namespace std; using LL = long long; constexpr int N = 5e5 + 10; int a[N]; template<typename T> void chkmin(T &a, const T &b) { a > b ? a = b: 0; } template<typename T> void chkmax(T &a, const T &b) { a < b ? a = b: 0; } struct node { int l, r; LL val, add; // 维护min(b[i]+a[i]) }; struct segment_tree { #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)] node tr[N << 2]; void push_up(int u) { p.val = min(pl.val, pr.val); } void push_down(int u) { LL &d = p.add; if (d) { pl.val += d, pl.add += d; pr.val += d, pr.add += d; d = 0; } } void build(int u, int l, int r) { if (l == r) p = {l, r, a[l], 0}; else { p = {l, r}; int mid = l + r >> 1; build(ls(u), l, mid); build(rs(u), mid + 1, r); push_up(u); } } void modify(int u, int l, int r, LL d) { if (l <= p.l && p.r <= r) { p.val += d, p.add += d; } else { push_down(u); int mid = p.l + p.r >> 1; if (l <= mid) modify(ls(u), l, r, d); if (r > mid) modify(rs(u), l, r, d); push_up(u); } } LL query(int u, int l, int r) { if (l <= p.l && p.r <= r) return p.val; push_down(u); int mid = p.l + p.r >> 1; LL res = 2e18; if (l <= mid) chkmin(res, query(ls(u), l, r)); if (r > mid) chkmin(res, query(rs(u), l, r)); push_up(u); return res; } } tr; /** * ans=max{sum[l,i]-a[i+1]} for i in [l,r) * 令b[i]=sum[i,n] * 则ans=max{b[l]-b[i+1]-a[i+1]} * query(l,l)-a[l]-query(l+1,r) */ void solve() { int n, q; cin >> n >> q; for (int i = 1; i <= n; ++ i) cin >> a[i]; tr.build(1, 1, n); // 维护后缀 for (int i = n; i; -- i) { tr.modify(1, 1, i, a[i]); } while (q --) { int op, x, y; cin >> op >> x >> y; if (op == 1) { tr.modify(1, 1, x, y - a[x]); tr.modify(1, x, x, y - a[x]); a[x] = y; } else { cout << tr.query(1, x, x) - tr.query(1, x + 1, y) - a[x] << '\n'; } } } int main() { cin.tie(0)->sync_with_stdio(0); int T; cin >> T; while (T --) solve(); } |
H
|
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 |
#include <iostream> #include <vector> #include <cstring> #include <algorithm> using LL = long long; constexpr int N = 5e5 + 10; constexpr LL INF = 1e17; int a[N]; template<typename T> T max(const T &x) { return x; } template<typename T, typename... Args> T max(const T &x, Args... rest) { return std::max(x, max(rest...)); } struct node { int l, r; LL pre2, // pre- pre3, // pre+- suf1, // suf+ suf3, // suf+- sum , // sum+ sum1, // sum+- ans ; // ans void updata(const node &a, const node &b) { sum = a.sum + b.sum; pre2 = std::max(a.pre2, -a.sum + b.pre2); suf1 = std::max(b.suf1, b.sum + a.suf1); sum1 = max(a.sum - b.sum, a.sum1 - b.sum, a.sum + b.sum1); pre3 = max(a.pre3, a.sum + b.pre3, a.sum1 + b.pre2, a.sum + b.pre2); suf3 = max(b.suf3, -b.sum + a.suf3, b.sum1 + a.suf1, -b.sum + a.suf1); ans = max(a.ans, b.ans, a.suf1 + b.pre2, a.suf1 + b.pre3, a.suf3 + b.pre2); } }; struct segment_tree { #define ls (u << 1) #define rs (u << 1 | 1) #define p tr[u] #define pl tr[ls] #define pr tr[rs] node tr[N << 2]; void push_up(int u) { p.updata(pl, pr); } void build(int u, int l, int r, int *a) { p.l = l, p.r = r; if (l == r) { LL d = a[l]; p.suf1 = p.sum = d; p.pre2 = -d; p.pre3 = p.suf3 = p.ans = p.sum1 = -INF; return; } int mid = l + r >> 1; build(ls, l, mid, a); build(rs, mid + 1, r, a); push_up(u); } void modify(int u, int x, int d) { if (p.l == x && p.r == x) { p.suf1 = p.sum = d; p.pre2 = -d; p.pre3 = p.suf3 = p.ans = p.sum1 = -INF; return; } int mid = p.l + p.r >> 1; if (x <= mid) modify(ls, x, d); else modify(rs, x, d); push_up(u); } node query(int u, int l, int r) { if (p.l >= l && p.r <= r) return p; int mid = p.l + p.r >> 1; if (r <= mid) return query(ls, l, r); if (l > mid) return query(rs, l, r); node res, lq = query(ls, l, r), rq = query(rs, l, r); res.updata(lq, rq); return res; } } tr; void solve() { int n, q; std::cin >> n >> q; for (int i = 1; i <= n; ++ i) std::cin >> a[i]; tr.build(1, 1, n, a); while (q --) { int op, x, y; std::cin >> op >> x >> y; if (op == 1) { tr.modify(1, x, y); } else { std::cout << tr.query(1, x, y).ans << '\n'; } } } int main() { std::cin.tie(0)->sync_with_stdio(0); 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 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 |
#include <iostream> #include <cstring> #include <algorithm> using namespace std; using LL = long long; using PII = pair<int, int>; constexpr int N = 2e5 + 10, M = 31 * N; constexpr int mod = 1e9 + 7; int a[N], pow2[N], inv2[N]; int fpow(int a, int b) { int res = 1; for (; b; b >>= 1) { if (b & 1) res = (LL)res * a % mod; a = (LL)a * a % mod; } return res; } struct trie { int ch[M][2], w[M], idx; void init() { memset(ch, 0, sizeof(int[2]) * (idx + 1)); memset(w, 0, sizeof(int) * (idx + 1)); idx = 0; } void insert(int x, int id) { int p = 0, c = inv2[id]; for (int i = 30; ~i; -- i) { int u = x >> i & 1; if (!ch[p][u]) ch[p][u] = ++ idx; p = ch[p][u]; w[p] = (w[p] + c) % mod; } } int query(int x, int id, int k) { int p = 0, c = pow2[id - 1], res = 0; for (int i = 30; ~i; -- i) { int u = x >> i & 1; int v = k >> i & 1; if (v) { if (ch[p][u]) res = (res + w[ch[p][u]]) % mod; if (!ch[p][u ^ 1]) return (LL)res * c % mod; p = ch[p][u ^ 1]; } else { if (!ch[p][u]) return (LL)res * c % mod; p = ch[p][u]; } } return (LL)(res + w[p]) * c % mod; } } tr; void solve() { int n, k; cin >> n >> k; for (int i = 1; i <= n; ++ i) cin >> a[i]; sort(a + 1, a + 1 + n); int ans = 0; tr.init(); for (int i = 1; i <= n; ++ i) { ans = (ans + tr.query(a[i], i, k) + 1) % mod; tr.insert(a[i], i); } cout << ans << '\n'; } void pre_work() { pow2[0] = 1; for (int i = 1; i < N; ++ i) { pow2[i] = (LL)2 * pow2[i - 1] % mod; inv2[i] = fpow(pow2[i], mod - 2); } } int main() { cin.tie(0)->sync_with_stdio(0); pre_work(); int T; cin >> T; while (T --) solve(); } |
发表回复