Good Bye 2023

Good Bye 2023

Good Bye 2023

A. 2023

题意：序列a中所有数的乘积应为2023，现在给出序列中的n个数，找到剩下的k个数并输出，报告不可能。

思路：把所有已知的数字乘起来，判断是否整除2023，不够的k补1，注意当前乘积已经大于2023的情况。

AC code：

void solve() {
    cin >> n >> k;
    int now = 1;
    for(int i = 0; i < n; i ++) {
    int x; cin >> x;
    a[i] = x;
    now *= x;
    }
    if(2023 % now || now > 2023) {
        cout << "NO" << endl;
        return;
    }
    cout << "YES" << endl;
    k -= 1;
    while(k --) cout << 1 << " ";
    cout << 2023 / now << endl;
        
    //cout << "Good Bye 2023" << endl;
}

B. Two Divisors

题意：给出正整数的两个最大的除数a和b，求x。

思路：首先是找出a和b的最小公倍数lcm，然后判断lcm是否为较大的除数：

如果是，说明a是b的除数，且a和b还是x最大的两个除数，当前的最小公倍数是b，b/a为当前b最大能放大的倍数，则x=b*(b / a)；

否则，x=lcm。

AC code：

int gcd (int a, int b) {
    if(b) while((a%=b) && (b%=a)); return a + b;
}
 
void solve() {
    int a, b; cin >> a >> b;
    int lcm = a * b / gcd(a, b);
    if (lcm != b) {
        cout << lcm << endl;
        return;
    }
    cout << b * b / a << endl;
}

C. Training Before the Olympiad

题意：

在一个长度为n的正整数数组中，A和B轮流操作：

• 每次选择两个不同的索引i和j，然后在数组中删除$a_i$和$a_j$，在数组中加入[($a_i$+$a_j$)/2] *2，A先起手，直到数组元素为1游戏结束；

• A目标是最大化最终数字，B目标是最小化最终数字；

• 现在针对数组a的每个前缀数字进行操作，每个前缀的最终数字是多少。

思路：

看奇偶：

• 每次操作选择的两元素奇偶性相同则操作不会影响最终结果，否则会对最终结果-1；
• 奇数才是影响最终结果的关键，AB无论怎么选择，一次操作后的数字必定是偶数；
• 对A来说是尽可能选择奇偶性相同的元素，对B则是选择奇偶性不同的元素来缩小最终结果：
• A优先选择成对的奇数来减少奇数的数量，一次减少2个奇数，选择一个奇数一次减少1个奇数：
  • 首先前缀和奇数的数量；
  • 各一轮下来最多消灭三个奇数，一次结果-1，再看多出的奇数若为1结果额外-1。

AC code：

void solve() {
    cin >> n;
    vector<int> cnt(n + 1, 0);
    vector<int> sum(n + 1, 0);
    for (int i = 1; i <= n; i ++) {
        cin >> a[i];
        sum[i] = sum[i - 1] + a[i];
        cnt[i] = cnt[i - 1] + (a[i] % 2 != 0);
    }
    for(int i = 2; i <= n; i ++) {
        if(cnt[i] == 1){
            sum[i] -= 1;
            continue;
        }
        sum[i] -= (cnt[i] / 3) + (cnt[i] % 3 == 1);
    }
 
    for(int i = 1; i <= n; i ++) 
        cout << sum[i] << " ";
    cout << endl;
}

D. Mathematical Problem

题意：找出n个n位数(n为奇数)，每个数满足各数位的组成的集合相同，且每个数都是一个平方数；

思路：

map打表找规律，会发现神奇的事情：

n = 3
169
196
961
n = 5
10609
16900
19600
61009
90601
96100
n = 7
1006009
1060900
1690000
1960000
6100900
9006001
9060100
9610000
n = 9
100060009
100600900
106090000
169000000
196000000
610090000
900060001
900600100
906010000
961000000
......

然后就是字符串的操作了…

AC code：

void solve() {
    string cnt = "00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000";
    cin >> n;
    if (n == 1) {
        cout << 1 << endl;
        return;
    }
    cout << "196" << cnt.substr(0, max((LL)0, n - 3)) << endl;
    for (int i = 0; i < n / 2; i ++) {
        cout << '1' << cnt.substr(0, i) << '6' << cnt.substr(0, i) << '9' << cnt.substr(0, max((LL)0, n - 3 - 2 * i)) << endl;
        cout << '9' << cnt.substr(0, i) << '6' << cnt.substr(0, i) << '1' << cnt.substr(0, max((LL)0, n - 3 - 2 * i)) << endl;
    }
}