算法竞赛比赛记录: [6/6] CodeForces Round 1026 (Div. 2)

这次写了四道题，E 题有思路但是不会写，再接再厉吧

A. Fashionable Array

观察到 $n$ 非常小，只有 $50$ . 因此我们可以直接对 $A[]$ 排序后，用 $O(n^2)$ 暴力枚举 $\min,\max$ 即可。唯一值得注意的是， $\min,\max$ 可以是同一个数。

Code

#include <algorithm>
#include <headers/io/io.hpp>
#include <vector>
IO::IO io;

void run() {
    int n = io.scan<int>();
    std::vector<int> mp(n);
    io.read(mp);

    std::ranges::sort(mp);
    int ans = 1e9;
    for (int i = 0; i < n; i++) {
        for (int j = i; j < n; j++) {
            if ((mp[i] + mp[j]) % 2 != 0) continue;
            ans = std::min(ans, n - (j - i + 1));
        }
    }

    io.println(ans);
}

int main() {
    int T = io.scan<int>();
    while (T--) run();
}

B. Down with Brackets

因为需要且必须删除一个左括号、一个右括号，考虑两种情况：

删的右括号在左括号前面

我们可以证明这个情况是不行的。由于原串已经是合法的括号序了，令左括号为 $c_i=1$ 、右括号为 $c_i=-1$ ，则对于每一个位置都有

\forall i, f(i)=\sum_{1\le j\le i} c_j \ge 0

那么，如果先删右括号，这个和式必然不会减小。比如说删除了 $i$ 位置的 ')' 和 $j$ 位置的 '(' 且有 $i\lt j$ ，那么 $f(k),k\lt i$ 都不变， $f(k),i\lt k\lt j$ 会变大， $f(k),k\gt j$ 不变。所以这个串必然还是合法的括号序

删的左括号在右括号前面

对于这种情况的话，我们发现，如果某个位置上 $f(i)=0$ ，那么删掉它（或者它之前的一个 '('）就会让括号序不合法

Code

#include <headers/io/io.hpp>
#include <string>
IO::IO io;

void run() {
    std::string s = io.scan<std::string>();
    int n         = s.length();
    std::vector<int> pf(n + 1);
    pf[0] = 0;
    for (int i = 1; i <= n; i++) {
        if (s[i - 1] == '(') pf[i] = pf[i - 1] + 1;
        else pf[i] = pf[i - 1] - 1;

        if(i<n && pf[i] == 0) {
            io.println("YES");
            return;
        }
    }

    io.println("NO");
}

int main() {
    int T = io.scan<int>();
    while (T--) run();
}

C. Racing

合法性比较容易想到，就是用 $[l_i,r_i]$ 维护走完 $d_i$ 后可能的高度，判断和规定的区间是否有交集。没有则不合法，否则一定合法。

对于构造答案，我们从任意一个结束时的合法值出发，然后倒着看 $d_i$ 。如果符合要求的区间高度，则下降；否则不下降。

Code

#include <headers/io/io.hpp>
#include <utility>
using pii = std::pair<int, int>;
IO::IO io;

void run() {
    int n = io.scan<int>();
    std::vector<int> d(n);
    std::vector<pii> a(n);
    io.read(d, a);

    std::vector<pii> inter(n + 1, {0, 0});
    for (int i = 1; i <= n; i++) {
        if (d[i - 1] != -1) {
            inter[i].first  = inter[i - 1].first + d[i - 1];
            inter[i].second = inter[i - 1].second + d[i - 1];
        } else {
            inter[i].first  = inter[i - 1].first;
            inter[i].second = inter[i - 1].second + 1;
        }

        inter[i].first  = std::max(inter[i].first, a[i - 1].first);
        inter[i].second = std::min(inter[i].second, a[i - 1].second);

        if (inter[i].first > inter[i].second) {
            io.println("-1");
            return;
        }
    }

    // possible
    int H = inter[n].first;
    for (int i = n; i > 0; i--) {
        if (d[i - 1] != -1) H -= d[i - 1];
        else {
            if (H - 1 >= inter[i - 1].first && H - 1 <= inter[i - 1].second) H -= 1, d[i - 1] = 1;
            else d[i - 1] = 0;
        }
    }

    for (auto i : d) io.print(i, "");
    io.println("");
}

