The 4th Universal Cup. Stage 1 个人题解

比赛链接: The 4th Universal Cup. Stage 1: Grand Prix of Korolyov

C. Staple Stable

题意:

给定,,(), 求最小的, 满足:

记, (1) 式化为:

满足该方程的最小的为:

而满足的最小的为:

问题转变为最小化:

直接枚举显然会爆炸, 且这个函数虽然像对勾函数, 但不是单峰的, 所以也不能直接二分.

根据商的分段性质,最多只有个不同的取值, 且是关于递增的, 因此我们只需要跳着枚举, 对这个不同取值都让最小, 就可以求出答案.

AC Code:

void solve(){
    ll h = read(), w = read(), s = read();
    if(h * w <= s){puts("0"); return;}
    const ll inf = 1e18;
    ll ans = inf;

    // ceil(x / y)
    auto cdiv = [&](ll x, ll y){return (x - 1) / y + 1;};

    // 枚举所有可能的 A = ceil(h / x), 跳跃x进行枚举
    ll x = 1;
    while(x <= h){
        ll A = cdiv(h, x);
        if(s / A) ans = min(ans, cdiv(h, A) + cdiv(w, s / A) - 2);
        // (A-1) * x < h <= A * x ==> 满足不等式的最大x为 (h-1) / (A-1)
        if(A == 1) break;
        x = (h - 1) / (A - 1) + 1;
    }
    printf("%lld\n", ans);
}

---

D. Sequence Is Not Subsequence

题意: 给定字符串, 要求构造最短的字符串, 满足的所有真子序列都包含于, 且不含于.

设字符串长为, 下标从开始.

队友想的构造:

令, 对每个从到, 先把加入, 如果(即), 再把也加入.

我想的证明:

1.包含了的所有真子序列

的真子序列可通过删除至少个字符得到, 显然, 只需要证明删除个字符得到的真子序列都包含于即可. (既然存在删个得到的子序列, 那么删更多个肯定也存在.)

首先考虑删除头和尾的情况, 根据上述构造规则,直接就包含了和, 这种情况是平凡的.

接着考虑删掉中间某个字符的情况, 假设所求子序列是删除得到的, 由于包含了,包含了, 并且能保证中的出现在中的后面, 因此必然包含删除了得到的子序列.

综上,包含了的所有真子序列.

2.不含于

归纳反证.

在我们的构造中, 每轮循环都是先加入, 再加入.

假设包含于.

的最后一个字符是, 并只在最后时作为被加入.

因此子序列只能在中的这个之前出现, 记为(由到所构成)

问题转化为:是否是的子序列?

不断重复这个过程, 最后问题等价于:
是否是的子序列?

根据我们的构造, 如果, 则, 如果, 则, 因此不是的子序列.

因此最开始的假设就不成立, 故不含于.

3. 这样构造的最短

和都必须是的子序列, 感性理解一下, 我们的构造方式就是最短的合并和的方法, 因此最短. (不知道要怎么严谨证明.)

AC Code:

void solve(){
    std::string s; std::cin >> s;
    int n = s.size();
    std::string A = s.substr(1, n);   // s[1..n-1]
    std::string B = s.substr(0, n-1); // s[0..n-2]
    std::string t;
    for(int i = 0; i < n - 1; ++i){
        t += A[i];
        if(A[i] != B[i]) t += B[i];
    }
    std::cout << t << '\n';
}

E. Coffee Shops

题意: 把分配到长为的和序列, 让伤心的人尽可能多.

显然,越大越难伤心, 越容易让别人伤心.

首先尝试让序列的人都伤心, 这是可以做到的.

只需要如下构造(表示预留的空位):

就能让的每个人都伤心了. (注意,必须填数, 不能留空, 否则不会伤心.)

然后, 能否让也伤心呢? 当然可以, 只需要让比和都小就行.

不会严谨证明, 反正是对的.

AC Code:

void solve(){
    int n = read();
    int v = n << 1;
    std::vector<int> a(n), b(n);
    for(int i = 0; i < n; i += 2) a[i] = v--;
    if(!(n & 1)) a[n-1] = v--; // A 的最后一个数不能留空, 原因见上.
    for(int i = 0; i < n; ++i){
        b[i] = v--;
        if(!a[i]) a[i] = v--;
    }
    for(int i = 0; i < n; ++i) printf("%d ", a[i]); puts("");
    for(int i = 0; i < n; ++i) printf("%d ", b[i]); puts("");
}

F. Yet Another MST Problem

vp 的时候想出了做法, 但当时脑抽了没想到用 set 维护线段, 赛后才磨出代码.

最小生成树, 边权是神秘, 很自然想到 Kruskal, 按边权从小到大连点.

从小到大枚举, 假设找到了两个未相连的点和, 只要它们代表的线段的并集不包含, 则它们的边权就小于等于. 由于我们是按从小到大枚举的, 如果和的边权小于, 它们一定在之前就被连过了, 因此和的边权就只能为.

问题来了, 要如何高效找到所有对应线段不包含的点呢?

如果线段不包含, 只有两种情况:

1. 线段右端点在左边.
2. 线段左端点在右边.

这个很简单, 可以用两个 set 来维护线段: 一个 set 存放左端点, 一个 set 存放右端点.

再考虑连边, 除了用并查集维护连通性外, 我们还需要合并两个连通块所代表的线段, 这个合并后的线段要用于后续判断连通块是否一定能包含.

(只要有一条线段不包含, 就可以用它和合并, 而我们只关心那些一定不能和该连通块合并的点, 这也正是线段在题中代表的含义.)

那就简单了, 直接对两个连通块的代表线段求交即可.

复杂度应该是接近的吧.

感觉讲的有点抽象, 还是看代码吧.

AC Code:

void solve(){
    int n = read(), m = read();
    std::vector<int> p(n+1), pos(n+1);
    for(int i = 1; i <= n; ++i) p[i] = read(), pos[p[i]] = i;
    
    std::vector<int> f(m+1);
    std::vector<int> L(m+1), R(m+1);
    std::set<std::pair<int, int>> sL, sR;
    for(int i = 1; i <= m; ++i){
        L[i] = read(), R[i] = read();
        sL.insert({L[i], i}); sR.insert({R[i], i});
        f[i] = i;
    }

    auto find = [&](auto&& self, int x) -> int {
        return f[x] == x ? x : f[x] = self(self, f[x]);
    };

    auto merge = [&](int x, int y) -> void {
        f[find(find, y)] = find(find, x);
    };

    ll ans = 0;
    for(int mex = 0; mex <= n; ++mex){
        int p = pos[mex];
        std::vector<int> s; // 不覆盖p的线段
        for(auto it = sL.lower_bound({p+1, 0}); it != sL.end(); ++it) s.push_back(it->second);
        auto end = sR.lower_bound({p, 0});
        for(auto it = sR.begin(); it != end; ++it) s.push_back(it->second);
        
        if(s.empty()) continue;
        
        for(int& x : s) sL.erase({L[x], x}), sR.erase({R[x], x});
        
        int u = find(find, s[0]); // 全部都合并到 s[0]
        for(int i = 1; i < s.size(); ++i){
            int v = find(find, s[i]);
            if(u == v) continue;
            merge(u, v); ans += mex;
            L[u] = max(L[u], L[v]);
            R[u] = min(R[u], R[v]); // 取交, 空集统一设成 [n+1, 0]
            if(L[u] > R[u]) L[u] = n + 1, R[u] = 0;
        }
        for(int& x : s){
            if(find(find, x) == x) sL.insert({L[x], x}), sR.insert({R[x], x});
        }
    }
    printf("%lld\n", ans);
}

G. Cyclic TopsortG. Cyclic Topsort

题意: 给定一张有向图, 请你找出最长的序列, 满足: 对于的每个顶点, 所有指向它的点都出现在之前. 删除最大的即可.

如果我们把这个序列看作 “删除” 顺序, 那么当我们删到的时候, 它的入度必须为, 于是问题又等价于: 选择一个删除顺序, 使删除的节点最多, 删除的约束是当前点在图中的入度为, 其中第一个点可以任意选择.

先不考虑可任选的第一个点, 我们先做一遍 Kahn, 找出那些不论起点是谁, 都一定能被删除的节点, 计数 (cnt) 并标记 (removed).

接着考虑起点的枚举. 如果直接从到枚举起点做 Kahn, 时间复杂度, 无法接受. 而显然, 如果起点能作为节点的后继, 那么以为起点肯定非最优. 所以我们可以在拓扑排序的时候, 用 vis 标记出队过的节点, 枚举起点时跳过这些点即可.

即使有 vis 数组, 对于固定的起点枚举顺序, 依然可以构造图, 使得按这个顺序枚举起点时, 被 vis 标记的点很少, 从而把时间复杂度卡到. 我赛时从到枚举起点就这样直接飞了.

考虑这样一条树链:, 节点只有在其某个祖先被首先选作起点且比树链上其它节点更早出现时, 才会被包含到那次 Kahn 中.

因此, 随机选这链上的一点, 它在 Kahn 中的期望出现次数.

对所有节点求和, 因深度不超过, 以及由不等式, 有:

因此总点操作的期望次数上界为, 同理总边操作的期望次数上界为, 于是时间复杂度的期望上界为.

要如何达到期望时间复杂度? 随机起点的枚举顺序即可.

AC Code:

