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;
}