A
#include <bits/stdc++.h> using namespace std; const int maxn = 105; pair<int, int> arr[maxn]; map<int, int> mp; int main() { ios::sync_with_stdio(false); cin.tie(0); int n; cin >> n; bool flg = false; for(int i = 0; i < n; ++i) { int a, b; cin >> a >> b; arr[i].first = a, arr[i].second = b; if(mp.find(a + b) != mp.end()) { int id = mp[a + b]; if(arr[id].first + arr[id].second == a) flg = true; } mp[a] = i; } if(flg) cout << "YE5" << endl; else cout << "N0" << endl; }B 输出小数后k1到k2位，因为k2过大，不能暴力 但是k2-k1<=1e5，我们处理出第k1位然后暴力即可，快速幂(a%m)*10
#include <bits/stdc++.h> using namespace std; typedef long long ll; ll m, n; ll qpow(ll b) { ll res = m, a = 10 % n; while(b) { if(b & 1) res = res * a % n; b >>= 1; a = a * a % n; } return res; } int main() { int t; scanf("%d", &t); while(t--) { int k1, k2; scanf("%lld%lld%d%d", &m, &n, &k1, &k2); if(n == m) { for(int i = k1; i <= k2; ++i) printf("0"); printf("\n"); } else { if(k1 == 1) { ll tmp = m; for(int i = k1; i <= k2; ++i) { printf("%lld", tmp * 10 / n); tmp = (tmp * 10) % n; } printf("\n"); } else { ll tmp = qpow(k1 - 1); for(int i = k1; i <= k2; ++i) { printf("%lld", tmp * 10 / n); tmp = (tmp * 10) % n; } printf("\n"); } } } }C 最小生成树 注意卡常优化：结合并查集的路径压缩与启发式合并https://blog.csdn.net/qq_27121257/article/details/77185604
#include <bits/stdc++.h> using namespace std; typedef long long ll; inline void read(int &x){ int data = 0, w = 1; char ch = getchar(); while(ch != '-' && !isdigit(ch)) ch = getchar(); if(ch == '-') w = -1, ch = getchar(); while(isdigit(ch)) data = 10 * data + ch - '0', ch = getchar(); x = data * w; } inline void readll(ll &x){ ll data = 0; int w = 1; char ch = getchar(); while(ch != '-' && !isdigit(ch)) ch = getchar(); if(ch == '-') w = -1, ch = getchar(); while(isdigit(ch)) data = 10 * data + ch - '0', ch = getchar(); x = data * w; } const int maxn = 1e6 + 5; int T[maxn], fa[maxn]; int find(int x) { return x == fa[x] ? x : fa[x] = find(fa[x]); } void merge(int a, int b) { fa[find(a)] = find(b); } struct node { int u, v; ll c; bool operator <(const node& x) const { return c > x.c; } }; priority_queue<node> Q; int vis[maxn]; vector<pair<int, int>>E[maxn]; int main() { int n, m, k; ll t; read(n), read(m), read(k), readll(t); for(int i = 1; i <= n + 1; ++i) fa[i] = i; for(int i = 2; i <= n + 1; ++i) { read(T[i]); Q.push((node){1, i, T[i]}); } for(int i = 0; i < k; ++i) { int x; read(x); Q.push((node){1, x + 1, 0}); } for(int i = 0; i < m; ++i) { int u, v, c; read(u), read(v), read(c); E[u + 1].push_back(make_pair(v + 1, c)); E[v + 1].push_back(make_pair(u + 1, c)); } ll ans = 0; while(!Q.empty()) { node top = Q.top(); Q.pop(); int u = top.u, v = top.v; if(find(u) == find(v)) continue; merge(u, v); ans += top.c; if(!vis[u]) { for(int i = 0; i < E[u].size(); ++i) { if(!vis[E[u][i].first]) Q.push((node){u, E[u][i].first, E[u][i].second}); } vis[u] = 1; } if(!vis[v]) { for(int i = 0; i < E[v].size(); ++i) { if(!vis[E[v][i].first]) Q.push((node){v, E[v][i].first, E[v][i].second}); } vis[v] = 1; } } if(ans <= t) puts("Yes"); else puts("No"); }D 网络流 根据题意将每个点分为i和i’，建立源点到每个点i的容量为vi的边，建立i’到汇点的容量为wi的边；需要输出所有边中的最大边：二分+floyd处理即可。
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int maxn = 1e3 + 5; const int maxm = 1e5 + 5; const int inf = 0x3f3f3f3f; const ll INF = 10000000000000; struct Edge { int from, to, cap, flow; Edge() {} Edge(int f, int t, int c, int fl) { from = f, to = t, cap = c, flow = fl; } }; struct Dinic{ int n, m, s, t; vector<Edge> edges; vector<int> g[maxn]; bool vis[maxn]; int d[maxn]; int cur[maxn]; void init(int n){ this->n = n; for(int i = 0; i < n; i++) g[i].clear(); edges.clear(); } void AddEdge(int from, int to, int cap){ edges.push_back(Edge(from, to, cap, 0)); edges.push_back(Edge(to, from, 0, 0));//反向弧 m = edges.size(); g[from].push_back(m - 2); g[to].push_back(m - 1); } bool Bfs(){ memset(vis, 0, sizeof(vis)); queue<int> q; q.push(s); d[s] = 0; vis[s] = 1; while(!q.empty()){ int x = q.front(); q.pop(); for(int i = 0; i < (int)g[x].size(); i++){ Edge &e = edges[g[x][i]]; if(!vis[e.to] && e.cap > e.flow){ vis[e.to] = 1; d[e.to] = d[x] + 1; q.push(e.to); } } } return vis[t]; } int Dfs(int x, int a){ if(x == t || a == 0) return a; int flow = 0, f; for(int& i = cur[x]; i < (int)g[x].size(); i++){ Edge &e = edges[g[x][i]]; if(d[x] + 1 == d[e.to] && (f = Dfs(e.to, min(a, e.cap - e.flow))) > 0){ e.flow += f; edges[g[x][i]^1].flow -= f; flow += f; a -= f; if(a == 0) break; } } return flow; } int Maxflow(int s, int t){ this->s = s; this->t = t; int flow = 0; while(Bfs()){ memset(cur, 0, sizeof(cur)); flow += Dfs(s, inf); } return flow; } } dc; int vi[maxn], wi[maxn]; ll dis[maxn][maxn]; set<ll> mp; ll arr[maxm]; int n, m, sum; bool check(ll x) { dc.init(n + n + 2); for(int i = 1; i <= n; ++i) { dc.AddEdge(0, i, vi[i]); dc.AddEdge(n + i, n + n + 1, wi[i]); } for(int i = 1; i <= n; ++i) for(int j = 1; j <= n; ++j) if(dis[i][j] <= x) dc.AddEdge(i, n + j, sum); if(dc.Maxflow(0, n + n + 1) == sum) return true; else return false; } int main() { sum = 0; scanf("%d%d", &n, &m); for(int i = 1; i <= n; ++i) for(int j = 1; j <= n; ++j) dis[i][j] = INF; for(int i = 1; i <= n; ++i) { scanf("%d%d", &vi[i], &wi[i]); sum += vi[i]; } for(int i = 0; i < m; ++i) { int u, v, w; scanf("%d%d%d", &u, &v, &w); if(u != v) dis[u][v] = dis[v][u] = min(dis[u][v], w * 1ll); } for(int i = 1; i <= n; ++i) dis[i][i] = 0; for(int k = 1; k <= n; ++k) { for(int i = 1; i <= n; ++i) { for(int j = 1; j <= n; ++j) { dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]); } } } for(int i = 1; i <= n; ++i) { for(int j = 1; j <= n; ++j) { if(dis[i][j] != INF) mp.insert(dis[i][j]); } } int tot = 0; for(set<ll>::iterator it = mp.begin(); it != mp.end(); ++it) { arr[tot++] = *it; } bool flg = false; int l = 0, r = tot; while(l < r) { int mid = l + r >> 1; if(check(arr[mid])) flg = true, r = mid; else l = mid + 1; } printf("%lld\n", flg ? arr[l] : -1); }