JZTXT

CSP模拟34

发布时间 2023-09-10 20:59:00作者: User-Unauthorized

A. 斐波那契树

发现在最终的生成树中可以出现的白边数量为一个区间，所以求其边界即可。

最大 / 小化生成树中白边的数量可以将其边权置为 \(0 / 1\) 后求最小生成树即可。

不过其实不用显式排序，将边按颜色种类存储，然后先考虑一个颜色的边集即可。

复杂度 \(\mathcal{O}(\left(N + M\right) \alpha(N))\)。

B. 期末考试

Meet in the middle。枚举前 \(5\) 个答案和后 \(5\) 个答案，将前 \(5\) 个答案的所有情况在所有 \(n\) 个限制的得分哈希起来，枚举后 \(5\) 个答案的时候求解即可。

复杂度 \(\mathcal{O}(4^5n)\)。

C. 麻烦的工作

贪心的考虑，将 \(a, b\) 降序排列，将需要人数多的任务分配给可工作次数多的员工完成。

考虑将前 \(k\) 个任务视为一个任务并检查是否可以完成，对于前 \(k\) 个任务，每个员工最多贡献 \(\min(b_i, k)\) 次，所有员工共可工作 \(\sum\limits_{i = 1}^{m}\min(b_i, k)\)，而前 \(k\) 个任务共需工作 \(\sum\limits_{i = 1}^{k}a_i\) 次，故前 \(k\) 个任务可以完成的必要条件为

\[\sum\limits_{i = 1}^{m}\min(b_i, k) \ge \sum\limits_{i = 1}^{k}a_i \]

注意这里的 \(a\) 序列是降序排列的。

发现可以化简条件式

\[\begin{aligned} & \sum\limits_{i = 1}^{m}\min(b_i, k) \ge \sum\limits_{i = 1}^{k}a_i \\ \Leftrightarrow & \sum\limits_{i = 1}^{m}\sum\limits_{j = 1}^{\min(b_i, k)}1 \ge \sum\limits_{i = 1}^{k}a_i \\ \Leftrightarrow & \sum\limits_{i = 1}^{m}\sum\limits_{j \ge 1}\left[j \le b_i \land j \le k\right] \ge \sum\limits_{i = 1}^{k}a_i \\ \Leftrightarrow & \sum\limits_{i = 1}^{m}\sum\limits_{j = 1}^{k}\left[j \le b_i\right] \ge \sum\limits_{i = 1}^{k}a_i \\ \Leftrightarrow & \sum\limits_{j = 1}^{k}\sum\limits_{i = 1}^{m}\left[j \le b_i\right] \ge \sum\limits_{i = 1}^{k}a_i \\ \end{aligned}\]

记 \(val_j = \sum\limits_{i = 1}^{m}\left[j \le b_i\right], s_k = \sum\limits_{i = 1}^{k}a_i\)，那么可化为

\[\sum\limits_{j = 1}^{k} val_j - s_k \ge 0 \]

由于每次修改只会使值改变 \(1\)，故可以快速维护两个数组。首先考虑 \(val\) 的维护，发现 \(val\) 的变化可以快速计算，故其对前缀和的贡献使用一个支持区间加的数据结构即可。接下来考虑 \(s\) 的维护，因为 \(s\) 计算的是降序排列后的 \(a\) 数组值，故若有更改 \(a_i \rightarrow a_i + 1\)，将任意一个满足 \(a_x = a_i\) 的 \(x\) 的 \(a_i\) 值更改都是等价的，所以可以在更改时维护降序排列的性质，值增加时更改值相同中最前的元素，值减少时更改值相同中最后的元素即可。

D. 小X的Galgame

分类讨论可发现若一个节点子树内有存档点，那么在走到这个节点时设置存档点一定不劣，故在一个节点子树内有存档点时，强制要求也在走到这个节点时设置存档点，故可以进行 \(\tt{DP}\)。

