第二届ACM协会算法校内赛正式赛

发表于 2024-03-18 更新于 2024-07-19 分类于题解阅读次数： 1 本文字数： 1.7k 阅读时长 ≈ 6 分钟

It is easier to get than to keep it.

A. 莉丝缇亚

思路：

输出 $x \times 2$

时间复杂度： $O (1)$

t = int(input())

while t > 0:
    t -= 1
    a = int(input())
    print(a << 1)

B. 骰子之神

思路：

输出 20 为必胜态

时间复杂度： $O (1)$

print(20)

C. 风导星歌、黎明ノ景

思路：

前缀和维护区间数量
二分那个大于等于 k 的位置，然后减去 l即可

时间复杂度： $O (n l o g n)$

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

    int N, Q;
    std::cin >> N >> Q;

    std::vector<int> a(N);
    for (int i = 0; i < N; i++) {
        std::cin >> a[i];
    }
    std::vector<i64> s(N + 1);
    for (int i = 0; i < N; i++) {
        s[i + 1] = s[i] + a[i]; 
    }

    while (Q--) {
        int l, v;
        std::cin >> l >> v;

        if (s[N] - s[l - 1] < v) {
            std::cout << "-1\n";
            continue;
        }

        int l1 = l, r = N;
        while (l1 <= r) {
            int mid = l1 + r >> 1;
            auto check = [&](int x) {
                i64 k = s[x] - s[l - 1];
                return k >= v;
            };
            if (check(mid)) {
                r = mid - 1;
            } else {
                l1 = mid + 1;
            }
        }
        std::cout << l1 - l << "\n";
    }  

    return 0;
}

D. 木栅栏与栅栏门

思路：

比赛的时候有点紧张，下来直接过了
数学推一下

时间复杂度： $O (1)$

void solve() {
    int n;
    std::cin >> n;

    int t = (n + 2) / 3;
    if (t & 1) {
        std::cout << (t / 2 * 10 + 6) / 4 << "\n";
    } else {
        std::cout << (t / 2 * 10) / 4 << "\n";
    }
}

E. 加密通信

思路：

暴力枚举即可，枚举 x 和 y

时间复杂度： $O (n^{2})$

void solve() {
    int S;
    std::cin >> S;

    int ans = 0;
    for (int i = 0; i <= S; i++) {
        for (int j = 0; j <= S; j++) {
            if (i + j > S) continue ;
            int x = i, y = j * j * j, z = S - i - j;
            if ((x ^ y) == z) {
                ans++;
            }
        }
    }
    std::cout << ans << "\n";
}

F. 琪露诺的魔法九宫格

思路：

贪心找到最大的行和列的贡献，然后减去重复的位置即可

时间复杂度： $O (n^{2})$

struct Matrix {
    int g[15][15];

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

    void init(int n) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                std::cin >> g[i][j];
            }
        }
    }
};

