“山大地纬杯”第十二届山东省ICPC大学生程序设计竞赛(正式赛）

#include "bits/stdc++.h"

using namespace std;
using i64 = long long;

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

#define x real
#define y imag

constexpr Real eps = 1E-9;

int sign(const Real &x) {
    return x < -eps ? -1 : x > eps ? 1 : 0;
}

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

struct Segment : Line {
    Segment() = default;
    using Line::Line;
};

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

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

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

Real area(const Point &a, const Point &b, const Point &c) {
  return abs(cross(b - a, c - a));
}

Point cpoints(const Line &l, const Segment &s) {
  	return {s.a + (s.b - s.a) * cross(l.b - l.a, l.b - s.a) / cross(l.b - l.a, s.b - s.a)};
}

Real area(const vector<Point> &g) {
    int SIZE = g.size();
    Real res = 0;
    for (int i = 1; i < SIZE - 1; i++) {
        res += area(g[0], g[i], g[i + 1]);
    }
    return res;
}

bool intersect(const Line &l, const Segment &s) { 
    return cross(l.b - l.a, s.a - l.a) * cross(l.b - l.a, s.b - l.a) <= 0; 
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout << fixed << setprecision(15);
    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 m;
    cin >> m;
    vector<Point> b(m);
    for (int i = 0; i < m; i++) {
        int x, y;
        cin >> x >> y;
        b[i] = Point(x, y);
    }
    Real ans = 0;
    for (int i = 0; i < m; i++) {
        vector<Point> g;
        Line L(b[i], b[(i + 1) % m]);
        for (int j = 0; j < n; j++) {
            Segment S(a[j], a[(j + 1) % n]);
            if (onLeft(a[j], L) == -1) {
                g.push_back(a[j]);
            }
            if (intersect(L, S)) {
                g.push_back(cpoints(L, S));
            }
        }
        ans = max(ans, area(g));
    }
    cout << ans / 2.0 << '\n';
    return 0;
}

#include "bits/stdc++.h"

using namespace std;
using i64 = long long;

constexpr int P = 998244353;

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

    int n, x;
    cin >> n >> x;

    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }    

    if (x == 0) {
        i64 ans = 0;
        int l = 0;
        for (int i = 0; i < n; i++) {
            if (a[i] == 0) {
                ans += 1LL * (i + 1 - l) * (n - i);
                l = i + 1;
            }
        }
        cout << ans << '\n';
        return 0;
    }

    map<int, int> mp;
    i64 ans = 0;
    i64 now = 1;
    mp[x]++;
    for (int i = 0; i < n; i++) {
        if (a[i] == 0) {
            mp.clear();
            mp[x]++;
            now = 1;
        } else {
            now *= a[i];
            now %= P;
            ans += mp[now];
            mp[now * x % P]++;
        }
    }
    cout << ans << '\n';        


    return 0;
}

#include "bits/stdc++.h"

using namespace std;
using i64 = long long;

constexpr int N = 2E6;

int A[N + 1];
int B[N + 1];

void init() {
    for (int i = 1; i <= N; i++) {
        A[i] = -1;
    }
    for (int i = 2; i <= N; i++) {
        if (A[i - 2] != -1) {
            A[i] = A[i - 2] + 1;
        }
        if (i >= 3 && A[i - 3] != -1) {
            A[i] = A[i - 3] + 1;
        }
        if (i >= 17 && A[i - 17] != -1) {
            A[i] = A[i - 17] + 1;
        }
        if (i >= 19 && A[i - 19] != -1) {
            A[i] = A[i - 19] + 1;
        }
    }
    for (int i = 1; i <= N; i++) {
        B[i] = -1;
    }
    for (int i = 5; i <= N; i++) {
        if (B[i - 5] != -1) {
            B[i] = B[i - 5] + 1;
        }
        if (i >= 7 && B[i - 7] != -1) {
            B[i] = B[i - 7] + 1;
        }
        if (i >= 11 && B[i - 11] != -1) {
            B[i] = B[i - 11] + 1;
        }
        if (i >= 13 && B[i - 13] != -1) {
            B[i] = B[i - 13] + 1;
        }
    }
    for (int i = 0; i <= N; i++) {
        if (A[i] == -1) {
            A[i] = 2E9;
        }
        if (B[i] == -1) {
            B[i] = 2E9;
        }
    }
}

int getA(int n) {
    if (n <= N) {
        return A[n];
    } else {
        return A[n - ((n - N) / 19 + 1) * 19] + ((n - N) / 19 + 1);
    }
}

int getB(int n) {
    if (n <= N) {
        return B[n];
    } else {
        return B[n - ((n - N) / 13 + 1) * 13] + ((n - N) / 13 + 1);
    }
}

void solve() {
    int n;
    cin >> n;

    int a = getA(n);
    int b = getB(n);

    if (a == b && b != 2E9) {
        cout << "both\n"; 
    } else if (a == 2E9 && b == 2E9) {
        cout << -1 << '\n';
    } else if (a < b) {
        cout << "A\n";
    } else {
        cout << "B\n";
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    init();
    
    int t;
    cin >> t;

    while (t--) {
        solve();
    }

    return 0;
}