Codeforces Good Bye 2023 题解 | JorbanS

A - 2023

void solve() {
    cin >> n >> k;
    ll res = 1;
    while (n --) {
        int x; cin >> x;
        res *= x;
    }
    if (2023 % res) {
        cout << no << endl;
        return;
    }
    cout << yes << endl;
    cout << 2023 / res << ' ';
    k --;
    while (k --) cout << 1 << ' ';
    cout << endl;
}

B - Two Divisors

题解 先尝试让 $lcm(a,b)$ 作为 $x$。若 $x=lcm(a,b)$，此时 $b=a\times p$，$p$ 为 $x$ 的最小素因子，因此 $x=b\times p=b\times \frac{b}{a}$

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

int solve() {
    int a, b; cin >> a >> b;
    if (a > b) swap(a, b);
    int d = gcd(a, b);
    int res = a / gcd(a, b) * b;
    return res == b ? res / a * b : res;
}

C - Training Before the Olympiad

题意 $A$ 先取要使得最后剩下的数最大，$B$ 后取要使得数最小

题解 $B$ 每次优先取一奇一偶

若 $A$ 优先取两偶，进行操作后加上去的永远是偶数，因此每一轮多两个偶数，偶数的数量永远不能穷尽，则 $B$ 的取法不受 $A$ 的限制，故不是最优的

故 $A$ 优先取奇数，每轮少三个奇数多两个偶数，奇数能够穷尽，故看最后有几个奇数

• 若还剩 $0$ 个，不需要考虑
• 若还剩 $1$ 个，则一定会取一奇一偶
• 若还剩 $2$ 个，则 $A$ 取两个奇数使得奇数清零

int n, a[N], odd[N], even[N];

void solve() {
    cin >> n;
    for (int i = 1; i <= n; i ++) cin >> a[i];
    for (int i = 1; i <= n; i ++) odd[i] = even[i] = 0;
    for (int i = 1; i <= n; i ++) {
        odd[i] = odd[i - 1];
        even[i] = even[i - 1];
        if (a[i] & 1) odd[i] ++;
        else even[i] ++;
    }
    ll sum = a[1];
    cout << a[1] << ' ';
    for (int i = 2; i <= n; i ++) {
        sum += a[i];
        int res = odd[i] / 3;
        odd[i] %= 3;
        res += odd[i] & 1;
        cout << sum - res << ' ';
    }
    cout << endl;
}

D - Mathematical Problem

题解 打表找规律

打表 $code$

#define int long long

void solve() {
    auto digit = [](int x) {
        vector<int> a;
        set<int> s;
        while (x) {
            int t = x % 10;
            if (!s.count(t)) a.push_back(t), s.insert(t);
            x /= 10;
        }
        sort(a.begin(), a.end());
        return a;
    };
    int n; cin >> n;
    map<vector<int>, vector<int>> mp;
    for (int i = sqrt(pow(10, n - 1)); i <= sqrt(pow(10, n)); i ++)
        if (to_string(i * i).size() == n)
            mp[digit(i * i)].push_back(i * i);
    for (auto [x, c] : mp)
        if (c.size() >= n) {
            for (auto i : c)
                cout << i << endl;
            cout << endl;
        }
}

题目 $code$

int n;
int a[2][3] = {
    {1, 6, 9},
    {9, 6, 1},
};

#define loop(x) for (int _ = 0; _ < x; _ ++) cout << 0;

void solve() {
    cin >> n;
    if (n == 1) {
        cout << 1 << endl;
        return;
    }
    cout << 196;
    loop(n - 3);
    cout << endl;
    int cnt = 1;
    for (int j = 0; j <= (n - 1) / 2 - 1; j ++) {
        for (int i = 0; i < 2; i ++) {
            if (cnt == n) return;
            cout << a[i][0];
            loop(j);
            cout << a[i][1];
            loop(j);
            cout << a[i][2];
            loop(n - j * 2 - 3);
            cout << endl;
            cnt ++;
        }
    }
}