设 \(f_u\) 表示 \(u\) 节点及其子树内没有存档点且以 \(u\) 节点为当前根节点的代价，显然其值为 \(u\) 节点到其子树内所有叶子节点的距离和，设 \(g_u\) 表示在节点 \(u\) 设置存档点且根节点为 \(1\)，在第一次走到节点 \(u\) 后的代价最小值。\(f\) 的转移是平凡的，重点讨论如何转移 \(g\)，发现可以枚举每个儿子节点是否设立存档点，首先强制所有设立存档点的儿子节点都是从根节点到达的，那么有转移：

\[g_u = \sum\limits_{v \in \operatorname{son}_u} \min(f_v + count_v \times w(u, v), g_v + dist_v) \]

其中 \(count_u\) 表示 \(u\) 的子树内叶子节点的数量，\(w(u, v)\) 表示边权，\(dist_u\) 表示节点 \(u\) 到根节点的距离。

发现设立存档点的儿子中可以有一个从节点 \(u\) 转移而来，使得总花费减少 \(dist_u\)，所以若存在设立存档点的儿子节点，那么有 \(g_u \rightarrow g_u - dist_u\)，否则若存在儿子节点 \(v\) 使得 \(f_v + count_v \times w(u, v) > g_v + dist_v - dist_u\)，那么取使得 \(g_v + dist_v - f_v + count_v \times w(u, v)\) 最小的儿子节点 \(v\) 设立存档点可以使总花费最优，转移即可。

总复杂度 \(\mathcal{O}(n)\)。

Code

A

#include <bits/stdc++.h>

typedef int valueType;
typedef std::vector<valueType> ValueVector;
typedef std::pair<valueType, valueType> ValuePair;
typedef std::vector<ValuePair> PairVector;

class DSU {
public:
    typedef int valueType;
    typedef std::vector<valueType> ValueVector;

private:
    valueType N;

    std::vector<int> father, size;

public:
    explicit DSU(valueType n) : N(n), father(N, 0), size(N, 0) {
        std::iota(father.begin(), father.end(), 0);

        std::fill(size.begin(), size.end(), 1);
    }

    int find(int x) {
        return father[x] == x ? x : father[x] = find(father[x]);
    }

    void unite(int x, int y, bool sizeBalance = true) {
        x = find(x), y = find(y);

        if (x == y) return;

        if (sizeBalance && size[x] < size[y]) std::swap(x, y);

        father[y] = x;
        size[x] += size[y];
    }

    bool check(int x, int y) {
        return find(x) == find(y);
    }

    valueType sizeOf(int x) {
        return size[find(x)];
    }
};

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);

    ValueVector fibonacci = {0, 1, 1};

    for (int i = 3; i <= 30; i++)
        fibonacci.push_back(fibonacci[i - 1] + fibonacci[i - 2]);

    fibonacci.erase(fibonacci.begin());

    valueType T;

    std::cin >> T;

    for (int testcase = 0; testcase < T; ++testcase) {
        valueType N, M;

        std::cin >> N >> M;

        DSU dsu(N + 1);

        PairVector white, black;

        white.reserve(M);
        black.reserve(M);

        for (int i = 0; i < M; ++i) {
            valueType x, y, c;

            std::cin >> x >> y >> c;

            if (c == 1) {
                white.emplace_back(x, y);
            } else {
                black.emplace_back(x, y);
            }
        }

        valueType maxCount = 0;

        for (auto const &iter: white) {
            if (!dsu.check(iter.first, iter.second)) {
                dsu.unite(iter.first, iter.second);

                ++maxCount;
            }
        }

        for (auto const &iter: black) {
            if (!dsu.check(iter.first, iter.second)) {
                dsu.unite(iter.first, iter.second);
            }
        }

        if (dsu.sizeOf(1) != N) {
            std::cout << "NO" << std::endl;

            continue;
        }

        valueType minCount = 0;

        dsu = DSU(N + 1);

        for (auto const &iter: black) {
            if (!dsu.check(iter.first, iter.second)) {
                dsu.unite(iter.first, iter.second);

                ++minCount;
            }
        }

        for (auto const &iter: white) {
            if (!dsu.check(iter.first, iter.second)) {
                dsu.unite(iter.first, iter.second);
            }
        }

        minCount = N - 1 - minCount;

        bool ok = false;

        for (auto const &fib: fibonacci) {
            if (fib >= minCount && fib <= maxCount) {
                ok = true;

                break;
            }
        }

        std::cout << (ok ? "YES" : "NO") << std::endl;
    }

    std::cout << std::flush;

    return 0;
}

