D.哥三好

Solution

容易想到用 三维 加记忆化搜索得到答案，但是 ，不能开这么大的数组，考虑如何压缩数据。注意到每次花费分别为 ，不难证明对花费和金额同时做乘法除法后与原问题等价，先分别乘2，此时花费为 ，金额，再同时除以100，花费变为 ，此时金额为 。金额均满足 ，做朴素的记忆化搜索即可。

Code

#include<bits/stdc++.h>

const int mod = 1e9 + 7;
const int N = 1e5 + 5;

long long dp[205][205][205];
int table[3] = {6, 9, 15};
long long dfs(int a, int b, int c) {
    if (dp[a][b][c] != -1) {
        return dp[a][b][c];
    }
    long long res = 0;
    for (int i = 0; i < 3; i++) {
        int x = table[i];
        if (a >= x) {
            res += dfs(a - x, b, c);
        }
        if (b >= x) {
            res += dfs(a, b - x, c);
        }
        if (c >= x) {
            res += dfs(a, b, c - x);
        }
        if (res >= mod) {
            res %= mod;
        }
    }
    if (!res) {
        return dp[a][b][c] = 1;
    } else {
        return dp[a][b][c] = res;
    }
}
void solve() {
    memset(dp, -1, sizeof(dp));
    int a, b, c; std::cin >> a >> b >> c;
    a *= 2, b *= 2, c *= 2;
    a /= 100, b /= 100, c /= 100;
    std::cout << dfs(a, b, c) << '\n';
}
signed main() {
    std::cin.sync_with_stdio(false), std::cin.tie(nullptr);
    int T = 1; //std::cin >> T; 
    while (T--) {
        solve();
    }
    return 0;
}

G. 永不言弃

Solution

题目给出的需要通过前置关卡才能通关后续关卡，显然可以用拓扑排序来做，关键点在于一开始要判断能否通过关卡1，随后在拓扑排序的过程中可能有的关卡暂时无法通过，可以丢到一个优先队列（最小堆）和一个 ，当 更新和获得必须道具时，可以检查优先队列和 里是否有新的节点能否加入。

Code

#include<bits/stdc++.h>

const int mod = 1e9 + 7;
const int N = 1e6 + 5;

std::pair<int, int> a[500005], benefit[50005];
std::vector<int> V[50005], G[50005];
int in[50005], mp[50005];
bool vis[50005];
void solve() {
    int n; long long s; std::cin >> n >> s;
    for (int i = 1; i <= n; i++) { 
        std::cin >> a[i].first >> a[i].second;    
    }
    for (int i = 1; i <= n; i++) {
        std::cin >> benefit[i].first >> benefit[i].second;
    }
    for (int i = 1; i <= n; i++) {
        int k; std::cin >> k;
        for (int j = 1; j <= k; j++) {
            int num; std::cin >> num;
            G[i].emplace_back(num);
            in[num]++;
        }
    }
    std::queue<int> que_topo;
    for (int i = 1; i <= n; i++) {
        if (!in[i] && i != 1) { // 永远无法开启
            std::cout << "No\n"; return ;
        }
    } 
    if (s <= a[1].first) {
        std::cout << "No\n"; return ;
    }
    que_topo.push(1);
    std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int> >, std::greater<std::pair<int, int> > > que_buffer;
    while (!que_topo.empty()) {
        auto now = que_topo.front(); que_topo.pop();
        if (vis[now]) continue;
        vis[now] = true;
        if (!mp[benefit[now].second]) {
            mp[benefit[now].second]++; // 拥有这个物品
            for (auto &v : V[benefit[now].second]) {
                if (!vis[v]) {
                    que_topo.push(v);
                }
            }
            V[benefit[now].second].clear();
        }
        s += benefit[now].first; // 加属性
        while (!que_buffer.empty() && s > que_buffer.top().first) {
            que_topo.push(que_buffer.top().second);
            que_buffer.pop();
        }
        for (auto &v : G[now]) {
            in[v]--;
            if (!in[v]) {
                if (mp[a[v].second]) { // 有必备道具
                    que_topo.push(v);
                } else if (s > a[v].first) { // 属性足够
                    que_topo.push(v);
                } else {
                    V[a[v].second].emplace_back(v); 
                    que_buffer.push({a[v].first, v}); // 缓冲池，存储 
                }
            }
        }
    }
    for (int i = 1; i <= n; i++) {
        if (!vis[i]) {
            std::cout << "No\n"; return ;
        }
    }
    std::cout << "Yes\n";
}

signed main() {
    std::cin.sync_with_stdio(false), std::cin.tie(nullptr);
    int T = 1; //std::cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}

H.卷王之王

Solution

每次做一次加的操作相当于一次倍增（x -> 2x)，考虑到 ，最多只能做 次，所以用一个优先队列每次取出要处理的序列即，注意要特判 是否为 0。

Code

#include<bits/stdc++.h>

const int mod = 1e9 + 7;
const int N = 2e5 + 5;

void solve() {
    int n, m; std::cin >> n >> m;
    std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int> >, std::greater<std::pair<int, int> > > que;
    for (int i = 1; i <= n; i++) {
        int x; std::cin >> x;
        que.push({x, i});
    }
    std::vector<int> ans(n + 1);
    while (m--) {
        int x; std::cin >> x;
        if (x == 0) {
            continue;
        }
        std::vector<std::pair<int, int> > buffer;
        while (!que.empty() && que.top().first <= x) {
            buffer.emplace_back(que.top().first + x, que.top().second);
            que.pop();
        }
        for (auto it : buffer) {
            que.push(it);
        }
    }
    while (!que.empty()) {
        auto now = que.top(); que.pop();
        ans[now.second] = now.first;
    }
    for (int i = 1; i <= n; i++) {
        std::cout << ans[i] << " \n"[i == n];
    }
}

signed main() {
    std::cin.sync_with_stdio(false), std::cin.tie(nullptr);
    int T = 1; //std::cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}