本文共 10353 字，大约阅读时间需要 34 分钟。
给定三个变量 a、b、c，定义 x = max(a, b)，y = max(a, c)，z = max(b, c)。要求找出任意一组符合条件的 a、b、c。
#include#include #include #include using namespace std;int main() { // 读取输入 const int bufSize = 1e6; inline char nc() { #ifdef DEBUG return getchar(); #endif static char buf[bufSize], *p1 = buf, *p2 = buf; return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, bufSize, stdin), p1 == p2) ? EOF : *p1++; } inline void read(char *s) { static char c; for (; !isalpha(c); c = nc()); for (; isalpha(c); c = nc()) *s++ = c; *s = '\0'; } template inline t read(t &r) { static char c; static int flag; flag = 1, r = 0; for (c = nc(); !isdigit(c); c = nc()) if (c == '-') flag = -1; for (; isdigit(c); c = nc()) r = r * 10 + c - 48; return r *= flag; } int T; int a[4]; int main() { read(T); while (T--) { for (int i = 1; i <= 3; ++i) read(a[i]); sort(a + 1, a + 4); if (a[1] == a[2] && a[2] == a[3]) { puts("YES"); printf("%d %d %d\n", a[3], a[2], 1); } else { puts("NO"); } } return 0; }}
read 函数读取输入数据，处理大输入的情况。给定一个数组，通过删除某些元素使得剩余元素形成一个非递减序列。
#include#include #include #include using namespace std;int main() { const int bufSize = 1e6; inline char nc() { #ifdef DEBUG return getchar(); #endif static char buf[bufSize], *p1 = buf, *p2 = buf; return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, bufSize, stdin), p1 == p2) ? EOF : *p1++; } inline void read(char *s) { static char c; for (; !isalpha(c); c = nc()); for (; isalpha(c); c = nc()) *s++ = c; *s = '\0'; } template inline t read(t &r) { static char c; static int flag; flag = 1, r = 0; for (c = nc(); !isdigit(c); c = nc()) if (c == '-') flag = -1; for (; isdigit(c); c = nc()) r = r * 10 + c - 48; return r *= flag; } int T, n; vector a, vis; int main() { read(T); while (T--) { read(n); a.clear(); vis.resize(n + 1, 0); for (int i = 1; i <= n; ++i) { int x; read(x); if (!vis[x]) { vis[x] = 1; a.push_back(x); } } for (int i = 1; i <= n; ++i) { if (vis[i] == 1) { printf("%d ", i); } } putchar('\n'); } return 0; }}
vis 数组记录已访问的元素，避免重复。给定一个数组，要求每次取头尾元素，所取元素单调不减。
#include#include #include #include using namespace std;int main() { const int bufSize = 1e6; inline char nc() { #ifdef DEBUG return getchar(); #endif static char buf[bufSize], *p1 = buf, *p2 = buf; return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, bufSize, stdin), p1 == p2) ? EOF : *p1++; } inline void read(char *s) { static char c; for (; !isalpha(c); c = nc()); for (; isalpha(c); c = nc()) *s++ = c; *s = '\0'; } template inline t read(t &r) { static char c; static int flag; flag = 1, r = 0; for (c = nc(); !isdigit(c); c = nc()) if (c == '-') flag = -1; for (; isdigit(c); c = nc()) r = r * 10 + c - 48; return r *= flag; } int T, n; vector a; int main() { read(T); while (T--) { read(n); a.resize(n + 1); for (int i = 1; i <= n; ++i) { int x; read(x); a[i] = x; } int top = n; while (top > 1 && a[top - 1] >= a[top]) --top; int head = top; while (head > 1 && a[head - 1] <= a[head]) --head; if (head == 1) { puts("1\n"); } else { puts(to_string(head - 1) + "\n"); } } return 0; }}
给定一个字符串，找出最少删除次数使其成为好串。
#include#include #include #include using namespace std;int main() { const int bufSize = 1e6; inline char nc() { #ifdef DEBUG return getchar(); #endif static char buf[bufSize], *p1 = buf, *p2 = buf; return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, bufSize, stdin), p1 == p2) ? EOF : *p1++; } inline void read(char *s) { static char c; for (; !isalpha(c); c = nc()); for (; isalpha(c); c = nc()) *s++ = c; *s = '\0'; } template inline t read(t &r) { static char c; static int flag; flag = 1, r = 0; for (c = nc(); !isdigit(c); c = nc()) if (c == '-') flag = -1; for (; isdigit(c); c = nc()) r = r * 10 + c - 48; return r *= flag; } int T, n; string s; int main() { read(T); while (T--) { read(n); s.resize(n + 1); for (int i = 1; i <= n; ++i) { char c; read(c); s[i] = c; s[i] -= 'a'; } vector > sum(n + 1, vector (26, 0)); for (int i = 1; i <= n; ++i) { sum[i][s[i]]++; for (int j = 0; j < 26; ++j) { sum[i][j] += sum[i - 1][j]; } } auto solve = [&](int l, int r, int c) -> int { if (l == r) return (s[l] != c); int mid = l + r > 1 ? (l + r) / 2 : l; int left = solve(l, mid, c + 1); int right = solve(mid + 1, r, c + 1); int lval = left + (r - mid) - sum[mid][c]; int rval = right + (mid - l + 1) - (sum[mid][c] - sum[l - 1][c]); return min(lval, rval); }; int res = solve(1, n, 0); printf("%lld\n", res); } return 0; }}
给定一个有向图和无向边，判断是否可以转换为有向无环图。
#include#include #include #include using namespace std;int main() { const int bufSize = 1e6; inline char nc() { #ifdef DEBUG return getchar(); #endif static char buf[bufSize], *p1 = buf, *p2 = buf; return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, bufSize, stdin), p1 == p2) ? EOF : *p1++; } inline void read(char *s) { static char c; for (; !isalpha(c); c = nc()); for (; isalpha(c); c = nc()) *s++ = c; *s = '\0'; } template inline t read(t &r) { static char c; static int flag; flag = 1, r = 0; for (c = nc(); !isdigit(c); c = nc()) if (c == '-') flag = -1; for (; isdigit(c); c = nc()) r = r * 10 + c - 48; return r *= flag; } int T, n, m; struct edge { int to, next; bool directed; }; edge E[maxm + 1]; int head[n + 1], tot; int in[n + 1]; void topo() { int qh = 1, qt = 0; for (int i = 1; i <= n; ++i) if (!in[i]) q[++qt] = i; while (qt > qh) { if (ans) return; int u = q[qh++]; for (int p = head[u]; p; p = E[p].next) { int v = E[p].to; if (!E[p].directed) continue; if (--in[v] == 0) q[++qt] = v; if (in[v] < 0) ans = 1; } } } int main() { read(T); while (T--) { ans = tot = 0; read(n), read(m); for (int i = 1; i <= n; ++i) { vis[i] = 0, head[i] = 0, in[i] = 0; } for (int i = 1; i <= m; ++i) { int t, a, b; read(t), read(a), read(b); add(a, b, t); if (t) in[b]++; } topo(); if (ans) { puts("NO"); continue; } for (int i = 1; i <= n; ++i) { if (!id[i] || vis[i] != 1) { puts("NO"); goto end; } } puts("YES"); for (int i = 1; i <= m; ++i) { if (E[i].directed) { printf("%d %d\n", E[i].from, E[i].to); } else if (id[E[i].from] < id[E[i].to]) { printf("%d %d\n", E[i].from, E[i].to); } else { printf("%d %d\n", E[i].to, E[i].from); } } end:; return 0; }}
给定一个树，删除叶子节点，使得树变成链状结构。
#include#include #include #include #include #include using namespace std;int main() { vector fa, sonnum, leafnum; struct node { int x; int id; int type; bool operator<(const node &that) const { if (type != that.type) return type > that.type; return leafnum[id] > leafnum[that.id]; } }; int T, n, k; vector E; vector head; queue q; vector vis; int maxn = 2e5 + 100; int main() { read(T); while (T--) { tot = 0; read(n), read(k); fa.resize(n + 1, 0); sonnum.resize(n + 1, 0); leafnum.resize(n + 1, 0); while (!q.empty()) q.pop(); for (int i = 1; i <= n; ++i) { int a, b; read(a), read(b); add(a, b); add(b, a); } for (int i = 1; i <= n; ++i) { if (!head[i]) { fa[i] = i; for (int p = head[i]; p; p = E[p].next) { int v = E[p].to; if (v != fa[i]) { fa[v] = i; sonnum[i]++; } } if (sonnum[i] == leafnum[i]) { node t; t.x = leafnum[i]; t.id = i; t.type = 0; vis[i] = q.push(t); } else if (leafnum[i]) { node t; t.x = leafnum[i]; t.id = i; t.type = 1; vis[i] = q.push(t); } } } int ans = 0; while (take(k)) ++ans; printf("%d\n", ans); } return 0; }}
通过以上解析和实现，可以逐一解决每个小题的要求，确保代码的正确性和效率。
转载地址：http://mpwvz.baihongyu.com/