B

#include <bits/stdc++.h>

typedef int valueType;
typedef std::vector<valueType> ValueVector;
typedef std::string string;
typedef std::pair<string, valueType> LimitType;
typedef std::vector<LimitType> LimitVector;
typedef std::vector<string> StringSet;
typedef unsigned long long hashType;
typedef std::map<hashType, valueType> HashMap;

valueType match(const string &a, const string &b) {
    valueType result = 0;

    for (valueType i = 0; i < std::min(a.size(), b.size()); ++i)
        if (a[i] == b[i])
            ++result;

    return result;
}

const hashType mask = std::chrono::system_clock::now().time_since_epoch().count() ^ 0xc0ffeec0ffee;

hashType xor_shift(hashType x) {
    x ^= mask;
    x ^= x << 13u;
    x ^= x >> 7u;
    x ^= x << 17u;
    x ^= mask;

    return x;
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);

    StringSet leftAll, rightAll;

    for (char c1 = 'A'; c1 <= 'D'; ++c1) {
        for (char c2 = 'A'; c2 <= 'D'; ++c2) {
            for (char c3 = 'A'; c3 <= 'D'; ++c3) {
                for (char c4 = 'A'; c4 <= 'D'; ++c4) {
                    for (char c5 = 'A'; c5 <= 'D'; ++c5) {
                        string s;

                        s += c1;
                        s += c2;
                        s += c3;
                        s += c4;
                        s += c5;

                        leftAll.push_back(s);
                        rightAll.push_back("#####" + s);
                    }
                }
            }
        }
    }

    valueType T;

    std::cin >> T;

    for (int testcase = 0; testcase < T; ++testcase) {
        valueType N;

        std::cin >> N;

        LimitVector data(N);

        for (auto &iter: data) {
            std::cin >> iter.first >> iter.second;

            iter.second /= 10;
        }

        HashMap hashMap;

        for (auto const &str: leftAll) {
            hashType hash = 0;

            bool ok = true;

            for (auto const &iter: data) {
                valueType const len = match(str, iter.first);

                if (iter.second < len) {
                    ok = false;

                    break;
                }

                hash = xor_shift(hash + len);
            }

            if (ok)
                ++hashMap[hash];
        }

        valueType ans = 0;

        for (auto const &str: rightAll) {
            hashType hash = 0;

            bool ok = true;

            for (auto const &iter: data) {
                valueType const len = match(str, iter.first);

                if (iter.second < len) {
                    ok = false;

                    break;
                }

                hash = xor_shift(hash + iter.second - len);
            }

            if (ok)
                ans += hashMap[hash];
        }

        std::cout << ans << '\n';
    }

    std::cout << std::flush;

    return 0;
}

C

#include <bits/stdc++.h>

typedef long long valueType;
typedef std::vector<valueType> ValueVector;

class Tree {
public:
    typedef ValueVector container;

private:
    valueType N;
    container data, lazy;

    void push(valueType id) {
        if (lazy[id] != 0) {
            data[id << 1] += lazy[id];
            data[id << 1 | 1] += lazy[id];

            lazy[id << 1] += lazy[id];
            lazy[id << 1 | 1] += lazy[id];

            lazy[id] = 0;
        }
    }

public:
    explicit Tree(valueType n) : N(n), data(4 * N + 10, 0), lazy(4 * N + 10, 0) {};

    void update(valueType l, valueType r, valueType key) {
        if (l < 1)
            l = 1;

        if (l > r)
            return;

        update(1, 1, N, l, r, key);
    }

