华师的比赛赚了 200+50=250￥。下次还来打。😋😋😋
实际上两次比赛贪心找规律的题目都没有做出来，而且犯错太多了，罚时太多了。
感觉好像只有模拟的题做的快，实际上需要动脑筋的题目还是不行。
还得训，说实话。不过别灰心，再接再励。
新生赛
比较简单的一次比赛，二等，+200￥。
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 28 29 30 31 32 33 34 35 |
#include <bits/stdc++.h> using namespace std; const int N = 5e4 + 10; char s[N]; int n; bool is_letter(int x) { if (x == 1 || x == n) return false; return s[x - 1] > s[x] && s[x] < s[x + 1]; } bool is_wind(int x) { if (x == 1 || x == n) return false; return s[x - 1] < s[x] && s[x] > s[x + 1]; } int main() { cin.tie(0)->sync_with_stdio(0); cin >> n; cin >> s + 1; vector<int> ans; for (int i = 2; i < n; ++ i) { if (is_wind(i - 1) && is_letter(i) && is_wind(i + 1)) { ans.push_back(i); } } cout << ans.size() << '\n'; if (ans.size()) { for (auto i: ans) cout << i << ' '; } } |
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 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 |
#include <bits/stdc++.h> using namespace std; const int N = 1e6 + 10; int n, q, k; int xh[N], cnt = -1; int pow(int a, int b) { int res = 1; while (b --) res *= a; return res; } int mysort(int x) { vector<int> d; for (int i = 1; i <= n; ++ i) { d.push_back(x % 10); x /= 10; } sort(d.begin(), d.end()); int res = 0; for (int i = 0; i < n; ++ i) { int t = d[i]; res += t * (pow(10, i) - pow(10, n - 1 - i)); } return res; } void out(int x, int d=n) { if (!d) return; out(x / 10, d - 1); cout << x % 10; } int main() { cin >> n >> q >> k; unordered_map<int, pair<bool, int>> m; m[q] = {true, 0}; xh[++ cnt] = q; int p = mysort(q); while (!m[p].first) { q = p; p = mysort(q); xh[++ cnt] = q; m[q] = {true, cnt}; } int jie = m[p].second; int dist; if (k > cnt) dist = (k - jie) % (cnt - jie + 1) + jie; else dist = k; out(xh[dist]); } |
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 |
#include <bits/stdc++.h> using namespace std; const int N = 5e5 + 10; int d[N]; void solve() { memset(d, 0, sizeof d); int n; cin >> n; for (int i = 1; i < n; ++ i) { int u, v; cin >> u >> v; d[u] ++; d[v] ++; } int m = 0; for (int i = 1; i <= n; ++ i) if (d[i] <= 1) m ++; bool flag = m + n & 1 ^ 1; if (flag) cout << "AlexFisher\n"; else cout << "FlowerLion\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 |
#include <bits/stdc++.h> using namespace std; using LL = long long; const int N = 1e5 + 10, M = 110; const int NN = N << 1; int n, m, a[N]; int h[M][N], e[NN], ne[NN], idx; vector<int> st[M]; void add(int a, int b, int h[]) { e[idx] = b, ne[idx] = h[a], h[a] = idx ++; } LL solve(int h[], int x) { vector<LL> d(n + 1, 0); vector<bool> vis(n + 1, false); int c = 0; function<void(int,int)> dfs = [&](int u, int fa) -> void { vis[u] = true; for (int j = h[u]; ~j; j = ne[j]) { int v = e[j]; if (v == fa) continue; d[v] = d[u] + a[v]; if (d[v] > d[c]) c = v; dfs(v, u); } }; LL ans = 0; for (auto u: st[x]) if (!vis[u]) { d[u] = a[u]; dfs(u, 0); d[c] = a[c]; dfs(c, 0); ans = max(ans, d[c]); c = 0; } return ans; } int main() { cin.tie(0)->sync_with_stdio(0); memset(h, -1, sizeof h); cin >> n >> m; for (int i = 1; i <= n; ++ i) cin >> a[i]; for (int i = 1; i < n; ++ i) { int u, v, x; cin >> u >> v >> x; add(u, v, h[x]); add(v, u, h[x]); st[x].push_back(u); st[x].push_back(v); } LL ans = 0; for (int i = 1; i <= m; ++ i) { ans = max(ans, solve(h[i], i)); } cout << ans; } |
E
|
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; struct midnum { priority_queue<int, vector<int>, greater<int>> big; priority_queue<int> small; int siz = 0; int size() { return siz; } int get() { if (size() & 1) return big.top(); return small.top(); } void insert(int x) { if (!siz ++ || x < get()) small.push(x); else big.push(x); if (small.size() > siz >> 1) { big.push(small.top()); small.pop(); } else if (big.size() > (siz + 1) >> 1) { small.push(big.top()); big.pop(); } } }; int main() { cin.tie(0)->sync_with_stdio(0); int n; cin >> n; midnum m; for (int i = 1; i <= n; ++ i) { int x; cin >> x; m.insert(x); cout << m.get() << ' '; } } |
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 |
#include <bits/stdc++.h> using namespace std; void solve() { int flag = -1; for (int i = 0; i < 4; ++ i) { string x; cin >> x; if (flag == -1) { if (i == 0 && x == "yellow") flag = true; if (i == 0 && x == "green") flag = false; if (i == 1 && x == "no") flag = false; if (i == 2 && x == "mane") flag = false; if (i == 2 && x == "nothing") flag = false; if (i == 3 && x == "yes") flag = true; if (i == 3 && x == "no") flag = false; } } cout << (flag ? "Yes": "No") << '\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 |
#include <bits/stdc++.h> using namespace std; using LL = long long; const int N = 5e5 + 10; int n, m; int a[N], s[N]; int main() { cin.tie(0)->sync_with_stdio(0); cin >> n >> m; for (int i = 1; i <= n; ++ i) { cin >> a[i]; a[i] %= m; } s[0] = 0; for (int i = 0; i <= n; ++ i) { s[i] = (s[i - 1] + a[i]) % m; // cout << s[i] << ' '; } map<int, int> m; for (int i = 0; i <= n; ++ i) { m[s[i]] ++; } LL ans = 0; for (auto [x, y]: m) { ans += (LL)y * (y - 1) >> 1; } cout << ans; } |
图森杯
说实话有点菜了，贪心的题没有做出来，显得有点笨了。
A
实话说，我没想到 python 可以一遍过，在 C++ 中还是需要约分操作的，但是 python 好像没有这个问题。
|
1 2 3 4 5 6 |
a, b, c, d, e, f = map(int, input().split()) if a + b / c == d + e / f: print('Yes') else: print('No') |
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 |
#include <bits/stdc++.h> using namespace std; using LL = long long; template<typename T> void chkmax(T &x, const T &y) { if (x < y) x = y; } int fpow(int a, int b, int mod) { int res = 1; while (b) { if (b & 1) res = 1ll * res * a % mod; a = 1ll * a * a % mod; b >>= 1; } return res; } int inv(int x, int mod) { return fpow(x, mod - 2, mod); } int main() { cin.tie(0)->sync_with_stdio(0); srand(time(0)); int n, p; cin >> n >> p; vector<int> a(n); for (int i = 0; i < n; ++ i) { cin >> a[i]; } auto calc = [&]() -> int { int res = 2; int x = rand() % n; int y = x + rand() % 3 + 1; if (y >= n) return res; int q = (LL)a[y] * inv(a[x], p) % p; int l = a[x], r = a[y]; for (int i = y + 1; i < n; ++ i) { if ((LL)r * q % p == a[i]) { r = a[i]; ++ res; } } for (int i = x - 1; i >= 0; -- i) { if ((LL)l * inv(q, p) % p == a[i]) { l = a[i]; ++ res; } } return res; }; int res = n / 2; do { chkmax(res, calc()); } while ((double)clock() / CLOCKS_PER_SEC < 0.9); cout << res << '\n'; } |
F
文艺平衡树，虽然这道题好像暴力可做，似乎是题目数据弱了。确实得找个时间学习一下数据结构。
|
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 |
#include <bits/stdc++.h> #define Lson(k) (nodes[k].ch[0]) #define Rson(k) (nodes[k].ch[1]) #define fa(k) (nodes[k].fa) using namespace std; constexpr int MAXN = 5e5; int e, root; struct node { int val, size, lazy; int fa; int ch[2]; } nodes[MAXN + 10]; void pushdown(int k) { if (nodes[k].lazy) { nodes[Lson(k)].lazy ^= 1; nodes[Rson(k)].lazy ^= 1; swap(Lson(k), Rson(k)); nodes[k].lazy ^= 1; } } bool id(int k) { return k == nodes[fa(k)].ch[1]; } void link(int fa, int son, int sp) { if (fa) nodes[fa].ch[sp] = son; nodes[son].fa = fa; } void update(int k) { nodes[k].size = nodes[Lson(k)].size + nodes[Rson(k)].size + 1; } void rotate(int k) { int fa = fa(k); int gra = fa(fa); int spk = id(k); int spfa = id(fa); link(fa, nodes[k].ch[spk ^ 1], spk); link(k, fa, spk ^ 1); link(gra, k, spfa); nodes[k].size = nodes[fa].size; update(fa); } void splay(int k, int p) { while (nodes[k].fa != p) { int fa = fa(k); if (fa(fa) != p) id(fa) == id(k) ? rotate(fa) : rotate(k); rotate(k); } if (!p) root = k; } void insert(int &k, int x, int fa) { if (!k) { k = ++e; nodes[e].fa = fa; nodes[e].size = 1; nodes[e].val = x; splay(k, 0); return; } nodes[k].size++; if (x > nodes[k].val) insert(Rson(k), x, k); else if (x < nodes[k].val) insert(Lson(k), x, k); } int atRank(int k, int x) { if (!k) return 0; pushdown(k); if (x > nodes[Lson(k)].size + 1) return atRank(Rson(k), x - nodes[Lson(k)].size - 1); if (x <= nodes[Lson(k)].size) return atRank(Lson(k), x); return k; } int n, q; void solve(int l, int r) { int lch = atRank(root, l); int rch = atRank(root, r + 2); splay(lch, 0); splay(rch, root); nodes[Lson(rch)].lazy ^= 1; } void out(int k){ if (!k) return; pushdown(k); out(Lson(k)); if (nodes[k].val > 1 && nodes[k].val - 1 <= n) printf("%d ", nodes[k].val - 1); out(Rson(k)); } int main() { scanf("%d%d", &n, &q); for (int i = 1; i <= n + 2; i++) insert(root, i, 0); while (q--) { int l, r; scanf("%d%d", &l, &r); solve(l, r); } out(root); } |
发表回复