仓库源文，站点原文

title: Good Bye 2023 date: 2024-03-03 16:09:35 updated: 2024-03-03 16:09:35 categories:

• ACM&算法 tag:
• ACM
• Codeforces math: true description: Good Bye 2023 个人写题记录

A. 2023

大致题意

已知一个数组，其每个值的乘积之和恰好是 2023，但是删除掉了 $k$ 个值后，得到数组 $b$，在已知 $b$ 的情况下反推原数组

思路

反过来除一下即可

AC code

void solve() {
    int _;
    cin >> _;
    for (int tc = 0; tc < _; ++tc) {
        int n, k;
        cin >> n >> k;
        int sum = 1;
        bool flag = true;
        for (int i = 0; i < n; ++i) {
            int tmp;
            cin >> tmp;
            sum *= tmp;
            if (sum > 2023) {
                flag = false;
                sum = 0;
            }
        }
        if (flag && 2023 % sum == 0) {
            cout << "YES\n" << 2023 / sum;
            for (int i = 1; i < k; ++i) cout << ' ' << 1;
            cout << endl;
        } else cout << "NO" << endl;
    }
}

B. Two Divisors

大致题意

有一个值 $x$，已知它的两个最大的因子，问 $x$

思路

若 $gcd(a, b) == a$ 则为 $b b / a$ 否则为 $a b / gcd(a, b)$

AC code

#define int unsigned long long

void solve() {
    int _;
    cin >> _;
    for (int tc = 0; tc < _; ++tc) {
        int a, b;
        cin >> a >> b;
        if (const int c = __gcd(a, b); c != a) cout << a * b / c << endl;
        else cout << b / c * b << endl;
    }
}

C. Training Before the Olympiad

大致题意

有两个人玩游戏，每次可以选择一个数组中的两个值，移除它们两个并添加一个 $\left \lfloor \frac{a_i + a_j}{2} \right \rfloor \times 2$

第一个操作的人希望让最后剩下的那个值最大，第二个操作的人希望最小，问依次操作的情况下，最终结果是多少

思路

因为每次操作结束多出来的一定是偶数，所以要尽可能变成偶数

所以第一个人一定是尽力把两个奇数先合并了，第二个人一定是尽力选一个奇数一个偶数

AC code

#define int long long

void solve() {
    int _;
    cin >> _;
    for (int tc = 0; tc < _; ++tc) {
        int n;
        cin >> n;
        vector<int> data(n);
        for (auto& i: data) cin >> i;
        int cnt = 0, tot = 0;
        for (int i = 0; i < n; ++i) {
            cnt += data[i] % 2;
            tot += data[i];
            if (i == 0) cout << tot << ' ';
            else cout << tot - (cnt / 3 + (cnt % 3 == 1)) << ' ';
        }
        cout << endl;
    }
}

D. Mathematical Problem

大致题意

给出一个 $n$，希望找到 $n$ 个 $n$ 位的数值，它们都是某个值的幂次，且这 $n$ 个值都可以相互通过交换数值位置变换得到

给出一组解

思路

因为当 $n = 11$ 的时候，能够凑成的数量已经超过 99 个，所以剩下的情况下只要在上面的情况下后面加 0 即可

AC code

#define int long long

void solve() {
    vector<vector<int>> data(12);
    data[1] = {9};
    data[3] = {169, 196, 961};
    data[5] = {16384, 31684, 36481, 38416, 43681};
    data[7] = {1493284, 3214849, 3912484, 4239481, 4293184, 4932841, 9132484};
    data[9] = {236759769, 297769536, 369677529, 526977936, 677925369, 769729536, 773562969, 796763529, 927567936, 956293776, 993762576};
    data[11] = {
        10948273956, 12395704896, 12899053476, 13056947289, 13769849025, 14909875236, 15072963984, 15890367249, 16385792049, 16795382409, 17250983649, 17592308496, 17805432969, 17869540329,
        18096437529, 18543902976, 19036548729, 19936875204, 23897140569, 24091385796, 24196735809, 24371580996, 27939456801, 28347109956, 29137465809, 29163075984, 30524981796, 30896147529,
        30965792841, 31489567209, 31528974096, 31829057649, 31899746025, 31957640289, 34507892169, 34860997521, 37869549201, 37918604529, 38495617209, 39276501489, 39564790281, 39784690521,
        40217895936, 42513078969, 42750938169, 43596187209, 43608715929, 45192807396, 47031295689, 48913072569, 48963510729, 49218753609, 49327965801, 49918730625, 49956273081, 50329781649,
        50473912896, 50824997136, 51436879209, 52349897601, 54197236809, 58396172409, 58730129649, 59380429761, 59438927601, 59632174809, 62391547089, 63975102489, 65378910249, 68135094729,
        69713425089, 70152938496, 71489390625, 71985963204, 72153480996, 72195390864, 72953469801, 74902931856, 75318960249, 76921358409, 78031952964, 79495238601, 79542613089, 79910243856,
        80319527649, 80356941729, 84701953296, 84703699521, 84992073156, 85970931264, 86293175049, 86939471025, 87965034921, 90127845369, 90163874529, 90248571396, 90372985641, 91302478569,
        91534687209, 91625473809, 91987250436, 92305984761, 92504789316, 94829507136, 94971830625, 95971083264, 96438197025, 98015329476, 99270365184, 99764381025, 99853472016
    };
    int _;
    cin >> _;
    for (int tc = 0; tc < _; ++tc) {
        int n;
        cin >> n;
        if (n <= 11) for (int i = 0; i < n; ++i) cout << data[n][i] << endl;
        else for (int i = 0; i < n; ++i) {
            cout << data[11][i];
            for (int j = 11; j < n; ++j) cout << '0';
            cout << endl;
        }
    }
}