int main() {
    int T = io.scan<int>();
    while (T--) run();
}

D. Fewer Battery

考虑任意一条路径，我们发现如果走整条路径的话，终点时手上的电池数应该等于路径上的最大边权（当然前提要保证有足够多的电池可以走过这些边）

所以我们可以使用二分答案，过滤 $w\ge \texttt{mid}$ 的边，然后检查剩下的边是否可以成功到达终点。

Code

#include <headers/io/iov2.hpp>
#include <algorithm>
#include <utility>
#include <vector>
using i64       = long long;
using pii       = std::pair<int, i64>;
constexpr i64 V = -1e10;
IO::IO io;
 
void run() {
    auto [n, m] = io.scan<int, int>();
    std::vector<i64> b(n);
    io.read(b);
 
    std::vector<std::vector<pii>> adj(n);
    std::vector<i64> ws;
    for (int i = 0; i < m; i++) {
        auto [u, v, w] = io.scan<int, int, i64>();
        u--, v--;
        adj[u].emplace_back(v, w);
        ws.push_back(w);
    }
 
    std::vector<i64> dp(n, V);
 
    std::ranges::sort(ws);
    ws.erase(std::unique(ws.begin(), ws.end()), ws.end());
    i64 l = -1, r = ws.size();
    auto ck = [&](i64 mid) -> bool {
        std::ranges::fill(dp, V);
        dp[0] = b[0];
 
        for (int u = 0; u < n; u++) {
            if (dp[u] == V) continue;
            for (auto [v, w] : adj[u]) {
                if (w > mid) continue;
                if (dp[u] < w) continue;
                dp[v] = std::max(dp[v], dp[u] + b[v]);
            }
        }
 
        return dp[n - 1] >= 0;
    };
 
    while (l + 1 < r) {
        i64 mid = l + ((r - l) >> 1);
        if (ck(ws[mid])) r = mid;
        else l = mid;
    }
    io.println(r == ws.size() ? -1 : ws[r]);
}
 
int main() {
    int T = io.scan<int>();
    while (T--) run();
}

E. Melody

考虑左侧一列点位为 volume，右侧一列点为 pitch，条件相当于要求任意相邻两项是 v 不同、p 不同这样交错下去。

所以按上面这样建图的话，这个问题就是二分图上找欧拉路径

Code

#include <algorithm>
#include <headers/io/iov2.hpp>
#include <map>
#include <ranges>
#include <utility>
#include <vector>
#include <ranges>
using i64 = long long;
using pii = std::pair<int, int>;
IO::IO io;