    valueType query() const {
        return data[1];
    }

private:
    void update(valueType id, valueType nodeL, valueType nodeR, valueType queryL, valueType queryR, valueType key) {
        if (queryL <= nodeL && nodeR <= queryR) {
            data[id] += key;
            lazy[id] += key;

            return;
        }

        valueType const mid = (nodeL + nodeR) >> 1;

        push(id);

        if (queryL <= mid)
            update(id << 1, nodeL, mid, queryL, queryR, key);

        if (queryR > mid)
            update(id << 1 | 1, mid + 1, nodeR, queryL, queryR, key);

        data[id] = std::min(data[id << 1], data[id << 1 | 1]);
    }
};

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);

    valueType N, M;

    std::cin >> N >> M;

    ValueVector A(N + 1), B(M + 1);

    Tree tree(N);

    ValueVector bucket(N + 1, 0);

    for (valueType i = 1; i <= N; ++i)
        std::cin >> A[i];

    for (valueType i = 1; i <= M; ++i) {
        std::cin >> B[i];

        ++bucket[std::min(B[i], N)];
    }

    ValueVector SortedA = A;
    std::sort(SortedA.begin() + 1, SortedA.begin() + N + 1, std::greater<>());

    for (valueType i = 1; i <= N; ++i)
        tree.update(i, N, -SortedA[i]);

    bucket[0] = 0;
    std::partial_sum(bucket.rbegin(), bucket.rend(), bucket.rbegin());

    for (valueType i = 1; i <= N; ++i)
        tree.update(i, N, bucket[i]);

    valueType Q;

    std::cin >> Q;

    for (valueType i = 0; i < Q; ++i) {
        valueType opt, x;

        std::cin >> opt >> x;

        if (opt == 1) {
            valueType const pos = std::distance(SortedA.begin(),
                                                std::lower_bound(SortedA.begin() + 1, SortedA.begin() + N + 1, A[x],
                                                                 std::greater<>()));

            tree.update(pos, N, -1);

            ++A[x];
            ++SortedA[pos];
        } else if (opt == 2) {
            valueType const pos = std::distance(SortedA.begin(), std::prev(
                    std::upper_bound(SortedA.begin() + 1, SortedA.begin() + N + 1, A[x], std::greater<>())));

            tree.update(pos, N, 1);

            --A[x];
            --SortedA[pos];
        } else if (opt == 3) {
            ++B[x];

            tree.update(B[x], N, 1);
        } else {
            tree.update(B[x], N, -1);

            --B[x];
        }

        if (tree.query() >= 0)
            std::cout << 1 << '\n';
        else
            std::cout << 0 << '\n';
    }

    std::cout << std::flush;

    return 0;
}

D

#include <bits/stdc++.h>

typedef long long valueType;
typedef std::vector<valueType> ValueVector;
typedef std::pair<valueType, valueType> ValuePair;
typedef std::vector<ValuePair> PairVector;
typedef std::vector<PairVector> PairMatrix;

valueType N;
ValueVector F, G, dist, count;
PairMatrix Tree;

void dfs(valueType x, valueType from) {
    bool leaf = true;

    for (auto const &iter: Tree[x]) {
        if (iter.first == from)
            continue;

        leaf = false;

        dist[iter.first] = dist[x] + iter.second;

        dfs(iter.first, x);

        count[x] += count[iter.first];
    }

    if (leaf)
        count[x] = 1;

    valueType min = std::numeric_limits<valueType>::max();

    for (auto const &iter: Tree[x]) {
        if (iter.first == from)
            continue;

        valueType const f = F[iter.first] + iter.second * count[iter.first];
        valueType const g = G[iter.first] + dist[iter.first];

        F[x] += f;
        G[x] += std::min(f, g);

        min = std::min(min, g - f);
    }

    if (min < 0) {
        G[x] -= dist[x];
    } else if (min < dist[x]) {
        G[x] += min - dist[x];
    }
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);

    std::cin >> N;

    F.resize(N + 1);
    G.resize(N + 1);
    dist.resize(N + 1, 0);
    count.resize(N + 1, 0);
    Tree.resize(N + 1);

    for (valueType i = 1; i < N; ++i) {
        valueType a, b, w;

        std::cin >> a >> b >> w;

        Tree[a].emplace_back(b, w);
        Tree[b].emplace_back(a, w);
    }

    dfs(1, 0);

    std::cout << std::min(F[1], G[1]) << std::endl;

    return 0;
}