AtCoder Beginner Contest 133

mac2022-06-30 17

Contest InfoSolutions A. T or TB.Good DistanceC. Remainder Minimization 2019D. Rain Flows into DamsE. Virus Tree 2F. Colorful Tree

Contest Info

Practice Link

SolvedABCDEF6/6OOOOOO O 在比赛中通过Ø 赛后通过! 尝试了但是失败了- 没有尝试

Solutions

A. T or T

#include <bits/stdc++.h> using namespace std; int main() { int n, a, b; while (cin >> n >> a >> b) { cout << min(n * a, b) << "\n"; } return 0; }

B.Good Distance

#include <bits/stdc++.h> using namespace std; #define N 110 int n, d, x[N][N]; int dis(int i, int j) { int res = 0; for (int o = 1; o <= d; ++o) { res += (x[i][o] - x[j][o]) * (x[i][o] - x[j][o]); } return res; } int main() { set <int> se; se.insert(0); for (int i = 1; i <= 30000; ++i) { se.insert(i * i); } while (scanf("%d%d", &n, &d) != EOF) { for (int i = 1; i <= n; ++i) { for (int j = 1; j <= d; ++j) { scanf("%d", x[i] + j); } } int res = 0; for (int i = 1; i <= n; ++i) { for (int j = 1; j < i; ++j) { int Dis = dis(i, j); if (se.count(Dis)) { ++res; } } } printf("%d\n", res); } return 0; }

C. Remainder Minimization 2019

#include <bits/stdc++.h> using namespace std; #define p 2019 int main() { int l, r; while (scanf("%d%d", &l, &r) != EOF) { if (r - l + 1 >= 3000) { puts("0"); continue; } else { int res = 1e9; for (int i = l; i <= r; ++i) { for (int j = l; j < i; ++j) { res = min(res, (i % p) * (j % p) % p); } } printf("%d\n", res); } } return 0; }

D. Rain Flows into Dams

题意：给出两个序列\(a_i, b_i\)，知道\(a_i\)和\(b_i\)的关系如下：\[ a_i = \begin{cases} \frac{b_n}{2} + \frac{b_1}{2} &&i = n \\ \frac{b_i}{2} + \frac{b_{i + 1}}{2} && i \neq n \end{cases} \] 现在给出\(a_i\)，要求还原\(b_i\)。

思路：\(n = 3\)时：\[ \begin{eqnarray} a_1 = \frac{b_1}{2} + \frac{b_2}{2} \\ a_2 = \frac{b_2}{2} + \frac{b_3}{2} \\ a_3 = \frac{b_3}{2} + \frac{b_1}{2} \end{eqnarray} \] 我们发现\(b_1 = (1) - (2) + (3)\) 然后就可以还原\(b_i\)了。

#include <bits/stdc++.h> using namespace std; #define ll long long #define N 100010 int n, a[N]; ll b[N]; int main() { while (scanf("%d", &n) != EOF) { for (int i = 1; i <= n; ++i) { scanf("%d", a + i); } b[1] = 0; for (int i = 1; i <= n; ++i) { b[1] += a[i] * ((i & 1) ? 1 : -1); } b[n] = 2ll * a[n] - b[1]; for (int i = n - 1; i > 1; --i) { b[i] = 2ll * a[i] - b[i + 1]; } for (int i = 1; i <= n; ++i) printf("%lld%c", b[i], " \n"[i == n]); } return 0; }

E. Virus Tree 2

题意：用\(K\)种颜色个一棵树染色，要求距离小于等于\(2\)的两个点的颜色不同。求方案数。

思路：如果距离小于等于\(1\)的两个点的颜色不同怎么求? 考虑每个点跟父亲不同就好了，答案为\(k \cdot (k - 1)^{n - 1}\)

那距离小于等于\(2\)呢？考虑跟父亲往上走的距离小于等于\(2\)的点的颜色，因为这个点任意两个点的距离也是小于等于\(2\)的，也就是说这个点集中的每个点的颜色都不同，假设大小为\(sze\)，那么当前点的选择总数为\(k - sze\)。乘一乘就好了。

F. Colorful Tree

题意：有一棵树，每条边有颜色和边权。每次询问要求将所有颜色为\(x_i\)的边的边权都改成\(y_i\)，然后询问\(u_i \rightarrow v_i\)的距离。

