周赛 Round 140 题解

由于牛客的渲染问题，你可以点此链接进入我的博客查看

A 小红的区间计数

知识点：计数

三个数字分别判断一下是否在 的区间内，是则 ​ ，注意判断这三个数字是否有重复。

时间复杂度

void solve() {
    int l, r;
    vector<int> a(3);
    cin >> a[0] >> a[1] >> a[2] >> l >> r;
    sort(a.begin(), a.end());
    a.erase(unique(a.begin(), a.end()), a.end());
    auto In = [&](int x, int l, int r) { return l <= x && x <= r; };
    int ans = r - l + 1;
    for (auto v : a) ans -= In(v, l, r);
    cout << ans << endl;
}

B 小红的牛魔

知识点：栈

本质括号匹配，用栈模拟一下，每次判断一下栈顶的几个元素是否可删即可，这里为了实现方便使用 来实现栈。

时间复杂度

void solve() {
    int n;
    string s;
    cin >> n >> s;
    string st = "";
    for (auto v : s) {
        st += v;
        if (st.size() >= 3) {
            if (st.substr(st.size() - 3) == "niu") st.pop_back(), st.pop_back(), st.pop_back();
        }
        if (st.size() >= 2) {
            if (st.substr(st.size() - 2) == "mo") st.pop_back(), st.pop_back();
        }
    }
    cout << (st.empty() ? "Yes" : "No") << endl;
}

C 小红的矩阵计数

知识点：枚举

不妨把 块补全为 ​ 的正方形，用相对于左上格子的相对位移表示 块，枚举左上格子计数即可。

时间复杂度

void solve() {
    int n, m;
    cin >> n >> m;
    vector<string> g(n);
    for (int i = 0; i < n; ++i) cin >> g[i];
    auto check = [&](int x, int y) { return 0 <= x && x < n && 0 <= y && y < m; };
    auto calc = [&](vector<PII> sp) {
        int res = 0;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                unordered_set<int> st;
                for (auto [u, v] : sp) {
                    int nx = i + u, ny = j + v;
                    if (!check(nx, ny)) {
                        break;
                    }
                    st.insert(g[nx][ny] - '0');
                }
                if (st.size() == 3) res++;
            }
        }
        return res;
    };
    cout << calc({{0, 1}, {1, 1}, {1, 0}}) + calc({{0, 0}, {0, 1}, {1, 1}}) + calc({{1, 1}, {1, 0}, {0, 0}}) + calc({{1, 0}, {0, 0}, {0, 1}}) << endl;
}

D/E 小红的排序（hard）

知识点：图论，并查集

对于每一组交换，必然有 。那么我们对所有可交换的元素连边，连通块内的元素显然两两可达。最后检查 和 是否在同一个连通块内即可，使用并查集查询即可。

时间复杂度

void solve() {
    int n, x, y;
    cin >> n >> x >> y;
    vector<int> p(n + 1), pos(n + 1);
    for (int i = 1; i <= n; ++i) cin >> p[i], pos[p[i]] = i;
    DSU dsu(n);
    for (int i = 1; i <= n; ++i) {
        if (i + x <= n) dsu.merge(i, i + x);
        if (i + y <= n) dsu.merge(i, i + y);
    }
    for (int i = 1; i <= n; ++i) {
        if (!dsu.same(i, pos[i])) {
            cout << "No" << endl;
            return;
        }
    }
    cout << "Yes" << endl;
}

F 小红的三角形构造

知识点：数学，构造

对于一个直角三角形，我们可以用

进行描述。

所以：

• 如果 是奇数，我们令 ，取 ，解得

  

  计算出 即可。

• 如果 是偶数，我们令 ，取 ，计算 ​ 即可。

时间复杂度

void solve() {
    int x;
    cin >> x;
    if (x == 1 || x == 2)
        cout << "No" << endl;
    else if (x & 1) {
        int n = (x + 1) / 2, m = (x - 1) / 2;
        cout << "Yes" << endl;
        cout << n * n - m * m << " " << 2 * n * m << " " << n * n + m * m << endl;
    } else {
        int n = x / 2, m = 1;
        cout << "Yes" << endl;
        cout << n * n - m * m << " " << 2 * n * m << " " << n * n + m * m << endl;
    }
}

G 小红的生成树构造

知识点：生成树，构造，连通块，并查集

我们可以将题目的条件转化为：若我们将所有点分为两类： 和 ，则在这条连接 和 的路径上，所有经过的节点都必须属于

​ ，也就是说， 和 的匹配必须完全在 的同色连通块内部发生； 和 的匹配必须完全在 ​ 的同色连通块内部发生。

所以，在任何合法的生成树中，去除连接 和 之间的所有边后，我们会得到一个只由 节点构成与只由 节点构成的森林。对于每棵处于 中的树，它要么为空，要么必须同时包含至少一个 和至少一个 。因为只有这样，树中的 才能通向 ，且路径仅由 内节点构成。同理，每棵处于 中的树也必须同时包含至少一个 和至少一个 ​ 。

所以我们先连所有同组边，检查每一个连通块内是否包含该组的每组元素至少一个，然后将不同组的连通块之间相连即可。

时间复杂度

struct DSU {
    vector<int> f, siz;
    vector<int> mask;

    DSU() {}
    DSU(int n) {
        init(n);
    }

    void init(int n) {
        f.resize(n + 1);
        mask.resize(n + 1);
        iota(f.begin(), f.end(), 0);
        siz.assign(n + 1, 1);
    }

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

    void merge(int x, int y) {
        x = find(x), y = find(y);
        if (x == y) return;
        mask[x] |= mask[y];
        f[y] = x;
        siz[x] += siz[y];
    }

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

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

void init() {}

void solve() {
    int n, m;
    string s;
    cin >> n >> m >> s;

    vector<int> type(n + 1);
    DSU dsu(n);

    for (int i = 0; i < n; ++i) {
        if (s[i] == 'A') {
            type[i + 1] = 0, dsu.mask[i + 1] = 1;
        } else if (s[i] == 'B') {
            type[i + 1] = 0, dsu.mask[i + 1] = 2;
        } else if (s[i] == 'C') {
            type[i + 1] = 1, dsu.mask[i + 1] = 4;
        } else if (s[i] == 'D') {
            type[i + 1] = 1, dsu.mask[i + 1] = 8;
        }
    }
    vector<PII> edges(m), ans;
    for (int i = 0; i < m; ++i) cin >> edges[i].fi >> edges[i].se;

    for (auto [u, v] : edges) {
        if (type[u] == type[v]) {
            if (!dsu.same(u, v)) {
                dsu.merge(u, v);
                ans.pb({u, v});
            }
        }
    }

    for (int i = 1; i <= n; i++) {
        if (dsu.f[i] == i) {
            if (type[i] == 0) {
                if ((dsu.mask[i] & 1) == 0 || (dsu.mask[i] & 2) == 0) {
                    cout << "No" << endl;
                    return;
                }
            } else {
                if ((dsu.mask[i] & 4) == 0 || (dsu.mask[i] & 8) == 0) {
                    cout << "No" << endl;
                    return;
                }
            }
        }
    }

    for (auto [u, v] : edges) {
        if (type[u] != type[v]) {
            if (!dsu.same(u, v)) {
                dsu.merge(u, v);
                ans.pb({u, v});
            }
        }
    }

    if (ans.size() != n - 1) {
        cout << "No" << endl;
        return;
    }

    cout << "Yes" << endl;
    for (auto [u, v] : ans) {
        cout << u << " " << v << endl;
    }
}