【2024暑108】ACM暑期第三次测验（个人赛）题解

A - 猫抓老鼠

Solution

经典的逆序对问题，这里就不过多阐述了

有递归和树状数组两种写法，自行百度即可

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
    freopen ("A.in", "r", stdin);
    int n; cin >> n;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) cin >> a[i];
    
    ll ans = 0;

    auto cdq = [&] (auto cdq, int L, int R) {
        if (L == R) return;
        int mid = (L + R) / 2;
        cdq(cdq, L, mid); cdq(cdq, mid + 1, R);
        int l = L, r = mid + 1;
        vector<int> tmp;
        while (l <= mid || r <= R) {
            if (r > R || (l <= mid && a[l] <= a[r])) {
                tmp.push_back(a[l]); l++;
            } else {
                tmp.push_back(a[r]); r++;
                ans += mid - l + 1;
            }
        }
        for (int i = L; i <= R; i++) a[i] = tmp[i - L];
    };

    cdq(cdq, 1, n);
    cout << ans << endl;
    return 0;
}

B - 字符变换

Solution

查看 $(S [i] - T [i]) % 26$ 是否相同即可

Code

#include <bits/stdc++.h>
using namespace std;
int main() {
    string S, T; cin >> S >> T;
    set<int> st;
    for (int i = 0; i < S.size(); i++) {
        int cz = (S[i] - T[i] + 26) % 26;
        st.insert(cz);
    }
    cout << (st.size() == 1 ? "Yes" : "No") << endl;
    return 0;
}

C - 7777777

Solution

首先，如果我们删除了一些 7，如果仍然存在从原点看不到的 7，则我们也可以删除这些 7，而不会改变从原点看到的 7 的数量。

因此，问题可以重新表述如下：

给定 $N$ 个 7，你可以删除其中一些，以便所有剩余的 7 都可以从原点看到。找到剩余 7 的最大数量。

此外，我们可以把每个 7 视为一个开区间，区间的两端对应于其两个端点的极角，这样问题就可以重新表述如下：

给定 $N$ 个开放区间。第 $i$ 个区间的左端点为 $f (x_{i}, y_{i} - 1)$ ，右端点为 $f (x_{i} - 1, y_{i})$ ，其中 $f (i, j)$ 是一个由两个实数 $(i, j)$ 表示坐标 $(i, j)$ 极角的函数。

最多可以选择多少个区间，使得任意两个区间不重叠？

这就是著名的区间调度问题。可以通过以下贪心算法解决，同样可以应用于这个问题。

重复以下操作。

让 $R_{max}$ 成为已选择区间中（右端点的）最大坐标。如果存在尚未选择的区间，其左端点坐标大于或等于 $R_{max}$ ，则选择其中右端点最小的区间。

否则，如果不存在左端点坐标大于等于 $R_{max}$ 的区间，则终止过程。

在实现时，将 $N$ 个区间按其右端点坐标的递增顺序排序。然后维护 $R_{max}$ ，如果某个区间的左端点大于等于 $R_{m a x}$ ，那么直接把 $R_{max}$ 更新成当前区间的右端点

时间复杂度为 $O (N \log N)$ 。

Code

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

struct Frac {
    ll p, q; // p / q
    Frac(ll p = 0, ll q = 1) : p(p), q(q) {}
    bool operator < (const Frac &f) const { return p * f.q < q * f.p; }
    bool operator <= (const Frac &f) const { return p * f.q <= q * f.p; }
};

int main() {
    int N; cin >> N;
    vector<ll> x(N), y(N);
    for (int i = 0; i < N; i++) cin >> x[i] >> y[i];
    vector<pair<Frac, Frac>> que(N);
    for (int i = 0; i < N; i++) que[i] = make_pair(Frac(y[i], x[i] - 1), Frac(y[i] - 1, x[i]));
    sort(que.begin(), que.end());
    int cnt = 0;
    Frac R_max = Frac(0, 1);
    for (auto cur : que) {
        if (R_max <= cur.second) { // cur.second 是左端点
            cnt += 1;
            R_max = cur.first; // 更新右端点
        }
    }
    cout << cnt << endl;
    return 0;
}

D - 武术大师

Solution

可以使用记忆化 DFS，当然，由于满足 $A_{i, j} < i$ 说明需要在 $i$ 之前学的招式都是在 $i$ 之前出现过的，所以我们从后往前，记录一个数组 $u s e d [i]$ 表示 $i$ 是否需要学习，如果 $u s e d [i] = 1$ 表示需要学习，那么把 $i$ 之前需要学的招式 $j$ 都标记为 $1$

注意，这里的 $A_{i, j}$ 最好使用 $v e c t o r$ 来存储

Code

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    int n; cin >> n;
    vector<vector<int>> p(n, vector<int>());
    vector<int> T(n), K(n);
    for (int i = 0; i < n; i++) {
        cin >> T[i] >> K[i];
        for (int j = 0; j < K[i]; j++) {
            int x; cin >> x;
            p[i].push_back(x);
        }
    }
    vector<int> used(n, 0); used[n - 1] = 1;
    for (int i = n - 1; i >= 0; i--) {
        if (used[i]) {
            for (int j = 0; j < K[i]; j++) {
                used[p[i][j] - 1] = 1;
            }
        }
    }
    long long ans = 0;
    for (int i = 0; i < n; i++) 
        ans += T[i] * used[i];
    cout << ans << endl;
    return 0;
}

E - 扫雷

Solution

因为 $N$ 很小，直接暴力 dfs 就可以了

但是正解是使用 DP 来做的

定义 $F [i]$ 表示以第 $i$ 节点结束的最大值，则

f [i] = max f [j] + a [i] (g [i] [j] = 1)

对于输出，使用 $p r e [i]$ 记录 $i$ 的前驱节点，然后递归输出即可

Code

#include <bits/stdc++.h>
using namespace std;

int main() {
    freopen ("E.in", "r", stdin);
    int n; cin >> n;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) cin >> a[i];
    vector<vector<int>> g(n + 1, vector<int>(n + 1, 0));
    vector<int> f(n + 1, 0), pre(n + 1, 0);
    for (int i = 1; i <= n; i++) {
        for (int j = i + 1; j <= n; j++) {
            int x; cin >> x;
            g[i][j] = x;
        }
    }
    int ans = -1, ans_i;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j < i; j++) {
            if (g[j][i] == 1 && f[j] > f[i]) {
                f[i] = f[j];
                pre[i] = j;
            }
        }
        f[i] += a[i];
        if (f[i] > ans) {
            ans = f[i];
            ans_i = i;
        }
    }

    auto print = [&](auto && print, int x) -> void {
        if (pre[x] == 0) {
            cout << x << " ";
            return;
        }
        print(print, pre[x]);
        cout << x << " ";
    };

    print(print, ans_i);
    cout << endl;
    cout << ans << endl;
    return 0;
}

F - 整除(middle)

Solution

还是容斥原理

定义 $A = {能被2整除}, B = {能被3整除}, C = {能被 7 整除}, U = 全集$

那么所求的就是 $(U - A) (U - B) C = U^{2} C - U A C - U B C + U A B C = C - A C - B C + A B C$

写成式子的形式就是：

\frac{n}{7} - \frac{n}{2 \times 7} - \frac{n}{3 \times 7} + \frac{n}{2 \times 3 \times 7}

Code

#include<bits/stdc++.h>
using namespace std;
int main() {  
    long long n;  
    cin>>n;
    long long sum= (n/7)-(n/14)-(n/21)+(n/42);  
    cout<<sum<<endl;  
    return 0;  
}