526互联

The 2022 ICPC Asia Nanjing Regional Contest

发布时间 2023-09-05 13:39:30作者: Kidding_Ma

链接：https://codeforces.com/gym/104128

A. Stop, Yesterday Please No More

#include "bits/stdc++.h"

using namespace std;
using i64 = long long;

void solve() {
    int n, m, k;
    cin >> n >> m >> k;
    string s;
    cin >> s;
    int len = s.size();
    int u = 1, d = n, l = 1, r = m;
    int mnx = 1, mxx = n, mny = 1, mxy = m;
    for (int i = 0; i < len; i++) {
        if (s[i] == 'U') {
            u++;
            d++;
        } else if (s[i] == 'D') {
            u--;
            d--;
        } else if (s[i] == 'L') {
            l++;
            r++;
        } else {
            l--;
            r--;
        }

        mnx = max(mnx, u);
        mxx = min(mxx, d);
        mny = max(mny, l);
        mxy = min(mxy, r);
    }

    if (mnx > mxx || mny > mxy) {
        if (k == 0) {
        cout << n * m << '\n';
        return;
        }
        cout << 0 << '\n';
        return;
    }

    int res = (mxx - mnx + 1) * (mxy - mny + 1) - k;
    vector<vector<i64>> pre(2 * n + 1, vector<i64>(2 * m + 1));
    int x = n + 1, y = m + 1;
    pre[x][y] = 1;
    for (int i = 0; i < len; i++) {
        if (s[i] == 'U') {
            x++;
        } else if (s[i] == 'D') {
            x--;
        } else if (s[i] == 'L') {
            y++;
        } else {
            y--;
        }
        pre[x][y] = 1;
    }

    for (int i = 1; i <= 2 * n; i++) {
        for (int j = 1; j <= 2 * m; j++) {
            pre[i][j] += pre[i - 1][j] + pre[i][j - 1] - pre[i - 1][j - 1];
        }
    }

    int ans = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            int U = mnx - i + n + 1;
            int D = mxx - i + n + 1;
            int L = mny - j + m + 1;
            int R = mxy - j + m + 1;
            if (pre[D][R] - pre[U - 1][R] - pre[D][L - 1] + pre[U - 1][L - 1] == res) {
                ans++;
            }
        }
    }
    cout << ans << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int tt;
    cin >> tt;
    while (tt--) {
        solve();
    }
    return 0;
}

G. Inscryption

#include "bits/stdc++.h"

using namespace std;
using i64 = long long;

void solve() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    int cnt = 0;
    int ans1 = 1, ans2 = 1;
    for (int i = 0; i < n; i++) {
        if (a[i] == 1) {
            ans1++;
            ans2++;
        } else if (a[i] == -1) {
            if (ans2 >= 2) {
                ans2--;
            } else if (cnt >= 1) {
                cnt--;
                ans1++;
                ans2++;
            } else {
                cout << -1 << '\n';
                return;
            }
            } else {
            if (ans2 >= 2) {
                ans2--;
                cnt++;
            } else {
                ans1++;
                ans2++;
            }
        }
    }
    int g = gcd(ans1, ans2);
    cout << ans1 / g << ' ' << ans2 / g << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int tt;
    cin >> tt;
    while (tt--) {
        solve();
    }
    return 0;
}

I. Perfect Palindrome

#include "bits/stdc++.h"

using namespace std;
using i64 = long long;

void solve() {
    string s;
    cin >> s;
    vector<int> cnt(26);
    for (int i = 0; i < (int) s.size(); i++) {
        cnt[s[i] - 'a']++;
    }
    int ans = s.size();
    for (int i = 0; i < 26; i++) {
        ans = min(ans, (int) s.size() - cnt[i]);
    }
    cout << ans << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int tt;
    cin >> tt;
    while (tt--) {
        solve();
    }
    return 0;
}

M. Drain the Water Tank

#include "bits/stdc++.h"

using namespace std;
using i64 = long long;

using Real = i64;
using Point = complex<Real>;

#define x real
#define y imag

Real cross(const Point &a, const Point &b) {
    return (conj(a) * b).imag();
}

Real dot(const Point &a, const Point &b) {
    return (conj(a) * b).real();
}

struct Line {
    Point a, b;
    Line() = default;
    Line(const Point &a, const Point &b) : a(a), b(b) {}
};

int onLeft(const Point &p, const Line &l) {
    return cross(l.b - l.a, p - l.a);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n;
    cin >> n;
    vector<Point> a(n);

    for (int i = 0; i < n; i++) {
        int x, y;
        cin >> x >> y;

        a[i] = Point(x, y);
    }

    int ans = 0;
    for (int i = 0, j = 1; i < n; i++) {
        while (a[i].y() == a[j].y()) {
            j++;
            j %= n;
        }
        if (a[i].y() < a[(i + n - 1) % n].y() && a[i].y() < a[j].y()) {
            if (a[i].y() != a[(i + 1) % n].y()) {
                if (onLeft(a[(i + n - 1) % n], Line(a[i], a[j])) > 0) {
                    ans++;
                }
            } else {
                if (a[i].x() < a[(i + 1) % n].x()) {
                    ans++;
                }
            }
        }
    }

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