思路：将询问拆成原来的距离 - 路径上颜色为\(x_i\)的边的边权和 + 路径上颜色为\(x_i\)的边的条数 * \(y_i\) 然后离线即可。其实不用写树剖和树状数组，只要将询问拆成三个询问丢在点那里，\(DFS\)下去的时候分别维护一下三个信息就好了。

#include <bits/stdc++.h> using namespace std; #define N 100010 #define pii pair <int, int> #define fi first #define se second int n, q; struct node { int u, v, w, id; node() {} node(int v, int w) : v(v), w(w) {} node (int u, int v, int w, int id = 0) : u(u), v(v), w(w), id(id) {} }; vector <vector<node>> E, Q, G; int res[N]; int fa[N], deep[N], dis[N], sze[N], son[N], top[N], in[N], cnt; void DFS(int u) { sze[u] = 1; for (auto it : G[u]) if (it.v != fa[u]) { int v = it.v; fa[v] = u; deep[v] = deep[u] + 1; dis[v] = dis[u] + it.w; DFS(v); sze[u] += sze[v]; if (son[u] == -1 || sze[v] > sze[son[u]]) son[u] = v; } } void gettop(int u, int sp) { top[u] = sp; in[u] = ++cnt; if (son[u] == -1) return; gettop(son[u], sp); for (auto it : G[u]) { int v = it.v; if (v == fa[u] || v == son[u]) continue; gettop(v, v); } } int querylca(int u, int v) { while (top[u] != top[v]) { if (deep[top[u]] < deep[top[v]]) { swap(u, v); } u = fa[top[u]]; } if (deep[u] > deep[v]) swap(u, v); return u; } pii add(pii x, pii y) { return pii(x.fi + y.fi, x.se + y.se); } pii sub(pii x, pii y) { return pii(x.fi - y.fi, x.se - y.se); } struct BIT { pii a[N]; void init() { memset(a, 0, sizeof a); } void update(int x, int s, int t) { for (; x < N; x += x & -x) { a[x] = add(a[x], pii(s, t)); } } pii query(int x) { pii res = pii(0, 0); for (; x > 0; x -= x & -x) { res = add(res, a[x]); } return res; } pii query(int l, int r) { return sub(query(r), query(l - 1)); } }bit; pii query(int u, int v) { pii res = pii(0, 0); while (top[u] != top[v]) { if (deep[top[u]] < deep[top[v]]) swap(u, v); res = add(res, bit.query(in[top[u]], in[u])); u = fa[top[u]]; } if (u == v) return res; if (deep[u] > deep[v]) swap(u, v); return add(res, bit.query(in[son[u]], in[v])); } void init() { bit.init(); cnt = 0; dis[1] = 0; fa[1] = 0; E.clear(); E.resize(n + 1); Q.clear(); Q.resize(n + 1); G.clear(); G.resize(n + 1); memset(son, -1, sizeof son); memset(res, 0, sizeof res); } int main() { while (scanf("%d%d", &n, &q) != EOF) { init(); for (int i = 1, u, v, c, d; i < n; ++i) { scanf("%d%d%d%d", &u, &v, &c, &d); G[u].push_back(node(v, d)); G[v].push_back(node(u, d)); E[c].push_back(node(u, v, d)); } for (int i = 1, c, u, v, w; i <= q; ++i) { scanf("%d%d%d%d", &c, &w, &u, &v); Q[c].push_back(node(u, v, w, i)); } DFS(1); gettop(1, 1); // for (int i = 1; i <= n; ++i) printf("%d %d %d %d\n", i, fa[i], son[i], in[i]); for (int i = 1; i < n; ++i) { if (Q[i].empty()) continue; for (auto &it : E[i]) { if (fa[it.u] == it.v) swap(it.u, it.v); bit.update(in[it.v], 1, it.w); } for (auto it : Q[i]) { int u = it.u, v = it.v, w = it.w, id = it.id; int lca = querylca(u, v); // cout << u << " " << v << " " << lca << endl; pii tmp = query(u, v); res[id] = dis[u] + dis[v] - 2 * dis[lca] - tmp.se + w * tmp.fi; } for (auto it : E[i]) { bit.update(in[it.v], -1, -it.w); } } for (int i = 1; i <= q; ++i) printf("%d\n", res[i]); } return 0; }

转载于:https://www.cnblogs.com/Dup4/p/11148100.html

相关资源：JAVA上百实例源码以及开源项目

最新回复(0)