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;}
}