A、最小生成树
小 A 有一张 n 个点的带权无向图，这张无向图非常特别，首先第 i 个点有一个点权 ai，之后这张无向图是一张完全图，且边 (u,v) 的权值为 au+av 现在小 A 想找一个这张图的边权之和最小的生成树，需要你来帮帮他
题解： 每个点都和最小那个点连接形成的树即最小生成树 注意：使用长整形
AC代码：
#include<iostream> #include<algorithm> using namespace std; #define ll long long const int maxn = 1e5 + 15; ll a[maxn]; int main() { int n; cin >> n; for (int i = 0; i < n; i++) cin >> a[i]; sort(a, a + n); ll ans = 0; for (int i = 1; i < n; i++) ans += a[0] + a[i]; cout << ans << endl; return 0; }B、病毒感染 有一天clccle和rqy走在某个国家的街头上,机智的rqy却发现周围的行人不太对劲,他们嘴里念念有词,说着"sqn tql!",一边漫无目的的行走,clccle也发现了这一点,却惊讶的发觉这种奇怪的病毒会向周围的城市,最终会感染整个国家,因为网络已经崩溃,所以她们忘记了自己所在的城市,她们唯一知道的是这种病毒是从当前她们所在的城市开始传播的,并且这个国家的所有城市到这个城市的距离和最小（所有道路的距离都为1）,现在给定聪明的你一张整个国家的地图,请你帮rqy和clccle找到她们现在可能在这个国家的哪一个城市.
题解： 树的重心板子题
AC代码：
#include<iostream> #include<algorithm> #include<stdio.h> #include<vector> using namespace std; #define ll long long #define inf 0x3f3f3f3f const int maxn = 1e5 + 15; vector<int>G[maxn]; vector<int>ans[maxn]; int minn; int d[maxn]; int n, m; /* 树的重心求法：遍历所有点的子树的大小，然后重心存在的那个点就是最大子树最小的那个点 */ void dfs(int u, int fa) { d[u] = 1; int maxx = 0; for (int i = 0; i < G[u].size(); i++) { int v = G[u][i]; if (v != fa) { dfs(v, u); d[u] += d[v]; maxx = max(maxx, d[v]); } } maxx = max(maxx, n - d[u]); if (maxx <= minn) { minn = maxx; ans[minn].push_back(u); } } int main() { cin >> n >> m; for (int i = 0; i < m; i++) { int x, y; cin >> x >> y; G[x].push_back(y); G[y].push_back(x); } minn = inf; dfs(1, 0); sort(ans[minn].begin(), ans[minn].end()); for (int i = 0; i < ans[minn].size(); i++) cout << ans[minn][i] << " "; return 0; }C、Shooping 你要买n件物品，其中有一些是凳子。 商场正在举行促销活动，如果购物车中有至少一个凳子，那么你可以半价购买这个购物车中最贵的一个物品。 你有m辆购物车，请最小化你的花费。
题解： 找出min(m,凳子数量)，然后对前k大的物品进行打折就好
AC代码：
#include<iostream> #include<algorithm> #include<stdio.h> using namespace std; #define ll long long const int maxn = 1e3 + 15; bool cmp(double a, double b) { return a > b; } int main() { int t; cin >> t; while (t--) { double a[maxn]; int num = 0; int n, m; cin >> n >> m; int x; double ans = 0; for (int i = 0; i < n; i++) { cin >> a[i] >> x; ans += a[i]; if (x == 1) num++; } sort(a, a + n, cmp); for (int i = 0; i < min(num, m); i++) ans -= a[i] / 2; printf("%.1lf\n", ans); } return 0; }D、铺地毯 为了准备一个独特的颁奖典礼，组织者在会场的一片矩形区域（可看做是平面直角坐标系的第一象限）铺上一些矩形地毯。一共有n张地毯，编号从1到n。现在将这些地毯按照编号从小到大的顺序平行于坐标轴先后铺设，后铺的地毯覆盖在前面已经铺好的地毯之上。地毯铺设完成后，组织者想知道覆盖地面某个点的最上面的那张地毯的编号。注意：在矩形地毯边界和四个顶点上的点也算被地毯覆盖。
题解： 将所有地毯按顺序依次铺上，然后倒序查找最上面的即可
AC代码：
#include<iostream> #include<algorithm> using namespace std; #define ll long long const int maxn = 1e6 + 15; struct node { int a, b, g, k; }a[maxn]; int main() { int n; cin >> n; for (int i = 1; i <= n; i++) cin >> a[i].a >> a[i].b >> a[i].g >> a[i].k; int x, y; cin >> x >> y; int is_ok = 0; for (int i = n; i >= 1; i--) { if (a[i].a > x || a[i].b > y) continue; else if (x <= a[i].a + a[i].g && x >= a[i].a && y >= a[i].b && y <= a[i].b + a[i].k) { cout << i << endl; is_ok = 1; break; } } if (is_ok == 0) cout << -1 << endl; return 0; }E、金币陷阱 最近，奶牛们热衷于把金币包在面粉里，然后把它们烤成馅饼。第i块馅饼中含有Ni(1<=Ni<=25)块金币，并且，这个数字被醒目地标记在馅饼表面。 奶牛们把所有烤好的馅饼在草地上排成了一个R行(1<=R<=100)C列(1<=C<=100)的矩阵。你现在站在坐标为(1,1)的馅饼边上，当然，你可以拿到那块馅饼里的所有金币。你必须从现在的位置，走到草地的另一边，在坐标为(R,C)的馅饼旁边停止走动。每做一次移动，你必须走到下一列的某块馅饼旁边，并且，行数的变动不能超过1（也就是说，如果现在你站在坐标为(r,c)的馅饼边上，下一步你可以走到坐标为(r-1,c+1),(r,c+1),或者(r+1,c+1)的馅饼旁边）。当你从一块馅饼边经过，你就可以拿走馅饼里所有的金币。当然啦，你一定不会愿意因半路离开草地而失去唾手可得的金币，但，最终你一定得停在坐标为(R,C)的馅饼旁边。 现在，你拿到了一张标记着馅饼矩阵中，每一块馅饼含金币数量的表格。那么，按照规则，你最多可以拿到多少金币呢？
题解： 大佬们拿dp写的，卑微的我看不懂，只好裸dfs了
搜索代码：
#include<iostream> #include<algorithm> using namespace std; #define ll long long const int N = 1e2 + 5; #define inf 0x3f3f3f3f int a[N][N]; int vis[N][N]; int R, C; int dir[3][2] = { {0, 1}, {-1, 1}, {1, 1} }; int dfs(int x, int y) { if (x == R && y == C) return 0; if (vis[x][y]) return vis[x][y]; vis[x][y] = -inf; for (int i = 0; i < 3; i++) { int xx = x + dir[i][0]; int yy = y + dir[i][1]; if (xx >= 1 && xx <= R && yy >= 1 && yy <= C) vis[x][y] = max(vis[x][y], dfs(xx, yy) + a[xx][yy]); } return vis[x][y]; } int main() { cin >> R >> C; for (int i = 1; i <= R; i++) for (int j = 1; j <= C; j++) cin >> a[i][j]; int ans = dfs(1, 1) + a[1][1]; cout << ans << endl; return 0; }dp代码：
#include<iostream> #include<algorithm> #include<string.h> using namespace std; #define ll long long const int N = 1e2 + 5; #define inf 0x3f3f3f3f int a[N][N], dp[N][N]; int R, C; int main() { cin >> R >> C; for (int i = 1; i <= R; i++) for (int j = 1; j <= C; j++) cin >> a[i][j]; dp[1][1] = a[1][1]; for (int i = 2; i <= C; i++) { for (int j = 1; j <= R; j++) { if (dp[j][i - 1] != 0) dp[j][i] = max(dp[j][i], dp[j][i - 1] + a[j][i]); if (dp[j + 1][i - 1] != 0) dp[j][i] = max(dp[j][i], dp[j + 1][i - 1] + a[j][i]); if (dp[j - 1][i - 1] != 0) { dp[j][i] = max(dp[j][i], dp[j - 1][i - 1] + a[j][i]); } } } cout << dp[R][C] << endl; return 0; }