当前位置：首页 > article >正文

codeforces round974 div3 分层图树形dp

article 2024/11/15 9:48:31

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

问题：

思路：注意到 $i^{i}$ 的奇偶性只与 $i$ 有关因此前 $i$ 天树叶的和的奇偶性我们可以很容易的得到，并且叶子只能存活m天，所以只需判断 $n - m + 1$ 到 $n$ 天叶子的奇偶性即可

代码：

#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]表示保护

那么状态转移可表示为：

$dp[i][0] += max(dp[son][0], dp[son][1])$

$dp[i][1] += max(dp[son][0], dp[son][1] - 2 * c)$

代码：

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

查看全文

http://www.kler.cn/a/317111.html