void solve(){
    int n = read(), m = read();
    std::vector<std::vector<int>> adj(n+1, std::vector<int>());
    std::vector<int> in(n+1);
    for(int i = 1; i <= m; ++i){
        int x = read(), y = read();
        adj[x].push_back(y);
        ++in[y];
    }

    int cnt = 0; // 必选点个数
    std::vector<bool> removed(n+1);
    
    auto kahn1 = [&]() -> void {
        std::queue<int> q;
        for(int i = 1; i <= n; ++i){
            if(!in[i]) q.push(i);
        }
        while(q.size()){
            int x = q.front(); q.pop();
            removed[x] = 1; ++cnt;
            for(auto& y : adj[x]) if(!--in[y]) q.push(y);
        }
    }; kahn1();

    std::vector<bool> vis(n+1);

    auto kahn2 = [&](int s) -> int {
        std::vector<int> rec; // recover
        std::queue<int> q; q.push(s);
        int res = 0;
        while(q.size()){
            int x = q.front(); q.pop();
            vis[x] = 1; ++res;
            rec.push_back(x);
            for(auto& y : adj[x]){
                if(removed[y] or y == s) continue;
                if(!--in[y]) q.push(y);
            }
        }
        for(auto& x : rec) for(auto& y : adj[x])
            if(!removed[y] and y != s) ++in[y];
        
        return res;
    };

    int ans = 0;
    std::vector<int> p(n+2);
    for(int i = 1; i <= n; ++i) p[i] = i;
    std::random_shuffle(&p[1], &p[n+1]); // 随机起点枚举顺序
    
    for(int i = 1; i <= n; ++i){
        if(!removed[p[i]] and !vis[p[i]]) ans = max(ans, kahn2(p[i]));
    }
    printf("%d\n", ans += cnt);
}

H. Misread Problem

题意: 求一个石子总数为的石子分配方案, 使得该方案 b 分别变成给定的 k 个石子分配方案的总成本最小.

换言之, 目标即最小化:

队友的做法(原话):

首先可以发现最终代价就是每一列确定一个，每一列的数字和的差绝对值的总和的一半。
然后先不考虑总和为的限制，对每一列单独考虑，可以看成初始，为这一列的总代价贡献（与差的和），可以发现是个分段函数，每多放一个，小于的值贡献的代价，大于的值的贡献的代价，斜率就是当前小于的数量减去大于等于的数量。

最后每一列都处理出来若干段函数的斜率和分段的区间长度，贪心选取斜率最小的段，直到选取的长度为即可。

不过这是我的博客, 所以我讲我的想法(其实和上面的想法很像).

交换求和顺序:

将问题分解到每个位置上, 令表示给位置分配个石头的所需最小成本.

这是一个凸函数, 目标就是求的条件下, 这个凸函数的和的最小值.

给位置添加一个石子, 成本的增量为:

如果贪心地放石头, 那么所有位置最后放入的那个石子的成本增量应该大致相等. (否则, 我们可以从成本高的位置取出石子, 放到成本更低的位置, 从而使总成本减小.)

由于很大, 一个一个放石子是不可能的. 因为成本函数是凸函数, 我们可以在二分出一个最大的成本增量, 并计算: 如果把每个位置的成本都拉到, 需要的石子总数是多少? 如果, 说明现有的足够支撑更大的, 令, 否则令.

二分出来的这个满足: 最大成本达到所需的石子数, 最大成本达所需的石子数. 最后再贪心地分配剩余 (用掉使成本达到的石子后所剩下的) 的石子即可.

瓶颈在预处理的排序部分, 时间复杂度.

AC Code:

void solve(){
    int n = read(), m = read(), k = read();
    // s[i][j] : 第 i 个位置在第 k 个分布中的石子数
    std::vector<std::vector<ll>> a(n, std::vector<ll>(k));
    for(int j = 0; j < k; ++j) for(int i = 0; i < n; ++i) a[i][j] = read();
    // 排序后的前缀和
    std::vector<std::vector<ll>> ps(n, std::vector<ll>(k+1));
    for(int i = 0; i < n; ++i){
        std::sort(a[i].begin(), a[i].end());
        for(int j = 0; j < k; ++j){
            ps[i][j+1] = ps[i][j] + a[i][j];
        }
    }
    int l = 0, r = k, idx = -1; // 达到最优成本对应的索引
    while(l <= r){
        int mid = l + r >> 1;
        ll tot = 0;
        for(int i = 0; i < n; ++i) tot += a[i][mid];
        if(tot <= m) idx = mid, l = mid + 1;
        else r = mid - 1;
    }
    // 按 idx 分配
    std::vector<ll> b(n);
    ll used = 0;
    if(idx != -1){
        for(int i = 0; i < n; ++i) b[i] = a[i][idx], used += b[i];
    }
    // 分配剩余石子
    ll rem = m - used;
    std::vector<std::pair<ll, int>> stones;
    for(int i = 0; i < n; ++i){
        // 当前成本
        ll cost = std::upper_bound(a[i].begin(), a[i].end(), b[i]) - a[i].begin();
        stones.emplace_back(cost, i);
    }
    // 按成本从小到大贪心放置
    std::sort(stones.begin(), stones.end());
    for(const auto& [cost, i] : stones){
        if(!rem) break;
        // 容量
        ll cap = idx == k-1 ? m : a[i][idx+1] - b[i];
        ll add = min(rem, cap);
        b[i] += add; rem -= add;
    }

    // 计算总成本
    ll ans = 0;
    for(int i = 0; i < n; ++i){
        auto it = std::upper_bound(a[i].begin(), a[i].end(), b[i]);
        int p = it - a[i].begin(); // 有 p 个位置的石子数 <= b[i]
        ans += p * b[i] - ps[i][p];
    }
    printf("%lld\n", ans);
}