SMU Summer 2023 Contest Round 12

A. K-divisible Sum

分类讨论:

\(n > k\)时:
- \(n\)能整除\(k\)就全是\(1\)
- 不能整除,最多就是在全\(1\)的基础上再一部分\(1\)
\(n \leq k\)时:
- \(k\)能整除\(n\)就全放\(\frac{k}{n}\)
- 不能的话就在原基础上再加一部分\(1\)

#include <bits/stdc++.h>
#define int long long

using namespace std;

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

	int T;
	cin >> T;
	while (T--) {

		int n, k;
		cin >> n >> k;
		if (n > k) {
			if (n % k == 0)
				cout << 1 << '\n';
			else
				cout << 2 << '\n';
		} else {
			if (k % n == 0)
				cout << k / n << '\n';
			else
				cout << k / n + 1 << '\n';
		}

	}

	return 0;
}

B. Inflation

按顺序去模拟即可,记得要向上取整

#include <bits/stdc++.h>
#define int long long

using namespace std;

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

    int T;
    cin >> T;
    while (T--) {
        int n, k;
        cin >> n >> k;
        vector<int> p(n);
        int sum = 0;
        for (auto &i : p) {
            cin >> i;
        }

        int ans = 0;
        for (int i = 1; i < n ; i ++) {
            sum += p[i - 1];
            if (p[i] * 100 <= k * sum) continue;
            ans += (ceil(p[i] * 100.0 / k) - sum);
            sum += (ceil(p[i] * 100.0 / k) - sum);

        }
        cout << ans << '\n';
    }

    return 0;
}

C. Longest Simple Cycle

设\(dp[i]\)表示前\(i\)条链能组成环的最大点数

当\(a[i] = b[i]\)时,第\(i\)个点就是单独一个点闭环,\(dp[i] = c[i] + 1\),否则,就应该判断是否用\(a[i]\)和\(b[i]\)之间的点组成环,还是用两点之外的之前的环来组成环,当然还要包含后面的\(c[i]+1\)才能组成环

#include <bits/stdc++.h>
#define int long long

using namespace std;

typedef pair<double, double> PII;

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

    int T;
    cin >> T;
    while (T--) {
        int n;
        cin >> n;
        vector<int> c(n), a(n), b(n);
        for (auto &i : c) cin >> i;
        for (auto &i : a) cin >> i;
        for (auto &i : b) cin >> i;

        vector<int> dp(n);
        int ans = 0;

        for (int i = 1; i < n; i ++) {
            if (a[i] == b[i]) dp[i] = c[i] + 1;
            else dp[i] = max(abs(a[i] - b[i]), dp[i - 1] - abs(a[i] - b[i])) + c[i] + 1;
            ans = max(ans, dp[i]);
        }

        cout << ans << '\n';
    }

    return 0;
}