void solve() {
    Matrix A(9), B(9);
    
    std::vector<std::pair<int, int>> row(9);
    for (int i = 0; i < 9; i++) {
        int a = std::accumulate(A.g[i], A.g[i] + 9, 0);
        int b = std::accumulate(B.g[i], B.g[i] + 9, 0);
        row[i] = {b - a, i};
    }

    std::vector<std::pair<int, int>> col(9);
    for (int j = 0; j < 9; j++) {
        int sum = 0;
        for (int i = 0; i < 9; i++) {
            sum += B.g[i][j] - A.g[i][j];
        }
        col[j] = {sum, j + 9};
    }

    std::vector<std::pair<int, int>> s(9);
    for (int i = 0; i < 9; i++) {
        s.push_back(col[i]);
        s.push_back(row[i]);
    }

    std::sort(s.rbegin(), s.rend());

    int x;
    std::cin >> x;
    
    int ans = 0;
    std::vector<std::vector<int>> vis(9, std::vector<int>(9));
    for (int j = 0; j < x; j++) {
        if (s[j].second >= 9) {
            for (int i = 0; i < 9; i++) {
                if (vis[i][s[j].second % 9]) ans -= B.g[i][s[j].second % 9];
                vis[i][s[j].second % 9] = true;
                if (vis[i][s[j].second % 9])
                    ans += B.g[i][s[j].second % 9];
            }
        } else {
            for (int i = 0; i < 9; i++) {
                if (vis[s[j].second % 9][i]) ans -= B.g[s[j].second % 9][i];
                vis[s[j].second % 9][i] = true;
                if (vis[s[j].second % 9][i])
                    ans += B.g[s[j].second % 9][i];
            }
        }
    }

    for (int i = 0; i < 9; i++) {
        for (int j = 0; j < 9; j++) {
            vis[i][j] ? ans += 0 : ans += A.g[i][j];
        }
    }

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

G. 东方永夜抄

思路：

直接暴力枚举距离，然后和半径 r 进行比较即可

时间复杂度： $O (q s)$

void solve() {
    int s;
    std::cin >> s;

    std::vector<int> x(s), y(s), r(s);
    for (int i = 0; i < s; i++) {
        std::cin >> x[i] >> y[i] >> r[i];
    }

    int q;
    std::cin >> q;

    int ans = 0;
    std::vector<int> vis(s);
    for (int i = 0; i < q; i++) {
        int a, b;
        std::cin >> a >> b;

        for (int j = 0; j < s; j++) {
            if (!vis[j]) {
                if (std::hypot(abs(a - x[j]), abs(b - y[j])) <= r[j]) {
                    ans++;
                    vis[j] = true;
                }
            }
        }
    }
    std::cout << ans << "\n";
}

xxxxxxxxxx void solve() { int n; std::cin >> n; std::set st; for (int i = 0; i < n; i++) { int k; std::cin >> k; for (int j = 0; j < k; j++) { std::string s; std::cin >> s; st.insert(s); } } std::cout << st.size() << "";}cpp

思路：

暴力枚举所有的冰淇淋机器，选过的直接标记跳过，类似于八皇后，当枚举出界就结束这个分支
然后我们在枚举的过程中记录这个结果

时间复杂度： $O (2^{9} \times 9^{2})$

解法一：状压 DP

constexpr int inf = 0x3f3f3f3f;

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

    std::vector g(10, std::vector<int>(10));
    for (int i = 1; i <= 9; i++) {
        for (int j = 1; j <= 9; j++) {
            std::cin >> g[i][j];
        }
    }
    
    std::vector dp(10, std::vector<int>(1 << 9, inf));
    dp[0][0] = 0;
    
    std::vector<int> ans(10, inf);
    for (int i = 1; i <= 9; i++) {
        for (int S = 0; S < 1 << 9; S++) {
            for (int j = 0; j < 9; j++) {
                if (~(S >> j) & 1) {
                    dp[i][S | 1 << j] = std::min(dp[i][S | 1 << j], dp[i - 1][S] + g[j + 1][i]);
                }
            }
            ans[i] = std::min(ans[i], dp[i][S]);
        }
    }
    
    for (int i = 1; i <= 9; i++) {
        std::cout << ans[i] << ' ';
    }
    
    return 0;
}

解法二：暴搜

constexpr int inf = 0x3f3f3f3f;

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

    std::vector g(10, std::vector<int>(9));
    for (int i = 1; i <= 9; i++) {
        for (int j = 0; j < 9; j++) {
            std::cin >> g[i][j];
        }
    }
    
    std::vector<int> ans(10, inf);
    for (int i = 1; i <= 9; i++) {
        std::vector<int> vis(10);
        std::function<void(int, int, int)> dfs = [&](int x, int k, int cost) {
            if (x < k) {
                ans[i] = std::min(ans[i], cost);
                return ;
            }
            for (int i = 1; i <= 9; i++) {
                if (vis[i]) continue ;
                vis[i] = true;
                dfs(x, k + 1, cost + g[i][k - 1]);
                vis[i] = false;
            }
        };
        dfs(i, 1, 0);
    }
    
    for (int i = 1; i <= 9; i++) {
        std::cout << ans[i] << ' ';
    }
    
    return 0;
}

