南京集训 Day 14

The fourth day of intensive training at Nanjing Foreign Language School.
第一题模拟

#include <bits/stdc++.h>
using namespace std;
int n, m;
int main() {
    cin >> n >> m;
    if (n == 0 && m != 0) {
        cout << "Impossible";
        exit(0);
    }
    if (n == 0 && m == 0) {
        cout << "0 0";
        exit(0);
    }
    if (m == 0) {
        cout << n << " " << n;
        exit(0);
    }
    if (m > n) {
        cout << m << " ";
    } else {
        cout << n << " ";
    }
    cout << n + m - 1;
    return 0;
}

第二题，还是模拟

#include <bits/stdc++.h>
using namespace std;
int n, k[10], cnt, ans, x;
int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> x;
        k[x]++;
    }
    if (k[2] % 2 == 0) {
        k[2] = k[2] / 2;
    } else {
        k[2] = k[2] / 2 + 1;
        k[1] -= 2;
    }
    if (k[1] > k[3]) {
        k[1] -= k[3];
        if (k[1] % 4 == 0) {
            k[1] = k[1] / 4;
        } else {
            k[1] = k[1] / 4 + 1;
        }
        cout << k[1] + k[3] + k[2] + k[4];
    } else {
        cout << k[2] + k[3] + k[4];
    }
    return 0;
}

第三题，继续模拟

#include <bits/stdc++.h>
using namespace std;
int n, ans;
struct qee {
    int l, r;
} a[101010];
bool cmp(qee a, qee b) {
    if (a.l != b.l) {
        return a.l < b.l;
    }
    return a.r < b.r;
}
int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i].l >> a[i].r;
    }
    sort(a + 1, a + 1 + n, cmp);
    int maxx = a[1].r, minn = a[1].l;
    for (int i = 2; i <= n; i++) {
        if (a[i].l <= maxx) {
            maxx = max(maxx, a[i].r);
            minn = min(minn, a[i].l);
        } else {
            ans += maxx - minn + 1;
            maxx = a[i].r;
            minn = a[i].l;
        }
    }
    ans += maxx - minn + 1;
    cout << ans;
    return 0;
}

第四题，DP

#include <bits/stdc++.h>
using namespace std;
int n, tot, cnt;
int dp[2000100][3];
char a[2000100];
int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    for (int i = 1; i <= n; i++) {
        tot = 0;
        cnt = 0;
        if (a[i] == &#039;A&#039;) {
            tot = 1;
        } else {
            cnt = 1;
        }
        dp[i][1] = min(dp[i - 1][1] + cnt, dp[i - 1][0] + 1);
        dp[i][0] = min(dp[i - 1][0] + tot, dp[i - 1][1] + 1);
    }
    cout << dp[n][1];
    return 0;
}