void run() {
    int n   = io.scan<int>();
    auto vp = io.scan<std::vector<pii>>(n);

    std::vector<int> vs, ps;
    for (auto [v, p] : vp) {
        vs.push_back(v);
        ps.push_back(p);
    }
    std::ranges::sort(vs), std::ranges::sort(ps);
    vs.erase(std::unique(vs.begin(), vs.end()), vs.end());
    ps.erase(std::unique(ps.begin(), ps.end()), ps.end());
    int numv = vs.size(), nump = ps.size();
    int num = numv + nump;
    std::vector<std::vector<pii>> G(num);
    std::vector<int> deg(num, 0);
    std::map<pii, int> index;
    for (int i = 0; i < n; i++) {
        auto &[v, p] = vp[i];
        v            = std::lower_bound(vs.begin(), vs.end(), v) - vs.begin();
        p            = std::lower_bound(ps.begin(), ps.end(), p) - ps.begin() + numv;
        deg[v]++, deg[p]++;
        G[v].push_back({p, i});
        G[p].push_back({v, i});
        index[{v, p}] = i;
        index[{p, v}] = i;
    }

    std::vector<int> used(n, 0);
    std::vector<int> ans;
    std::vector<int> cur(num, 0);

    auto dfs = [&](auto F, int u) -> void {
        while(cur.at(u) < G.at(u).size()) {
            auto [v, id] = G[u][cur[u]];
            cur[u]++;
            if (used[id]) continue;
            used[id] = 1;
            F(F, v);
        }
        ans.push_back(u);
    };

    int root = 0, cnt = 0;
    for (int i = 0; i < num; i++) {
        if (deg[i] % 2 == 1) cnt++, root = i;
    }

    dfs(dfs, root);
    if (ans.size() != n + 1 || cnt > 2) {
        io.println("NO");
        return;
    }

    auto pt = ans | std::views::adjacent_transform<2>([&](int a, int b) { return index[{a, b}] + 1; });
    io.println("YES");
    std::ranges::for_each(pt, [&](int x) { io.print(x), io.print(" "); });
    io.println();
}

int main() {
    int T = io.scan<int>();
    while (T--) run();
}

F. Faculty

最没有注意力的一集……

我们需要观察到以下几点：

$\min(x,y)\le f(x,y)\le \max(x,y), x\ne y$

这个结论的证明比较简单。不妨设 $x\lt y$ ，则令 $y=kx+r,k\ge 1 \land 0\le r\lt x$ . 那么

x\le f(x,y)=x+r\le kx+r=y

故得证

考虑 $x\lt y\lt z$ ，则 $f(x,y)\le f(y,z)$

由 (1) 可证， $f(x,y)\le \max(x,y)=y=\min(y,z)\le f(y,z)$

这个结论也告诉我们，对于任意一个数组 $a[1\dots n]$ ，实际上只有 $n$ 个值需要检查：即 $f(a_1,a_{max}),f(a_2,a_{max})\dots, f(a_n,a_{max})$

若 $x\lt y\lt 2x$ ，则 $f(x,y)=y$

也可以从 (1) 证明。此时 $y=kx+r\implies k=1$ ，故 $f(x,y)=x+r=y$ .

有了这几点后我们就可以利用势能分析法了. 设新加入的数为 $a_i$ ， $a_{1:i-1}$ 的最大值为 $a_{max}$

如果 $a_i\le a_{max}$ ，那么根据 (2)，我们只需要考虑 $f(a_i,a_{max})$ 会不会成为答案即可。
如果 $a_{max}\lt a_i\lt 2a_{max}$ ，那么根据 (3)，我们只需要考虑 $f(a_i,a_{max})=a_i$ 会不会成为答案即可。
否则若 $a_i\ge 2a_{max}$ ，那么我们就遍历数组暴力求解

1/2 两步都是 $O(1)$ 的，对于 (3)，由于每一次 $a_{max}$ 都至少翻倍，因此最多执行 $O(\log V)$ 次第三步，因此这样的时间复杂度是 $O(n\log V)$

Code

#include <headers/io/iov2.hpp>
IO::IO io;

void run() {
    int n              = io.scan<int>();
    std::vector<int> a = io.scan<std::vector<int>>(n);

    auto F  = [&](int x, int y) { return x % y + y % x; };
    int max = a[0];
    int ans = 0;
    for (int i = 0; i < n; i++) {
        ans = std::max(ans, F(max, a[i]));

        if (max < a[i] && a[i] < 2 * max) {
            max = a[i];
            ans = std::max(ans, F(max, a[i]));
        } else if (a[i] >= 2 * max) {
            max = a[i];
            for (int j = 0; j <= i; j++) ans = std::max(ans, F(a[i], a[j]));
        }

        io.print(ans);
    }
    io.println();
}

int main() {
    int T = io.scan<int>();
    while (T--) run();
}