I. 吉他与孤独与蓝色星球 (Easy ver)

思路：

因为是双向道路，所以直接用最小的那个和其他的挨个连接
答案为 $(n - 2) \times a_{x} + Σ_{i = 1}^{n} a_{i}$

时间复杂度： $O (n l o g n)$

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

    int N;
    std::cin >> N;

    std::vector<int> a(N);
    for (int i = 0; i < N; i++) {
        std::cin >> a[i];
    }

    std:sort(a.begin(), a.end());

    i64 ans = 0;
    for (int i = 1; i < N; i++) {
        ans += a[i] + a[0];
    }
    std::cout << ans << "\n";

    return 0;
}

J. Never (Hard ver)

思路：

给个Akashi的官方题解

时间复杂度：

signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int n;
    std::cin >> n;

    std::vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) {
        std::cin >> a[i];
    }

    std::vector<i64> f(n + 1), g(n + 1), h(n + 1);
    for (int i = 1; i <= n; i++) {
        if (a[i] == 1) {
            g[i] = g[i - 1];
            f[i] = f[i - 1] + g[i];
            h[i] = h[i - 1] + 1;
        }
        if (a[i] == 2) {
            f[i] = f[i - 1];
            h[i] = h[i - 1];
            g[i] = g[i - 1] + 1;
        }
        if (a[i] == 3) {
            f[i] = f[i - 1];
            g[i] = g[i - 1] - 1;
            h[i] = h[i - 1];
        }
    }

    int q;
    std::cin >> q;

    while (q--) {
        int l, r;
        std::cin >> l >> r;

        std::cout << f[r] - f[l - 1] - (h[r] - h[l - 1]) * g[l - 1] << "\n"; 
    }
    
    return 0;
}

K. 铁路调度模拟器

思路：

直接并查集维护每一个站点的集合，并查集板子题

时间复杂度： $O (2 M \times l o g (2 M))$

struct DSU {
    std::vector<int> f, siz;

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

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

    int find(int x) {
        while (x != f[x]) {
            x = f[x] = f[f[x]];
        }
        return x;
    }

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

    bool merge(int x, int y) {
        x = find(x);
        y = find(y);
        if (x == y) {
            return false;
        }
        siz[y] += siz[x];
        f[x] = y;
        return true;
    }

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

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

    int m, q;
    std::cin >> m >> q;

    DSU f(1000010);

    int tot = 1;
    std::map<std::string, int> mp;
    for (int i = 0; i < m; i++) {
        std::string a, b;
        std::cin >> a >> b;
        if (!mp.count(a))
            mp[a] = tot++;
        if (!mp.count(b))
            mp[b] = tot++;
        f.merge(mp[a], mp[b]);
    }

    while (q--) {
        std::string x, y;
        std::cin >> x >> y;

        if (x == y) {
            std::cout << "1\n";
        } else if (!mp.count(x) || !mp.count(y)) {
            std::cout << "0\n";
        } else {
            if (f.same(mp[x], mp[y])) {
                std::cout << "1\n";
            } else {
                std::cout << "0\n";
            }
        }
    }

    return 0;
}

A. 莉丝缇亚

B. 骰子之神

C. 风导星歌、黎明ノ景

D. 木栅栏与栅栏门

E. 加密通信

F. 琪露诺的魔法九宫格

G. 东方永夜抄

xxxxxxxxxx void solve() { int n; std::cin >> n;​ std::set st; for (int i = 0; i < n; i++) { int k; std::cin >> k; for (int j = 0; j < k; j++) { std::string s; std::cin >> s; st.insert(s); } } std::cout << st.size() << "";}cpp

I. 吉他与孤独与蓝色星球 (Easy ver)

J. Never (Hard ver)

K. 铁路调度模拟器

xxxxxxxxxx void solve() { int n; std::cin >> n; std::set st; for (int i = 0; i < n; i++) { int k; std::cin >> k; for (int j = 0; j < k; j++) { std::string s; std::cin >> s; st.insert(s); } } std::cout << st.size() << "";}cpp