算法

(模拟)

Python 代码

n, m = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))

ans = []
for x in a:
    if x not in b:
        ans.append(x)
for x in b:
    if x not in a:
        ans.append(x)
ans.sort()
print(*ans)

class Solution:
    def kItemsWithMaximumSum(self, numOnes: int, numZeros: int, numNegOnes: int, k: int) -> int:
        res = min(k, numOnes)
        k -= min(k, numOnes)
        k -= min(k, numZeros)
        res -= k 
        return res

算法

(模拟)

假设答案为 $ans$

根据题意，则有 $\frac{ans}{Z} < \frac{Y}{X}$
$\Rightarrow ans \cdot X < YZ \Rightarrow ans \cdot \leqslant YZ-1 \Rightarrow ans \leqslant \frac{YZ-1}{X}$

Python 代码

x, y, z = map(int, input().split())
print((y*z-1)//x)

class Solution:
    def maxWidthOfVerticalArea(self, points: List[List[int]]) -> int:
        points.sort()
        res = 0
        for i in range(1, len(points)):
            res = max(res, points[i][0]-points[i-1][0])
        return res

#define rep(i, n) for (int i = 0; i < (n); ++i)
class Solution {
public:
    // linear sieve
    vector<int> ps, pf;
    void sieve(int mx) {
        pf.resize(mx + 1);
        rep(i, mx + 1) pf[i] = i;
        for (int i = 2; i <= mx; ++i) {
            if (pf[i] == i) ps.push_back(i);
            rep(j, ps.size()) {
                int x = ps[j] * i;
                if (x > mx) break;
                pf[x] = ps[j];
            }
        }
    }

    bool primeSubOperation(vector<int>& nums) {
        sieve(1000);
        int pre = 0;
        for (int x : nums) {
            if (x <= pre) return false;
            int mn = x;
            for (int p : ps) {
                if (x-p <= pre) break;
                mn = x-p;
            }
            pre = mn;
        }
        return true;
    }
};

using ll = long long;
class Solution {
public:
    vector<long long> minOperations(vector<int>& nums, vector<int>& queries) {
        int n = nums.size(), m = queries.size();
        sort(nums.begin(), nums.end());
        vector<int> ord(m);
        iota(ord.begin(), ord.end(), 0);
        sort(ord.begin(), ord.end(), [&](const int i, const int j) {
            return queries[i] < queries[j];
        });
        int i = 0;
        ll l = 0, r = reduce(nums.begin(), nums.end(), 0ll);
        vector<ll> res(m);
        for (const int qi : ord) {
            for (; i < n and nums[i] < queries[qi]; ++i) {
                l += nums[i];
                r -= nums[i];
            }
            res[qi] = r-l-1ll*queries[qi]*(n-i-i);
        }
        return res;
    }
};

class Solution {
public:
    int collectTheCoins(vector<int>& coins, vector<vector<int>>& edges) {
        const int n = coins.size();
        vector<set<int>> to(n);
        for (auto e : edges) {
            int a = e[0], b = e[1];
            to[a].insert(b);
            to[b].insert(a);
        }
        queue<int> q;
        for (int i = 0; i < n; ++i) {
            if (to[i].size() == 1 and !coins[i]) {
                q.push(i);
            }
        }
        vector<bool> used(n);
        while (q.size()) {
            int v = q.front(); q.pop();
            used[v] = true;
            int u = *to[v].begin();
            to[u].erase(v);
            to[v].clear();
            if (to[u].size() == 1 and !coins[u]) q.push(u);
        }
        vector<int> dist(n, -1);
        for (int i = 0; i < n; ++i) {
            if (!used[i] and to[i].size() == 1) {
                dist[i] = 0;
                q.push(i);
            }
        }
        while (q.size()) {
            int v = q.front(); q.pop();
            used[v] = true;
            int u = *to[v].begin();
            to[u].erase(v);
            to[v].clear();
            dist[u] = max(dist[u], dist[v]+1);
            if (to[u].size() == 1 and dist[u] <= 1) q.push(u);
        }
        return 2*(max(static_cast<int>(count(used.begin(), used.end(), false)), 1) - 1);
    }
};

算法分析

可以考虑用并查集来维护强连通分量，而操作 $2$ 的答案就是点 $x$ 所在小组中的最小编号

C++ 代码

#include <bits/stdc++.h>
#if __has_include(<atcoder/all>)
#include <atcoder/all>
using namespace atcoder;
#endif
#define rep(i, n) for (int i = 0; i < (n); ++i)

using namespace std;
using ll = long long;

int main() {
    int n;
    cin >> n;

    vector<int> p(n, -1);
    rep(i, n-1) {
        cin >> p[i+1];
        p[i+1]--;
    }

    dsu uf(n);
    vector<int> root(n);
    rep(i, n) root[i] = i;
    auto get = [&](int v) -> int& {
        return root[uf.leader(v)];
    };
    auto merge = [&](int a, int b) {
        int r = min(get(a), get(b));
        uf.merge(a, b);
        get(a) = r;
    };

    int q;
    cin >> q;
    rep(qi, q) {
        int type;
        cin >> type;
        if (type == 1) {
            int u, v;
            cin >> u >> v;
            --u; --v;
            while (!uf.same(u, v)) {
                u = get(u);
                merge(u, p[u]);
            }
        }
        else {
            int x;
            cin >> x;
            --x;
            int ans = get(x)+1;
            cout << ans << '\n';
        }
    }

    return 0;
}

class Solution {
public:
    string shortestCommonSupersequence(string s1, string s2) {
        int n = s1.size(), m = s2.size();
        vector dp(n+1, vector<int>(m+1));
        for (int i = 0; i < n; ++i) {
            dp[i][m] = n-i;
        }
        for (int i = 0; i < m; ++i) {
            dp[n][i] = m-i;
        }
        for (int i = n-1; i >= 0; --i) {
            for (int j = m-1; j >= 0; --j) {
                if (s1[i] == s2[j]) {
                    dp[i][j] = dp[i+1][j+1]+1;
                }
                else {
                    dp[i][j] = min(dp[i+1][j], dp[i][j+1])+1;
                }
            }
        }

        string res;
        int i = 0,  j = 0;
        while (i < n and j < m) {
            if (s1[i] == s2[j]) {
                res += s1[i];
                ++i;
                ++j;
            }
            else if (dp[i+1][j] == dp[i][j]-1) {
                res += s1[i];
                ++i;
            }
            else if (dp[i][j+1] == dp[i][j]-1) {
                res += s2[j];
                ++j;
            }
        }
        if (i < n) res += s1.substr(i);
        else if (j < m) res += s2.substr(j);
        return res;
    }
};