目录
Contest InfoSolutions A A Prize No One Can WinB Birthday BoyC Cardboard ContainerD Driver DisagreementE Entirely Unsorted SequencesF Financial PlanningG Game NightH Harry the HamsterI In Case of an Invasion, Please. . .J Janitor TroublesK Kingpin EscapePractice Link
SolvedABCDEFGHIJK8/11OOO--OO-OOO O 在比赛中通过Ø 赛后通过! 尝试了但是失败了- 没有尝试签到。view code
#include <bits/stdc++.h> using namespace std; const int N = 1e5 + 10; int n, a[N], x; int main() { while (scanf("%d%d", &n, &x) != EOF) { for (int i = 1; i <= n; ++i) scanf("%d", a + i); sort(a + 1, a + 1 + n); int res = 1; for (int i = 2; i <= n; ++i) { if (a[i] + a[i - 1] <= x) { ++res; } else break; } printf("%d\n", res); } return 0; }题意： 给出\(n\)个生日，现在要找个日期，使得在它前面离它最近的生日和它相距的天数最大，如果有多个，输出和\(10-27\)相距天数最大的。
思路： 题意读清楚就可以了，枚举每一天。view code
#include <bits/stdc++.h> using namespace std; using pII = pair <int, int>; #define fi first #define se second int n; pII a[110]; char s[110]; int mon[] = { 0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31 }; bool operator < (pII a, pII b) { if (a.fi < b.fi || (a.fi == b.fi && a.se <= b.se)) { return true; } return false; } int dis(pII a, pII b) { if (a < b) { if (a.fi == b.fi) return b.se - a.se; int res = mon[a.fi] - a.se; for (int i = a.fi + 1; i < b.fi; ++i) res += mon[i]; res += b.se; return res; } else { int res = mon[a.fi] - a.se; for (int i = a.fi + 1; i <= 12; ++i) res += mon[i]; for (int i = 1; i < b.fi; ++i) res += mon[i]; res += b.se; return res; } } int main() { while (scanf("%d", &n) != EOF) { for (int i = 1; i <= n; ++i) scanf("%s d-d", s, &a[i].fi, &a[i].se); sort(a + 1, a + 1 + n, [&](pII x, pII y) { if (x.fi != y.fi) return x.fi < y.fi; return x.se < y.se; }); pII res = pII(-1, -1); int Max = -1; a[0] = a[n]; int pos = 0; for (int i = 1; i <= 12; ++i) { for (int j = 1; j <= mon[i]; ++j) { pII t = pII(i, j); while (pos < n && a[pos + 1] < t) ++pos; if (dis(a[pos], t) > Max) { Max = dis(a[pos], t); res = t; } else if (dis(a[pos], t) == Max) { if (dis(pII(10, 28), t) < dis(pII(10, 28), res)) { res = t; } } } } printf("d-d\n", res.fi, res.se); } return 0; }题意： 给出一个立方体的体积\(V\)，算表面积
思路： 枚举长宽高，长宽高是\(V\)的因子，枚举量不大。view code
#include <bits/stdc++.h> using namespace std; typedef long long ll; void getfac(vector <int> &vec, int n) { vec.clear(); for (int i = 1; 1ll * i * i <= n; ++i) { if (n % i == 0) { vec.push_back(i); if (i * i != n) vec.push_back(n / i); } } } int main() { int n; while (scanf("%d", &n) != EOF) { vector <int> vec_a; getfac(vec_a, n); ll res = 1e18; for (auto a : vec_a) { vector <int> vec_b; getfac(vec_b, n / a); for (auto &b : vec_b) { int c = n / a / b; res = min(res, 2ll * (a * b + a * c + b * c)); } } printf("%lld\n", res); } return 0; }题意： 给出\(n\)个点的图，每个点都有两条边，并且每个点有一个标记\(1\)或者\(0\) 现在两个人在同一点，但是他们不知道自己在哪一点，一个人觉得他们在\(A\)，另一个人觉得他们在\(B\)。 然后他们所在的位置是\(A\)或者\(B\) 现在需要设计一种路线，使得沿着路线走，如果从\(A\)出发走到一个点和从\(B\)出发走到一个点那个点的标记不一样，那么它们就知道谁对谁错了。 现在问最少的路线长度。 这个路线是每次选择往左走还是往右走，因为每个点有两条边
题意： 有\(n\)个数，定义一个数是有序的当且仅当它左边的数都小于等于它，它右边的数都大于等于它。 现在问有多少种这些数的排列，使得所有数都不是有序的。
题意： 给出一些理财产品，对于每个理财产品，刚开始需要投入\(c_i\)的钱，之后每一天都会获得\(p_i\)的钱。 过了\(x\)天，一款理财产品带来的收益是\(xp_i - c_i\)。 现在问，如果选择理财产品，使得\(x\)天后的收益大于等于\(M\) 要满足\(x\)最小
思路： 二分\(x\)，那么每款理财产品的收益固定，贪心的取。view code
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int N = 1e5 + 10; int n, m, p[N], c[N]; bool check(ll x) { ll res = 0; for (int i = 1; i <= n; ++i) { ll t = 1ll * p[i] * x - c[i]; res += max(0ll, t); if (res >= m) return true; } return res >= m; } int main() { while (scanf("%d%d", &n, &m) != EOF) { for (int i = 1; i <= n; ++i) scanf("%d%d", p + i, c + i); ll l = 0, r = 2e9, res = 2e9; while (r - l >= 0) { ll mid = (l + r) >> 1; if (check(mid)) { r = mid - 1; res = mid; } else { l = mid + 1; } } printf("%lld\n", res); } return 0; }题意： 有一个长度为\(n\)的字符串环，里面只有'A', 'B', 'C'三种字符。 问最少要移动多少个字符，使得同类字符所在的位置的连续的。
思路： 枚举最终形态，那么如果一个位置最终形态对应的位置不是本身，那么这个字符要动。 维护三个前缀和\(O(1)\)算贡献。view code
#include <bits/stdc++.h> using namespace std; const int N = 1e5 + 10; int n, A[N], B[N], C[N]; char s[N]; int get(char c, int l, int r) { if (l > r) return 0; if (c == 'A') return (A[r] - A[l - 1]); else if (c == 'B') return (B[r] - B[l - 1]); return (C[r] - C[l - 1]); } int gao(string t) { int num[3]; for (int i = 0; i < 3; ++i) num[i] = get(t[i], 1, n); int res = 0; for (int i = 0; i <= num[0]; ++i) { res = max(res, get(t[0], 1, i) + get(t[1], i + 1, i + num[1]) + get(t[2], i + num[1] + 1, i + num[1] + num[2]) + get(t[0], i + num[1] + num[2] + 1, n)); } return n - res; } int main() { while (scanf("%d%s", &n, s + 1) != EOF) { memset(A, 0, sizeof A); memset(B, 0, sizeof B); memset(C, 0, sizeof C); for (int i = 1; i <= n; ++i) { A[i] = A[i - 1] + (s[i] == 'A'); B[i] = B[i - 1] + (s[i] == 'B'); C[i] = C[i - 1] + (s[i] == 'C'); } int res = 1e9; string t = "ABC"; do { res = min(res, gao(t)); } while (next_permutation(t.begin(), t.end())); printf("%d\n", res); } return 0; }题意： 有一张\(n\)个点\(m\)条边的有向图，每条边有边权，一个人在\(S\)点，它的左脑不想睡觉，它的右脑想睡觉。 两个脑袋轮流操作，每次操作在当前点选择一条出边往下走。 保证除了\(T\)点之外每个点都有出边，并且\(T\)没有出边。 问两个脑袋都最优操作，最终能否到\(T\)，能的话就输出到\(T\)的时间，不能的话就输出'infinity'
题意： 给出一张\(n\)个点\(m\)条边的无向图，每个点有\(p_i\)个人，有\(s(1 \leq s \leq 10)\)个保护区。 每个保护区有一个容量\(c_i\)，保证\(\sum c_i \geq \sum p_i\). 现在所有人都要到保护区，令所有人到保护区的最大时间最小。
思路： 二分答案，那么对于每个点，我们可以知道在这个答案下，这个点上的人可以到达哪些保护区。 那么用一个\(s\)的二进制状态表示它的可达状态，发现最多只有\(2^s\)种状态。 将同种状态的点都缩起来，网络流判断是否流量等于\(\sum p_i\)即可。view code
#include <bits/stdc++.h> using namespace std; using ll = long long; const int N = 2e5 + 10; const ll INFLL = 0x3f3f3f3f3f3f3f3f; struct Dicnic { static const int M = 2e6 + 10; static const int N = 1e4 + 10; struct Edge { int to, nxt; ll flow; Edge() {} Edge(int to, int nxt, ll flow): to(to), nxt(nxt), flow(flow) {} }edge[M]; int S, T; int head[N], tot; int dep[N]; void Init() { memset(head, -1, sizeof head); tot = 0; } void set(int _S, int _T) { S = _S; T = _T; } void addedge(int u, int v, ll w, ll rw = 0) { edge[tot] = Edge(v, head[u], w); head[u] = tot++; edge[tot] = Edge(u, head[v], rw); head[v] = tot++; } bool BFS() { memset(dep, -1, sizeof dep); queue<int>q; q.push(S); dep[S] = 1; while (!q.empty()) { int u = q.front(); q.pop(); for (int i = head[u]; ~i; i = edge[i].nxt) { if (edge[i].flow && dep[edge[i].to] == -1) { dep[edge[i].to] = dep[u] + 1; q.push(edge[i].to); } } } return dep[T] >= 0; } ll DFS(int u, ll f) { if (u == T || f == 0) { return f; } ll w, used = 0; for (int i = head[u]; ~i; i = edge[i].nxt) { if (edge[i].flow && dep[edge[i].to] == dep[u] + 1) { w = DFS(edge[i].to, min(f - used, edge[i].flow)); edge[i].flow -= w; edge[i ^ 1].flow += w; used += w; if (used == f) return f; } } if (!used) dep[u] = -1; return used; } ll solve() { ll res = 0; while (BFS()) { res += DFS(S, INFLL); } return res; } }dicnic; struct Edge { int to, nxt; ll w; Edge() {} Edge(int to, int nxt, ll w): to(to), nxt(nxt), w(w){} }edge[N << 2]; int n, m, s; int a[N], c[N], p[N]; int head[N], used[N], tot; ll dis[11][N]; void Init() { memset(head, -1, sizeof head); tot = 0; } void addedge(int u, int v, int w) { edge[tot] = Edge(v, head[u], w); head[u] = tot++; edge[tot] = Edge(u, head[v], w); head[v] = tot++; } struct qnode { int u; ll w; qnode() {} qnode(int u, ll w): u(u), w(w) {} bool operator < (const qnode &other) const { return w > other.w; } }; void Dij(int id, int S) { for (int i = 1; i <= n; ++i) { dis[id][i] = INFLL; used[i] = false; } dis[id][S] = 0; priority_queue<qnode> pq; pq.push(qnode(S, 0)); while (!pq.empty()) { int u = pq.top().u; pq.pop(); if (used[u]) continue; used[u] = true; for (int i = head[u]; ~i; i = edge[i].nxt) { int v = edge[i].to, w = edge[i].w; if (!used[v] && dis[id][v] > dis[id][u] + w) { dis[id][v] = dis[id][u] + w; pq.push(qnode(v, dis[id][v])); } } } } ll sum; ll mark[1 << 11]; bool check(ll x) { memset(mark, 0, sizeof mark); for (int i = 1; i <= n; ++i) { int S = 0; for (int j = 1; j <= s; ++j) { if (dis[j][i] <= x) { S |= 1 << (j - 1); } } mark[S] += p[i]; } dicnic.Init(); int S = (1 << s) + s + 10, T = S + 1, tmp = 1 << s; dicnic.set(S, T); for (int i = 0; i < tmp; ++i) { dicnic.addedge(S, i, mark[i]); for (int j = 0; j < s; ++j) { if (i & (1 << j)) { dicnic.addedge(i, j + tmp, mark[i]); } } } for (int i = (1 << s), j = 1; j <= s; ++j, ++i) { dicnic.addedge(i, T, c[j]); } ll res = dicnic.solve(); return res == sum; } int main() { while (scanf("%d %d %d", &n, &m, &s) != EOF) { Init(); sum = 0; for (int i = 1; i <= n; ++i) { scanf("%d", p + i); sum += p[i]; } for (int i = 1, u, v, w; i <= m; ++i) { scanf("%d %d %d", &u, &v, &w); addedge(u, v, w); } for (int i = 1; i <= s; ++i) { scanf("%d %d", a + i, c + i); } for (int i = 1; i <= s; ++i) { Dij(i, a[i]); } ll l = 0, r = INFLL, res = INFLL; while (r - l >= 0) { ll mid = (l + r) >> 1; if (check(mid)) { r = mid - 1; res = mid; } else { l = mid + 1; } } printf("%lld\n", res); } return 0; }题意： 给出四条边，问这四条边构成的四边形的最大面积
思路： 四边形是内接圆四边形时最大。view code
#include <bits/stdc++.h> using namespace std; using db = double; const db eps = 1e-8; int sgn(db x) { if (fabs(x) < eps) return 0; else return x > 0 ? 1 : -1; } inline db F(db a, db b, db c) { db p = (a + b + c) / 2.0; db res = sqrt(p * (p - a) * (p - b) * (p - c)); return res; } inline db f(db a, db b, db c, db d) { db res = 0.0; db l = max(fabs(a - b), fabs(c - d)); db r = min(fabs(a + b), fabs(c + d)); for (db e = l; e < r; e += 0.0005) { if (a + b - e <= 0) continue; if (a + e - b <= 0) continue; if (b + e - a <= 0) continue; if (c + d - e <= 0) continue; if (c + e - d <= 0) continue; if (d + e - a <= 0) continue; res = max(res, F(a, b, e) + F(c, d, e)); } return res; } int a, b, c, d; int main() { while (scanf("%d %d %d %d", &a, &b, &c, &d) != EOF) { if (a == b && b == c && c == d) { db res = a * b; printf("%.10f\n", res); continue; } db res = f(a, b, c, d); res = max(res, f(a, c, b, d)); res = max(res, f(a, d, b, c)); printf("%.15f\n", res); } return 0; }题意： 给出一棵树，有一个特殊点，现在可以额外加一些边，使得不管删去原树中的哪条边，每个点仍然可以到达特殊点view code
#include <bits/stdc++.h> using namespace std; int n, m; vector<vector<int> >G; vector<int> vec; void gao(int u, int fa) { if (G[u].size() == 1) { vec.push_back(u); return ; } for (auto &v : G[u]) if (v != fa){ gao(v, u); } } int main() { while (scanf("%d %d", &n, &m) != EOF) { G.clear(); G.resize(n); vec.clear(); for (int i = 1, u, v; i < n; ++i) { scanf("%d %d", &u, &v); G[u].push_back(v); G[v].push_back(u); } if (n == 2) { puts("1"); puts("0 1"); continue; } int rt = 0; for (int i = 0; i < n; ++i) { if (G[i].size() > 1) { rt = i; break; } } gao(rt, rt); int sze = vec.size(); int cnt = (sze + 1) / 2; printf("%d\n", cnt); for (int i = 0; i + cnt < sze; ++i) { printf("%d %d\n", vec[i], vec[i + cnt]); } if (sze & 1) { if (vec[cnt - 1] != m) { printf("%d %d\n", vec[cnt - 1], m); } else { printf("%d %d\n", vec[cnt - 1], vec[cnt - 2]); } } } return 0; }转载于:https://www.cnblogs.com/Dup4/p/11603310.html
