Codeforces Round 963 (Div. 2)
锐评
只做出来两道题，感觉相当差劲，第三题思路很明切没想到合适的实现方法
A. Question Marks
题意
蒂姆正在做一个由 4n 个问题组成的测试；每个问题有 4 个选项：A"、"B"、"C "和 "D"。每个选项都有 n 个正确答案，也就是说有 n 道题的答案是 "A"， n 道题的答案是 "B"， n 道题的答案是 "C"， n 道题的答案是 "D"。
对于每道题，蒂姆都会把答案写在答题纸上。如果想不出答案，他会在该题上留下问号"？
他的答题纸有 4n 个字符。蒂姆最多能答对多少题？
输入描述
第一行包含一个整数 t ( 1 \le t \le 1000 ) - 测试用例数。
每个测试用例的第一行包含一个整数 n ( 1 \le n \le 100 )。
每个测试用例的第二行包含一个由 4n 个字符（ s_i \in \{\texttt{A}, \texttt{B}, \texttt{C}, \texttt{D}, \texttt{?}\} ）组成的字符串 s - 蒂姆对问题的回答。
输出描述
为每个测试用例打印一个整数--Tim 能达到的最高分。
样例输入
6
1
ABCD
2
AAAAAAAA
2
AAAABBBB
2
????????
3
ABCABCABCABC
5
ACADC??ACAC?DCAABC?C
样例输出
4
2
4
0
9
13
样例说明
在第一个测试案例中，只有一个问题的答案是 "A"、"B"、"C "和 "D"，因此蒂姆有可能答对所有答案。
在第二个测试案例中，只有两个正确答案 "A"，这使得他无论如何都能得到 2 分。
在第三个测试案例中，蒂姆最多可以得到 2 个正确答案（选项 A）和 2 个正确答案（选项 B）。例如，如果答案是 "AACCBBDD"，他将得到 4 分。
在第四个测试案例中，他拒绝回答任何问题，因此得到了 0 分。
思路
每个选项最多答对的题目数量是min((A,B,C,D),n)，记录ABCD的数量和n取最小值，结果累加即可。
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 1e6 + 9;
const int MOD = 998244353;
int n, m;
void solve() {
cin >> n ;
map<int,int>mp;
string s; cin >> s;
for (int i = 0; i < 4 * n; ++ i) {
mp[s[i]] ++;
}
int ans = min(n, mp['A']) + min(n, mp['B']) + min(n, mp['C']) + min(n, mp['D']);
cout << ans << "\n";
}
signed main() {
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int _ = 1;
cin >> _;
while (_--) {
solve();
}
return 0;
}
B. Parity and Sum
题意
好的，让我们重新整理一下问题描述，使用 $ 作为 LaTeX 符号的包裹符：
给定一个由 n 个正整数组成的数组 a 。
在一次操作中，你可以选取任意一对索引 (i, j) ，使得 a_i 和 a_j 具有不同的奇偶性，然后用它们的和替换较小的那个。更正式的说法是
- 如果 a_i < a_j ，则用 a_i + a_j 替换 a_i ；
- 否则，用 a_i + a_j 替换 a_j 。
求使数组中所有元素具有相同奇偶性所需的最少操作数。
输入描述
第一行包含一个整数 t ( 1 \le t \le 10^4 ) - 测试用例数。
每个测试用例的第一行包含一个整数 n ( 1 \le n \le 2 \cdot 10^5 ).
第二行包含 n 个整数 a_1, a_2, \ldots, a_n ( 1 \le a_i \le 10^9 ) - 数组 a 的元素。
保证所有测试用例中 n 的总和不超过 2 \cdot 10^5 。
输出描述
对于每个测试用例，输出一个整数 - 所需的最少操作数。
样例输入
7
5
1 3 5 7 9
4
4 4 4 4
3
2 3 4
4
3 2 2 8
6
4 3 6 1 2 1
6
3 6 1 2 1 2
5
999999996 999999997 999999998 999999999 1000000000
样例输出
0
0
2
4
3
3
3
样例说明
在第一个测试案例中，所有整数的奇偶校验已经相同。因此，无需进行任何操作。
在第三个测试用例中，我们可以执行 (1, 2) 和 (1, 3) 两种操作。数组 a 的变换如下： a = [\color{red}2, \color{red}3, 4] \longrightarrow [\color{red}5, 3, \color{red}4] \longrightarrow [5, 3, 9] .
在第四个测试用例中，最佳操作序列是 (1, 2) ， (1, 3) ， (1, 4) 和 (1, 4) 。数组 a 的变换如下： a = [\color{red}3, \color{red}2, 2, 8] \longrightarrow [\color{red}3, 5, \color{red}2, 8] \longrightarrow [\color{red}3, 5, 5, \color{red}8] \longrightarrow [\color{red}{11}, 5, 5, \color{red}8] \longrightarrow [11, 5, 5, 19] .
思路
- 只能选择奇偶性不同的两个数操作，操作后小的数必定为奇数，所以我们只能把偶数变成奇数，只要有一个数是奇数，他最后就必须全部变成奇数。
- 如果最大的数是奇数，那么一个偶数只需要进行一次操作，和最大的奇数进行操作，不需要额外的操作，此时操作数就是偶数的个数。
- 如果最大数是偶数我们就要考虑一些情况，我们要求出来目前最大的奇数，然后用它来每次和偶数组队进行操作，每次操作后最大的基数都会发生变化，就是会加上偶数的数值，直到我们目前的奇数小于当前的偶数的时候，我们需要额外进行一次操作，用当前最大的奇数和最大的偶数进行操作，这样奇数的数值会加上最大的偶数，剩下的所有偶数就都可以变成奇数。
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e6 + 9;
const int MOD = 998244353;
int n, a[N];
void solve() {
cin >> n;
int ji = 0, ou = 0;
int mx = 0;//最大的数
int m = 0;//最大奇数
for (int i = 1; i <= n; ++ i) {
cin >> a[i];
mx = max(mx, a[i]);
if (a[i] % 2 == 0) ou ++;
else {
ji ++;
m = max(m, a[i]);
}
}
if (ji == 0 || ou == 0) {
cout << "0\n";
return;
}
//一定有奇数
int ans = 0;
sort(a + 1, a + 1 + n);
if (mx % 2 == 1) {
ans = ou;//其他偶数都和最大的组合即可
}else {
//所有偶数和最大的奇数之和与最大的偶数对比
for (int i = 1; i <= n; ++ i) {
//奇数不管
if (a[i] % 2 == 1) continue;
//如果当前最大奇数大于当前的偶数
if (m > a[i]) {
//更新最大奇数
m += a[i];
ans ++;
}else {
//和最大的数（偶数）组合，更新
m += mx;
ans ++;
m += a[i];
ans ++;
}
}
}
cout << ans << "\n";
}
signed main() {
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int _ = 1;
cin >> _;
while (_--) {
solve();
}
return 0;
}
C. Light Switches
题意
有一个由 n 个房间组成的公寓，每个房间的灯**最初都是关着的。
为了控制这些房间的灯光，公寓的主人决定在房间里安装芯片，这样每个房间正好有一个芯片，芯片安装在不同的时间。具体来说，这些时间由数组 a_1, a_2, \ldots, a_n 表示，其中 a_i 是在 i (第三个房间)安装芯片的时间(以分钟为单位)。
芯片一经安装，就会每隔 k 分钟改变房间的灯光状态--在 k 分钟内开灯，然后在接下来的 k 分钟内关灯，再在接下来的 k 分钟内开灯，以此类推。换句话说，芯片在 a_i 、 a_i + k 、 a_i + 2k 、 a_i + 3k 、 \ldots 分钟时改变 i /房间的灯光状态。
公寓里所有房间最早亮灯的时刻是什么时候？
输入描述
第一行包含一个整数 t ( 1 \le t \le 10^4 ) - 测试用例数。
每个测试用例的第一行包含两个整数 n 和 k ( 1 \le k \le n \le 2 \cdot 10^5 ) - 公寓房间数和芯片周期。
第二行包含 n 个不同的整数 a_1, a_2, \ldots, a_n ( 1 \le a_i \le 10^9 ) -- 安装芯片的时刻。
保证所有测试案例的 n 之和不超过 2 \cdot 10^5 。
输出描述
对于每个测试用例，打印一个整数--问题的答案(以分钟为单位)。如果不存在所有房间都开灯的时刻，则打印 -1
样例输入
9
4 4
2 3 4 5
4 3
2 3 4 5
4 3
3 4 8 9
3 3
6 2 1
1 1
1
7 5
14 34 6 25 46 7 17
6 5
40 80 99 60 90 50
6 5
64 40 50 68 70 10
2 1
1 1000000000
样例输出
5
-1
10
8
1
47
100
-1
-1
样例说明
在第一个测试案例中，所有灯都将在 5 分钟前亮起，而芯片不会关闭任何一盏灯。答案是 5 。
在第二个测试案例中，由于 k=3 ， 1 /st 灯将在 2, 3, 4, 8, 9, 10, 14, \ldots 分钟时亮起；同时， 4 /th 灯将在 5, 6, 7, 11, 12, 13, 17, \ldots 分钟时亮起。这两个序列没有共同的数字，所以它们永远不会同时亮起。
在第三个测试案例中，可以看到 1 -st和 2 -nd灯会在 6 和 7 分钟时关闭，但芯片会在 9 和 10 分钟时重新打开。 3 -rd和 4 -th灯也会在 10 分钟时亮起，所以答案是 10 。
思路
每一个灯的周期都是K，我们需要找最晚开灯的那盏灯前后找最其他灯最近的开灯时间，然后我们将开灯时间进行排序，只要在这个区间内最晚开灯的时间和最早开灯的时间不超过K那么就一定是存在的，而最早同时开灯的时间就是我们排序后，在那个区间内，最晚开灯的时间。
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 1e6 + 9;
const int MOD = 998244353;
int n, k, a[N], b[N];
void solve() {
cin >> n >> k;
for (int i = 1; i <= n; ++ i)
{
cin >> a[i];
}
sort(a + 1, a + 1 + n);
for (int i = 1; i <= n; ++ i)
{
if (a[n] - a[i] >= k)
{
int t = (a[n] - a[i]) % (2 * k);
//同频或存在开灯周期相同的时候
if (t == 0 || t < k)
{
a[i] = a[i] + (a[n] - a[i]) / (2 * k) * (2 * k);
//放到一个周期里
}
else
{
a[i] = a[i] + (a[n] - a[i]) / (2 * k) * (2 * k) + 2 * k;
//放到下一个周期，这样里最大值开灯时更近
}
}
}
sort(a + 1, a + 1 + n);
cout << (a[n] - a[1] >= k ? -1 : a[n]) << "\n";
}
signed main() {
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int _ = 1;
cin >> _;
while (_--) {
solve();
}
return 0;
}
