codeforces round974 div3 分层图 树形dp
A Robin Helps
问题：
思路：模拟
代码：
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
void solve() {
int n, k;
cin >> n >> k;
vector<int> a(n + 1);
for(int i = 1; i <= n; i ++ ) cin >> a[i];
int sum = 0;
int cnt = 0;
for(int i = 1; i <= n; i ++ ) {
if(a[i] >= k) sum += a[i];
else if(a[i] == 0 && sum != 0) {
sum --;
cnt ++;
}
}
cout << cnt << endl;
}
int main() {
int t;
cin >> t;
while(t -- ) solve();
}
/*
2
1
-1
4
2
-1
*/ B Robin Hood and the Major Oak
问题：
思路：注意到的奇偶性只与
有关 因此前
天树叶的和的奇偶性我们可以很容易的得到，并且叶子只能存活m天，所以只需判断
到
天叶子的奇偶性即可
代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5 + 10;
void solve() {
int n, k;
cin >> n >> k;
/*vector<ll> a(N + 1);
for(int i = 1; i <= n / i; i ++ ) a[i] = i * i;*/
int num = 0;
if(n & 1) num = (n + 1) / 2;
else num = n / 2;
int num1 = 0;
if((n - k) & 1) num1 = (max(0, (n - k)) + 1) / 2;
else num1 = max(0, (n - k)) / 2;
if((num0 - num1) & 1) cout << "NO\n";
else cout << "YES\n";
}
int main() {
int t;
cin >> t;
while(t -- ) solve();
}C Robin Hood in Town
思路：
二分答案，然后在check函数中判断这个结果是否可行
代码：
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
const double eps = 1e-8;
void solve() {
int n;
cin >> n;
vector<long long> a(n + 1);
for(int i = 1; i <= n; i ++ ) cin >> a[i];
sort(a.begin() + 1, a.end());
auto check = [&](long long mid) {
//mid = 0;
a[n] += mid;
double sum = 0;
for(int i = 1; i <= n; i ++ ) sum += a[i];
int cnt = 0;
double avg = sum / n;
avg /= 2;
for(int i = 1; i <= n; i ++ ) {
if(a[i] + eps < avg) cnt ++;
}
a[n] -= mid;
//cout << cnt << " ";
return cnt >= n / 2 + 1;
};
//check(0);
//if(check(0)) cout << 11111;
long long l = 0, r = 1e16;
while(l < r) {
long long mid = l + r >> 1;
if(check(mid)) r = mid;
else l = mid + 1;
}
if(check(l)) cout << l << "\n";
else cout << "-1\n";
}
int main() {
int t;
cin >> t;
while(t -- ) solve();
}D robert hood and mrs hood
问题：
思路：
这道题目本质上是求一段区间内，最多和最少能包含多少个事件。首先可以通过差分的方式求出每个时间点当前包含多少事件，然后从该点开始向后扫描要扫描的区间长度，每碰见一个事件开始的左端点那么该段区间内事件数加1，第二层循环可以用前缀和优化掉，预处理出每个点之前有多少事件开始的左端点。
代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5 + 10;
const double eps = 1e-8;
void solve() {
int n, d, k;
cin >> n >> d >> k;
vector<pair<int, int>> a(k + 1);
for(int i = 1; i <= k; i ++ ) {
int l, r;
cin >> l >> r;
a[i] = {l, r};
}
sort(a.begin() + 1, a.end());
vector<ll> diff(n + 2);//每个点被几个区间覆盖
for(int i = 1; i <= k; i ++ ) {
int l = a[i].first;
int r = a[i].second;
diff[l] += 1;
diff[r + 1] -= 1;
}
for(int i = 1; i <= n; i ++ ) diff[i] += diff[i - 1];
vector<ll> sum(n + 1);
for(int i = 1; i <= k; i ++ ) {
sum[a[i].first] ++;
}
/*for(int i = 1; i <= n; i ++ ) cout << sum[i] << " ";
cout << endl;
for(int i = 1; i <= n; i ++ ) cout << diff[i] << " ";*/
for(int i = 1; i <= n; i ++ ) sum[i] += sum[i - 1];
ll minv = 0x3f3f3f3f, maxv = 0;
int pos1 = 1, pos2 = 1;
for(int i = 1; i <= n - d + 1; i ++ ) {
ll num = sum[i + d - 1] - sum[i] + diff[i];
if(num > maxv) {
maxv = num;
pos1 = i;
}
if(num < minv) {
minv = num;
pos2 = i;
}
}
cout << pos1 << " " << pos2 << endl;
}
int main() {
int t;
cin >> t;
while(t -- ) solve();
}E Rendez-vous de Marian et Robin
问题：
思路：分层图，第一层图的边权为均为w，第二层图的边权均为w / 2，第一层图的点i与第二层图的点i + n对应，由于骑上马之后一定比骑上马再下马更优，因此两层图之间用单向边连接，即，如果在点i上有马，那么就在i与i + n之间连一条边权为0的单向边。最后从点1和点n分别跑dijkstra即可。最后一个点的最短时间就是min(dis[i], dis[i + n])。记得开long long
代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
void solve() {
int n, m, h;
cin >> n >> m >> h;
vector<vector<pair<int, int>>> adj(2 * n + 1);
for(int i = 1; i <= h; i ++ ) {
int x;
cin >> x;
adj[x].push_back({x + n, 0});
}
while(m -- ) {
int u, v, w;
cin >> u >> v >> w;
adj[u].push_back({v, w});
adj[v].push_back({u, w});
adj[u + n].push_back({v + n, w / 2});
adj[v + n].push_back({u + n, w / 2});
}
vector<bool> st(2 * n + 1);
auto dijkstra = [&](int start, vector<ll> &dis) {
dis[start] = 0;
priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<>> q;
q.push({0ll, start});
while(!q.empty()) {
auto t = q.top();
q.pop();
ll dist = t.first, ver = t.second;
if(st[ver]) continue;
st[ver] = true;
for(auto t: adj[ver]) {
if(dis[t.first] > dist + t.second) {
dis[t.first] = dist + t.second;
q.push({dis[t.first], t.first});
}
}
}
};
vector<ll> dis(2 * n + 1, 1e18), redis(2 * n + 1, 0x3f3f3f3f);
dijkstra(1, dis);
for(int i = 1; i <= 2 * n; i ++ ) st[i] = false;
dijkstra(n, redis);
ll ans = 1e18;
for(int i = 1; i <= n; i ++ ) {
ans = min(ans, max(min(dis[i], dis[i + n]), min(redis[i], redis[i + n])));
}
if(ans == 1e18) cout << "-1\n";
else cout << ans << "\n";
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int t;
cin >> t;
while(t -- ) solve();
return 0;
}F sheriff's defences
问题：
思路：首先注意到这个图只有n - 1条边，并且是连通的，也就是说这是一棵树。然后对于一个点，如果这是一个单独被保护起来的点，那么这个点对答案的贡献实际上就是自身拥有的gold。如果这是多个连续的被保护的点，这里以两个点为例，对答案的贡献就是gold - c - c其中一个c表示本身被相邻的点抢走的gold，另一个c表示相邻那个点被这个点抢走的gold。这就和没有上司的舞会差不多了，dp[i][2]表示第i个营地我是否保护，dp[i][0]表示不保护， dp[i][1]表示保护
那么状态转移可表示为：
代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
void solve() {
int n, c;
cin >> n >> c;
vector<ll> a(n + 1);
for(int i = 1; i <= n; i ++ ) cin >> a[i];
vector<vector<int>> adj(n + 1);
for(int i = 1; i <= n - 1; i ++ ) {
int u, v;
cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
}
vector<vector<ll>> dp((n + 1), vector<ll>(3));
function<void(int, int)> dfs = [&](int u, int fa) -> void {
dp[u][1] = a[u];
for(auto t: adj[u]) {
if(t == fa) continue;
dfs(t, u);
dp[u][0] += max(dp[t][1], dp[t][0]);
dp[u][1] += max(dp[t][0], dp[t][1] - 2 * c);
}
};
dfs(1, 1);
cout << max(dp[1][1], dp[1][0]) << "\n";
}
int main() {
ios::sync_with_stdio(false);
int t;
cin >> t;
cin.tie(0), cout.tie(0);
while(t -- ) solve();
return 0;
}原文地址：https://blog.csdn.net/2201_75845839/article/details/142467310
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！