题目链接：Codeforces Round #551 (Div. 2)
好久不打又变菜了==
A- Serval and Bus
对于每个车枚举它会在哪些时刻出现，标进vis数组。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
#include <bits/stdc++.h> using namespace std; typedef long long LL; const LL maxn = 100000 + 5; LL n, t, vis[maxn * 2], d[maxn], s[maxn]; int main() { scanf("%lld%lld", &n, &t); for (LL i = 1; i <= n; ++i) { scanf("%lld%lld", s + i, d + i); for (LL j = s[i]; j < maxn * 2; j += d[i]) vis[j] = i; } while (vis[t] == 0) ++t; printf("%lld\n", vis[t]); return 0; } |
B – Serval and Toy Bricks
按照$a_{ij} = \min \{ r_i, c_j \} $构造。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
#include <bits/stdc++.h> using namespace std; typedef long long LL; const LL maxn = 100 + 5; LL n, m, h, mLine[maxn], nLine[maxn], top[maxn][maxn]; int main() { scanf("%lld%lld%lld", &n, &m, &h); for (LL i = 1; i <= m; ++i) scanf("%lld", mLine + i); for (LL i = 1; i <= n; ++i) scanf("%lld", nLine + i); LL x; for (LL i = 1; i <= n; ++i) { for (LL j = 1; j <= m; ++j) { scanf("%lld", &x); if (x != 0) printf("%lld", min(nLine[i], mLine[j])); else printf("0"); if (j != m) printf(" "); else printf("\n"); } } return 0; } |
C – Serval and Parenthesis Sequence
对于$s$的所有严格前缀，满足左括号数恒大于右括号数。运用贪心的思想，使得前缀中的左括号数量尽可能地大，也就是优先排左括号在前面。我们注意到$n$为奇数的时候肯定是无解的，$n$为偶数的时候左括号和右括号各有$\frac{n}{2}$个，按照此规则可以构造出完整的$s$。最终还需要检查一下括号匹配是否合法，是否有严格前缀正好可以合法匹配的情况。
|
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; typedef long long LL; LL n, l, r; string s; bool check() { LL leftPar = 0; for (unsigned i = 0; i < s.size(); ++i) { leftPar += (s[i] == '('); if (s[i] == ')' && !leftPar) return false; if (s[i] == ')' && leftPar) --leftPar; if (leftPar == 0 && i != s.size() - 1) return false; } return true; } int main() { ios::sync_with_stdio(false); cin >> n >> s; if (n & 1) { cout << ":(" << endl; return 0; } for (auto const &c: s) { if (c == '(') ++l; if (c == ')') ++r; } LL maxL = n / 2; LL leftPar = maxL - l; if (leftPar < 0) { cout << ":(" << endl; return 0; } for (unsigned i = 0; i < s.size(); ++i) { if (s[i] == '?') { if (leftPar) --leftPar, s[i] = '('; else s[i] = ')'; } } cout << (check() ? s : ":(") << endl; return 0; } |
D – Serval and Rooted Tree
首先考虑$\min$操作，假设$u$的所有子树的值的集合是$\{ 2,5,6 \}$，那么对$u$节点取$\min$之后得到$2$，$5,6$被损失掉了。我们发现只要又$\min$操作就会损失一些比决策结果更大的数，这对我们是不利的——因为我们总希望每个被决策出来的值尽量地大，这就需要我们少损失一些比较大的数。考虑$\max$操作，选择损失掉最少的子树。dfs后最终根节点的值就是所有损失掉的比较大的数，例如总共8个数，损失3个数，即损失了6、7、8。所以用$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 |
#include <bits/stdc++.h> using namespace std; typedef long long LL; const LL maxn = 300000 + 5; LL n, a[maxn], k; vector <LL> g[maxn]; LL dfs(LL x) { if (g[x].size() == 0) { ++k; return 0; } if (a[x] == 0) { LL ret = 0; for (unsigned i = 0; i < g[x].size(); ++i) { ret = ret + dfs(g[x][i]) + 1; } return ret - 1; } else { LL ret = INT_MAX; for (unsigned i = 0; i < g[x].size(); ++i) { ret = min(ret, dfs(g[x][i])); } return ret; } } int main() { ios::sync_with_stdio(false); cin >> n; for (LL i = 1; i <= n; ++i) cin >> a[i]; LL tf; for (LL i = 2; i <= n; ++i) { cin >> tf; g[tf].push_back(i); } LL lost = dfs(1); cout << (k - lost) << endl; return 0; } |
E, F
待填坑。
说点什么