A
B
C
等比数列的性质，前面的i项的和，不会超过第i+1项
D
有若干个区间，要求每一个点被区间覆盖的次数不能超过k个。问移除的最少的区间的数目。
贪心：
若某个点被覆盖了k次以上，那么肯定是移除这些区间里面右端点最右的点的区间。
时间复杂度要求是(O(nlog(n)))
模拟就好了
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<queue>
#include<cmath>
#include<map>
#include<stack>
#include<set>
#include<bitset>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
#define pb(x) push_back(x)
#define cls(x, val) memset(x, val, sizeof(x))
#define fi first
#define se second
#define mp(x, y) make_pair(x, y)
#define inc(i, l, r) for(int i=l; i<=r; i++)
const int inf = 0x3f3f3f3f;
const int maxn = 2e5+10;
int l[maxn], r[maxn];
int n, k;
vector<int> node[maxn];
set<pii> s;
int main(){
ios::sync_with_stdio(false);
cin>>n>>k;
for(int i=1; i<=n; i++){
cin>>l[i]>>r[i];
node[l[i]].push_back(i);
node[r[i]+1].push_back(-i);
}
vector<int> ans;
for(int i=1; i<=2e5; i++){
for(int j=0; j<node[i].size(); j++){
int u = node[i][j];
if(u>0){
s.insert(mp(r[u], u));
}
else s.erase(mp(r[-u], -u));
}
while(s.size()>k){
set<pii>::iterator it = s.end();
--it;
ans.push_back(it->se);
s.erase(*it);
}
}
cout<<ans.size()<<endl;
for(int i=0; i<ans.size(); i++){
cout<<abs(ans[i])<<" ";
}
cout<<endl;
return 0;
}
E
简单dp
F
题目：
要求一个点的集合，使得他们之间的任意两点之间的距离大于k,并且这个集合的点的权重和最大
树形dp
学习了一种很trick的写法，不具有普遍性
#include <bits/stdc++.h>
using namespace std;
const int maxn = 200 + 10;
vector<int> G[maxn];
int n, k, m;
int a[maxn], vis[maxn];
void dfs(int u, int fa, int d){
if(d > k) return ;
a[u] -= m;
for(int &v : G[u]) if(v != fa) dfs(v, u, d + 1);
}
int main(){
scanf("%d%d", &n, &k);
for(int i = 1; i <= n; i++) scanf("%d", a + i);
for(int i = 1; i < n; i++){
int u, v;
scanf("%d%d", &u, &v);
G[u].push_back(v);
G[v].push_back(u);
}
queue<int> q;
vector<int> b;
q.push(1); vis[1] = 1;
while(!q.empty()){
int u = q.front(); q.pop();
b.push_back(u);
for(int &v : G[u]){
if(!vis[v]){
q.push(v);
vis[v] = 1;
}
}
}
int ans = 0;
for(int i = b.size() - 1; i >= 0; i--){
//这里写的很trick, 从叶子节点开始取。若上面有更好的选择，那么相当于就叶子的贡献转移到上面了。
m = a[b[i]];
if(m < 0) continue;
ans += m;
dfs(b[i], 0, 0);
}
printf("%d
", ans);
return 0;
}
树形dp的写法有点像另外的一个题目：
给一个树形的结构，然后任意一个节点到关键节点的距离不能超过k。
问最小的关键节点的数目。
#include <bits/stdc++.h>
using namespace std;
const int N = 210;
int n, k;
vector<int> a;
vector<vector<int>> g, dp;
void dfs(int v, int p) {
dp[v][0] = a[v];
for (auto to : g[v]) {
if (to != p) dfs(to, v);
}
for (int dep = 0; dep < N; ++dep) {
if (dep == 0) {
for (auto to : g[v]) {
if (to == p) continue;
dp[v][dep] += dp[to][max(0, k - dep - 1)];
}
} else {
for (auto to : g[v]) {
if (to == p) continue;
int cur = dp[to][dep - 1];
for (auto other : g[v]) {
if (other == p || other == to) continue;
cur += dp[other][max(dep - 1, k - dep - 1)];
}
dp[v][dep] = max(dp[v][dep], cur);
}
}
}
for (int dep = N - 1; dep > 0; --dep) {
dp[v][dep - 1] = max(dp[v][dep - 1], dp[v][dep]);
}
}
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
#endif
cin >> n >> k;
++k;
a = vector<int>(n);
for (int i = 0; i < n; ++i) {
cin >> a[i];
}
g = vector<vector<int>>(n);
for (int i = 0; i < n - 1; ++i) {
int x, y;
cin >> x >> y;
--x, --y;
g[x].push_back(y);
g[y].push_back(x);
}
dp = vector<vector<int>>(n, vector<int>(N));
dfs(0, -1);
cout << dp[0][0] << endl;
return 0;
}