A - 最小生成树

思路：贪心

首先，是完全图；其次，权值与点有关。
为了边权尽可能小，那么在联通的基础上找个点权最小的把其他点都连一起就可以了。
将点权排序，最小的点权*n-1加上其他点权和即为答案，记得开ll
时间复杂度：

反思

看见带权无向图求最小生成树别直接上来就写模板，写了半天完事后看通不过傻眼了。不说别的，就连存边的数组都开不下来，还怎么找最小树。

代码

#include <stdio.h>
#include <algorithm>
using namespace std;
typedef long long ll;
const int N = 1e5+20;
int a[N];
int main() {
    int n; scanf("%d", &n);
    for(int i = 1; i <= n; ++i) scanf("%d", &a[i]);
    sort(a + 1, a + n + 1);
    ll ans = 1ll * a[1] * (n - 2);
    for(int i = 1; i <= n; ++i) ans += 1ll * a[i];
    printf("%lld\n", ans);
    return 0;
}

B - 病毒感染

思路：树的重心，dfs

涉及树的重心，可参考以下资料：

https://oi-wiki.org/graph/tree-centroid/

简而言之，对于树上的每一个点，计算其所有子树中最大的子树节点数，这个值最小的点就是这棵树的重心。
性质之一：树中所有点到某个点的距离和中，到重心的距离和是最小的；如果有两个重心，那么到它们的距离和一样。
用dfs找一下子树中最大的节点数，最小的拿出来更新重心，注意重心不止一个
时间复杂度：

反思

最开始想到Dijkstra，但是如果对每个节点作为根计算一遍距离和找最小的，时间复杂度绝对会超时，后来看到重心才知道正解。

代码

#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;
const int N = 5e4+10;
vector<int> g[N], ans;
int sz[N], n, mn = 1e8;
void dfs(int v, int f) {
    sz[v] = 1;
    int mx = 0;
    for(auto u : g[v]) {
        if(u != f) {
            dfs(u, v);
            sz[v] += sz[u];
            mx = max(mx, sz[u]);
        }
    }
    mx = max(mx, n - sz[v]);
    if(mx < mn) {
        mn = mx; ans.clear(); ans.push_back(v);
    } else if(mx == mn) ans.push_back(v);
}
int main() {
    int m; scanf("%d%d", &n, &m);
    for(int i = 1; i <= m; ++i) {
        int a, b; scanf("%d%d", &a, &b);
        g[a].push_back(b); g[b].push_back(a);
    }
    dfs(1, 0);
    for(auto v : ans) printf("%d ", v);
    printf("\n");
    return 0;
}

C - Shopping

思路：贪心

根据凳子数和购物车数之间的大小关系，使尽可能多的物品可以半价购入，最多为cnt=min(num, m)，按a值排序后把后cnt个贵的物品按半价计算，其余全价计算
时间复杂度：

代码

#include <stdio.h>
#include <algorithm>
using namespace std;
const int N = 1e3+10;
struct Dz{
    int a, b;
    bool operator < (const Dz& d) const {
        return a < d.a;
    }
}dz[N];
int main() {
    int t; scanf("%d", &t);
    while(t--) {
        int n, m, num = 0; scanf("%d%d", &n, &m);
        for(int i = 1; i <= n; ++i) {
            scanf("%d%d", &dz[i].a, &dz[i].b);
            if(dz[i].b) num++;
        }
        sort(dz + 1, dz + n + 1);
        double ans = 0; int now = n;
        for(int i = 0; i < min(num, m); ++i)
            ans += (double)dz[now--].a / 2;
        while(now)
            ans += (double)dz[now--].a;
        printf("%.1f\n", ans);
    }
    return 0;
}

D - 铺地毯

思路：暴力

虽然暴力就可以过，但是别啥都暴力，比如别真开个N*N的数组挨个维护地毯编号n次，完全没必要，那样做明显超时
正确的暴力做法为先将n张地毯记下来，读入坐标后再遍历所有地毯，边界符合的最后一个即为答案，当然也可以反向遍历，那样答案就是第一个边界符合的地毯编号
时间复杂度：

代码

#include <stdio.h>
const int N = 1e4+20;
struct Dt{
    int a, b, g, k;
}dt[N];
int main() {
    int n, x, y, ans; scanf("%d", &n);
    for(int i = 1; i <= n; ++i)
        scanf("%d%d%d%d", &dt[i].a, &dt[i].b, &dt[i].g, &dt[i].k);
    scanf("%d%d", &x, &y);
    for(int i = 1; i <= n; ++i) {
        int x1 = dt[i].a, y1 = dt[i].b, x2 = x1 + dt[i].g, y2 = y1 + dt[i].k;
        if(x1 <= x && x2 >= x && y1 <= y && y2>= y) ans = i;
    }
    printf("%d\n", ans);
    return 0;
}

E - 金币馅饼

思路：动态规划

dp[i][j]表示在(i,j)位置可获得的最大金币数，由题意，状态由前一列相邻的3个位置更新而来：
注意由于初始站在(1,1)位置，所以在第2列到第r列间的更新要单独拿出来，毕竟dp[2][2]只能由dp[1][1]而不可能由dp[2][1]和dp[3][1]更新过来，也就是说除了边界外还不能超过某个限制，而后续的更新就只有边界限制了
时间复杂度：

代码

#include <stdio.h>
#include <algorithm>
using namespace std;
const int N = 1e2+10;
int a[N][N], dp[N][N];
int main() {
    int r, c; scanf("%d%d", &r, &c);
    for(int i = 1; i <= r; ++i)
        for(int j = 1; j <= c; ++j) {
            scanf("%d", &a[i][j]); dp[i][j] = 0;
        }
    dp[1][1] = a[1][1];
    for(int j = 2; j <= r; ++j)
        for(int i = 1; i <= j; ++i)
            for(int k = max(i - 1, 1); k <= min(i + 1, j); ++k)
                dp[i][j] = max(dp[i][j], dp[k][j - 1] + a[i][j]);
    for(int j = r + 1; j <= c; ++j)
        for(int i = 1; i <= r; ++i)
            for(int k = max(i - 1, 1); k <= min(i + 1, r); ++k)
                dp[i][j] = max(dp[i][j], dp[k][j - 1] + a[i][j]);
    printf("%d\n", dp[r][c]);
    return 0;
}