Star 的档案库

Appearance

2025春个人训练赛第一场 ​

A. Concert Tickets ​

签到

cpp
#include <iostream>

using namespace std;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int b, t, p;
    cin >> b >> t >> p;
    if (b + p <= t) cout << 'Y' << ' ' << t - b - p << endl;
    else cout << 'N' << endl;
    return 0;
}

B. Olympic Scores ​

签到

cpp
#include <iostream>

using namespace std;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int mn = 100, mx = -100, tot = 0;
    for (int i = 0; i < 5; ++i) {
        int t;
        cin >> t;
        mn = min(mn, t), mx = max(mx, t);
        tot += t;
    }
    int c;
    cin >> c;
    cout << c * (tot - mn - mx) << endl;
    return 0;
}

C. Creative Candy Consumption ​

模拟

cpp
#include <iostream>
#include <algorithm>

using namespace std;

bool win(char a, char b) {
    return a == 'R' && b == 'G' || a == 'G' && b == 'B' || a == 'B' && b == 'R';
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    string a, b;
    int c1 = 0, c2 = 0;
    cin >> a >> b;
    reverse(a.begin(), a.end()), reverse(b.begin(), b.end());
    while (!a.empty() && !b.empty()) {
        if (a.back() == b.back()) c1++, c2++, a.pop_back(), b.pop_back();
        else if (win(a.back(), b.back())) c1++, b.pop_back();
        else c2++, a.pop_back();
    }
    c1 += a.size(), c2 += b.size();
    cout << c1 << endl << c2 << endl;
    return 0;
}

D. Snail Path ​

模拟

cpp
#include <iostream>
#include <set>

using namespace std;
set<pair<int, int>> vis;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int T;
    int res = 0;
    pair<int, int> cur = {0, 0};
    vis.insert(cur);
    cin >> T;
    while (T--) {
        auto &[x, y] = cur;
        string s;
        cin >> s;
        int d = stoi(s.substr(1));
        int dx, dy;
        if (s[0] == 'N') dx = -1, dy = 0;
        else if (s[0] == 'S') dx = 1, dy = 0;
        else if (s[0] == 'W') dx = 0, dy = -1;
        else dx = 0, dy = 1;
        for (int i = 1; i <= d; ++i) {
            x += dx, y += dy;
            if (vis.count(cur)) res++;
            else vis.insert(cur);
        }
    }
    cout << res << endl;
    return 0;
}

E. Beams of Light ​

本质上是一个静态区间加，直接差分前缀和即可。

cpp
#include <iostream>

using namespace std;

const int N = 500010;
int f[N];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int n, l, q;
    cin >> n >> l >> q;
    for (int i = 1; i <= l; ++i) {
        int p, s;
        cin >> p >> s;
        f[max(1, p - s)]++, f[min(n + 1, p + s + 1)]--;
    }
    for (int i = 1; i <= n; ++i) f[i] += f[i - 1];
    for (int i = 1; i <= q; ++i) {
        int t;
        cin >> t;
        if (f[t]) cout << 'Y' << endl;
        else cout << 'N' << endl;
    }
    return 0;
}

F. Baby Hop, Giant Hop ​

设距离为 d，最快的一定是 min{⌊dk⌋+d−k⌊dk⌋,⌊dk⌋+1+k∗(⌊dk⌋+1)−d} 之一，次快的可能是上面两个中较大的，或者上面两个中途左右走一步（+2）或者放弃最后一个 k 直接走过去。

cpp
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
typedef long long LL;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    LL a, b, k, t;
    cin >> a >> b >> k >> t;
    LL d = abs(a - b);
    vector<LL> v = {d / k + (d % k), d / k + 1 + (k * (d / k + 1) - d)};
    if (d / k - 1 >= 0) v.emplace_back(d / k - 1 + (d - k * (d / k - 1)));
    v.emplace_back(v[0] + 2), v.emplace_back(v[1] + 2);
    sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()), v.end());
    cout << v[t - 1] << endl;
    return 0;
}

G. Common Card Choice ​

不难发现 n≥4 的时候永远有解，只看前四个

  • 如果是四个奇数，那么一人分两个
  • 如果三个奇数，其中一个人那两个奇数，另一个人拿偶数
  • 否则两人各拿一个偶数

所以数据非常的小，直接暴力前 min{n,4} 个即可。

cpp
#include <iostream>
#include <set>
#include <vector>

using namespace std;
typedef long long LL;
const int N = 100010;
LL a[N];

LL gcd(LL a, LL b) {
    return b ? gcd(b, a % b) : a;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int n;
    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    if (a[1] != -1) {
        if (n > 4) n = 4;
        bool f = false;
        for (int i = 1; i < (1 << n); ++i) {
            for (int j = 1; j < i; ++j) {
                if ((i | j) == i) {
                    vector<int> v1, v2;
                    LL s1 = 0, s2 = 0;
                    for (int k = 0; k < n; ++k) {
                        if (i >> k & 1) {
                            if (j >> k & 1) s1 += a[k + 1], v2.emplace_back(k + 1);
                            else s2 += a[k + 1], v1.emplace_back(k + 1);
                        }
                    }
                    if (gcd(s1, s2) != 1) {
                        cout << "YES" << endl;
                        cout << v1.size() << ' ' << v2.size() << endl;
                        for (int i : v1) cout << i << ' ';
                        cout << endl;
                        for (int i : v2) cout << i << ' ';
                        cout << endl;
                        f = true;
                        break;
                    }
                }
            }
            if (f) break;
        }
        if (!f) cout << "NO" << endl;
    }
    else {
        if (n > 4) n = 4;
        set<pair<vector<int>, vector<int>>> s;
        for (int i = 1; i < (1 << n); ++i) {
            for (int j = 1; j < i; ++j) {
                if ((i | j) == i) {
                    vector<int> v1, v2;
                    for (int k = 0; k < n; ++k) {
                        if (i >> k & 1) {
                            if (j >> k & 1) v2.emplace_back(k + 1);
                            else v1.emplace_back(k + 1);
                        }
                    }
                    if (v1 > v2) swap(v1, v2);
                    s.insert({v1, v2});
                }
            }
        }
        cout << s.size() << endl;
        int f = 0;
        for (auto [v1, v2] : s) {
            cout << v1.size() << ' ' << v2.size() << endl;
            for (int i : v1) cout << i + f << ' ';
            cout << endl;
            for (int i : v2) cout << i + f << ' ';
            cout << endl;
            f += 4;
        }
    }
    return 0;
}