社区讨论

没有用可并堆,直接自底向上贪心 AC 了,为什么?

P10283 [USACO24OPEN] Identity Theft P参与者 48已保存回复 58

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
57 条
当前快照
1 份
快照标识符
@luajs7qh
此快照首次捕获于
2024/03/28 09:20
2 年前
此快照最后确认于
2024/08/05 07:55
2 年前
查看原帖
如题。就是先把子树贪完,过程中维护一个 f 数组表示从这个结点降下一个新的棋子,最少要几步可以调整使条件满足。随时动态维护 f。移动的时候,贪心朝 f 较小的一侧移动。
时间复杂度可以证明是一个 log,因为每个棋子最多移动 log 步。但是为什么贪心得到的答案是对的?
CPP
#include <iostream>
#include <string>
#include <vector>
#include <array>
#include <functional>
#include <algorithm>
using std::cin, std::cout;
using std::min;

void Solve();
int main() {
    cin.sync_with_stdio(false);
    cin.tie(nullptr);
    Solve();
    return 0;
}

void Solve() {
    int N;
    cin >> N;
    std::vector<std::array<int, 2>> child(2);
    std::vector<int> chips(2);
    int root = 1;
    for (int i = 1; i <= N; ++i) {
        std::string s;
        cin >> s;
        int now = root;
        for (char c : s) {
            int j = c - '0';
            if (!child[now][j]) {
                child[now][j] = (int)child.size();
                child.push_back({0, 0});
                chips.push_back(0);
            }
            now = child[now][j];
        }
        ++chips[now];
    }
    std::vector<int> f(child.size());
    int ans = 0;
    auto Update = [&](int u) {
        if (!child[u][0] && !child[u][1])
            f[u] = 0;
        else
            f[u] = min(f[child[u][0]], f[child[u][1]]) + 1;
    };
    std::function<void(int)> Propagate = [&](int u) {
        --chips[u];
        if (f[u] == 0) {
            f[u] = 2;
            return ;
        }
        if (!child[u][0] && !child[u][1]) {
            child[u][0] = (int)child.size();
            child.push_back({0, 0});
            chips.push_back(0);
            f.push_back(0);
            child[u][1] = (int)child.size();
            child.push_back({0, 0});
            chips.push_back(0);
            f.push_back(0);
            ++chips[child[u][0]], ++ans;
            ++chips[child[u][1]], ++ans;
            Propagate(child[u][0]);
            Propagate(child[u][1]);
            Update(u);
            return ;
        }
        int dir = f[child[u][0]] > f[child[u][1]];
        if (!child[u][dir]) {
            child[u][dir] = (int)child.size();
            child.push_back({0, 0});
            chips.push_back(0);
            f.push_back(0);
        }
        ++chips[child[u][dir]], ++ans;
        Propagate(child[u][dir]);
        Update(u);
    };
    std::function<void(int)> DFS = [&](int u) {
        if (!u)
            return ;
        DFS(child[u][0]);
        DFS(child[u][1]);
        Update(u);
        while (chips[u])
            Propagate(u);
    };
    DFS(root);
    cout << ans << '\n';
}

回复

58 条回复,欢迎继续交流。

正在加载回复...