A

n和m可以相等,直接输出n

B

贪心,最大值和所有值相连即可

C

只要距离终点的曼哈顿距离小于等于max(n,m)即可

{
    int n,m,k;
    cin>>n>>m>>k;
    vector<array<int,2>>b(k+1);
    for(int i=1;i<=k;i++)
        cin>>b[i][0]>>b[i][1];
    int tx,ty;
    tx=(n+1)/2;
    ty=(m+1)/2;
    int ans=max(n/2,m/2);
    int sum=0;
    for(int i=1;i<=k;i++)
        if(abs(b[i][0]-tx)+abs(b[i][1]-ty)<=ans)
            sum++;
    cout<<sum;
}

D

分组背包(背包问题)https://www.luogu.com.cn/training/5197

void solve() {
    int n, m;
    cin >> n >> m;
    vector<int> dp(m + 1, 0);  // dp[j] 表示使用j点体力时的最大收益
    
    // 遍历每个模式(分组背包中的每个组)
    for (int i = 1; i <= n; i++) {
        int a;
        cin >> a;  // 当前模式有a种操作
        
        vector<int> w(a + 1), val(a + 1);  // 操作消耗的体力和对应收益
        
        // 读取操作的收益值(注意题目描述中先给出的是收益值)
        for (int j = 1; j <= a; j++) cin >> val[j];
        
        // 读取操作的体力消耗值(后给出的是体力消耗)
        for (int j = 1; j <= a; j++) cin >> w[j];
        
        // 分组背包核心逻辑:逆序更新防止重复选择
        for (int j = m; j >= 0; j--) {  // 遍历所有可能的体力值
            for (int k = 1; k <= a; k++) {  // 遍历当前模式的所有操作
                if (j >= w[k]) {  // 体力足够选择该操作时
                    dp[j] = max(dp[j], dp[j - w[k]] + val[k]);
                }
            }
        }
    }
    cout << dp[m] << endl;  // 输出使用m点体力时的最大收益
}

E

并查集板题(不会的去学)https://www.luogu.com.cn/problem/P3367

int b[N];
int find(int x){
    if(x==b[x]) return x;
    return b[x]=find(b[x]);
}
void solve()
{
	int n;
    cin>>n;
    vector<int>a(n+1);
    for(int i=1;i<=n;i++) b[i]=i;
    for(int i=1;i<=n;i++) {
        cin>>a[i];
        int fa=find(i);
        int fb=find(a[i]);
        if(fa!=fb) b[fa]=fb;
    }
    int sum=0;
    for(int i=1;i<=n;i++) 
        if(b[i]==i) sum++;
    cout<<sum<<endl;
}

F

牛客周赛85原题 二分答案(有官方题解)

G

贪心加带权并查集

using namespace std;

const int MAXN = 1e5 + 5;
int g[MAXN], num[MAXN]; // 并查集数组,num记录每个连通块的大小

// 并查集查找根节点,路径压缩优化
int find(int x) {
    if (x == g[x]) return x;
    return g[x] = find(g[x]);
}

void solve() {
    int n;
    cin >> n;
    vector<array<int, 3>> a; // 存储边,格式为{权重, 顶点u, 顶点v}
    for (int i = 1; i < n; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        a.push_back({w, u, v});
    }
    // 将边按权重从小到大排序
    sort(a.begin(), a.end());
    
    // 初始化并查集,每个顶点初始为独立连通块,大小为1
    for (int i = 1; i <= n; i++) {
        g[i] = i;
        num[i] = 1;
    }
    
    long long ans = 0;
    for (auto [z, x, y] : a) { // 遍历每条边,z为权重,x和y为顶点
        int f = find(x);        // 查找x所在连通块的根
        int ff = find(y);       // 查找y所在连通块的根
        // 累加当前边的贡献:两个连通块大小的乘积 × 边权重
        ans += 1LL * num[f] * num[ff] * z;
        // 合并两个连通块,将较小的连通块合并到较大的(此处顺序不影响结果)
        // 更新父节点和连通块大小
        num[f] += num[ff];
        g[ff] = f; // 将ff的父节点指向f
    }
    cout << ans << endl;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    solve();
    return 0;
}