第二届ACM协会算法校内赛 热身赛

发表于 更新于 分类于 阅读次数： 本文字数： 1k 阅读时长 ≈ 4 分钟
Many a little makes a mackle.

A. 东方红红绿绿蓝

思路：

  • 仔细审题，按规则模拟

时间复杂度：\(O(n)\)​

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
void solve() {
    int n;
    std::cin >> n;

    std::string s;
    std::cin >> s;

    int ans = 0, G = 0, B = 0, R = 0;
    for (int i = 0; i + 5 <= n; i += 5) {
        std::string t = s.substr(i, 5);
        int a = 0, b = 0, c = 0;
        for (int j = 0; j < 5; j++) {
            if (t[j] == 'R') {
                a++;
            } else if (t[j] == 'B') {
                b++;
            } else if (t[j] == 'G') {
                c++;
            }
        }
        if (a >= 3) {
            R++;
        } else if (b >= 3) {
            B++;
        } else if (c >= 3) {
            G++;
        } else {
            ans++;
        }
    }
    std::cout << ans << " " << R << " " << G << " " << B << '\n';
}

B. 洛天依

思路：

  • 枚举 \(a\) ，二分 \(b\)，然后带入公式维护最大值

据说有暴力做法

时间复杂度：\(O(nlogn)\)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void solve() {
    int n, m, S;
    std::cin >> n >> m >> S;

    i64 ans = 0;
    for (int i = 0; i <= n; i++) {
        i64 val = i;
        int l = 0, r = m;
        while (l <= r) {
            int mid = l + r >> 1;
            if (val + 1LL * (i + mid) * (i + mid) <= S) {
                ans = std::max(ans, val + 1LL * (i + mid) * (i + mid));
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }
        if (i > S) break;
    }    
    std::cout << ans << "\n";
}

C. 珈百璃的小学妹

题目大意：

  • 任选两个index然后，对其分别进行 +3和-1操作

思路：

  • 注意，可以选相同index，也就是意味着对一个位置+2，所以我们只需要求奇偶的个数即可，如果奇数或者偶数mod 2为0，那么就是一个合法的序列

时间复杂度：\(O(n)\)​

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void solve() {
    int n;
    std::cin >> n;

    int odd = 0;
    for (int i = 0; i < n; i++) {
        int x;
        std::cin >> x;
        odd += x & 1;
    }
    if (odd % 2 == 0 || (n - odd) % 2 == 0) {
        std::cout << "YES\n";
    } else {
        std::cout << "NO\n";
    }
}

D. 动态规划热身

思路：

  • 将所有的数按照右端点排序，然后二分距离当前这个数左端点最近的右端点，然后我们用 dp来维护最大值的和

时间复杂度：\(O(nlogn)\)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
void solve() {
    int n, k;
    std::cin >> n >> k;

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

    std::sort(a.begin() + 1, a.end(), [&](auto i, auto j) {
        if (i[1] == j[1]) {
            return i[0] > j[0];
        }
        return i[1] < j[1];
    });

    int mx = 0;
    std::vector<int> dp(n + 1);
    for (int i = 1; i <= n; i++) {
        dp[i] = std::max(dp[i - 1], a[i][2]);
    }

    for (int i = 1; i <= n; i++) {
        int cur = a[i][0]; // 当前点的左端点
        int l = 1, r = i;
        while (l < r) {
            int mid = l + r + 1 >> 1;
            auto check = [&](int x) {
                int ir = a[x][1];
                return cur - ir < k;
            };
            if (check(mid)) {
                r = mid - 1;
            } else {
                l = mid;
            }
        }
        if (cur - a[l][1] >= k) {
            dp[i] = std::max(dp[l] + a[i][2], dp[i]);
        }
        dp[i] = std::max(dp[i], dp[i - 1]);
    }
    std::cout << dp[n] << "\n";
    
}

E. Tiny snow

思路：

  • 考虑三种情况即可
    1. 上面的最左边的两个端点和下面最右边的两个端点的距离和
    2. 上面的最右边的两个端点和下面最左边的两个端点的距离和
    3. 上面任意两个相邻的点到下面最左端的点和最右端的点的距离和

时间复杂度：\(O(n)\)​

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
void solve() {
    int n, m, D;
    std::cin >> n >> m >> D;

    std::vector<double> u(n), d(m);
    for (int i = 0; i < n; i++) {
        std::cin >> u[i];
    }
    for (int i = 0; i < m; i++) {
        std::cin >> d[i];
    }

    auto dist = [&](double x1, double y1, double x2, double y2) {
        double a = std::hypot(D, abs(x1 - y1));
        double b = std::hypot(D, abs(x2 - y2));
        return a + b;
    };

    double ans = 0;
    for (int i = 0, j; i + 1 < n; i++) {
        j = i + 1;
        ans = std::max(ans, dist(u[i], d[0], u[j], d[m - 1]));
        ans = std::max(ans, dist(u[i], d[m - 2], u[j], d[m - 1]));
        ans = std::max(ans, dist(u[i], d[0], u[j], d[1]));
    }
    std::cout << ans << "\n";
}

F. 社团嘉年华

思路：

  • 除了 1 其他的就暴力枚举就好了

时间复杂度：\(O(n\sqrt n)\)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
void solve() {
    int n, m;
    std::cin >> n >> m;

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

    int cnt = 0;
    std::vector<int> d(n + 1);
    for (int i = 0; i < m; i++) {
        if (x[i] == 1) {
            cnt++;
        } else {
            for (int j = x[i]; j <= n; j += x[i]) {
                d[j] += 1;
            }
        }
    }

    int ans = 0;
    for (int i = 1; i <= n; i++) {
        if ((cnt + d[i]) % 2 == 0) {
            ans++;
        }
    }
    std::cout << ans << "\n";
}

G. 要素过多

思路：

  • 用 \(set\) 直接维护个数

时间复杂度：\(O(nlogn)\)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void solve() {
    int n;
    std::cin >> n;

    std::set<std::string> 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() << "\n";
}