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