你在场边观看了比赛，但是你忘记了 $X$ 和 $Y$ ，只记得总共比了 $1 \le n \le 20$ 局，和每局获胜的人，请判断谁获胜了。如果 A 获胜，输出 A ，如果 B 获胜，输出 B ，如果都有可能，输出 ? 。
题目描述
Let’s consider a game in which two players, A and B, participate. This game is characterized by two positive integers, $ X $ and $ Y $ .
The game consists of sets, and each set consists of plays. In each play, exactly one of the players, either A or B, wins. A set ends exactly when one of the players reaches $ X $ wins in the plays of that set. This player is declared the winner of the set. The players play sets until one of them reaches $ Y $ wins in the sets. After that, the game ends, and this player is declared the winner of the entire game.
You have just watched a game but didn’t notice who was declared the winner. You remember that during the game, $ n $ plays were played, and you know which player won each play. However, you do not know the values of $ X $ and $ Y $ . Based on the available information, determine who won the entire game — A or B. If there is not enough information to determine the winner, you should also report it.
输入格式
Each test contains multiple test cases. The first line contains a single integer $ t $ $ (1 \leq t \leq 10^4) $ - the number of test cases. The description of the test cases follows.
The first line of each test case contains an integer $ n $ $ (1 \leq n \leq 20) $ - the number of plays played during the game.
The second line of each test case contains a string $ s $ of length $ n $ , consisting of characters $ \texttt{A} $ and $ \texttt{B} $ . If $ s_i = \texttt{A} $ , it means that player A won the $ i $ -th play. If $ s_i = \texttt{B} $ , it means that player B won the $ i $ -th play.
It is guaranteed that the given sequence of plays corresponds to at least one valid game scenario, for some values of $ X $ and $ Y $ .
输出格式
For each test case, output:
$ \texttt{A} $ — if player A is guaranteed to be the winner of the game.
$ \texttt{B} $ — if player B is guaranteed to be the winner of the game.
$ \texttt{?} $ — if it is impossible to determine the winner of the game.
样例 #1
样例输入 #1
1
7
2
5
3
ABBAA
4
3
5
BBB
6
7
7
BBAAABA
8
20
9
AAAAAAAABBBAABBBBBAB
10
1
11
A
12
13
13
AAAABABBABBAB
14
7
15
BBBAAAA
样例输出 #1
1
A
2
B
3
A
4
B
5
A
6
B
7
A
提示
In the first test case, the game could have been played with parameters $ X = 3 $ , $ Y = 1 $ . The game consisted of $ 1 $ set, in which player A won, as they won the first $ 3 $ plays. In this scenario, player A is the winner. The game could also have been played with parameters $ X = 1 $ , $ Y = 3 $ . It can be shown that there are no such $ X $ and $ Y $ values for which player B would be the winner.
In the second test case, player B won all the plays. It can be easily shown that in this case, player B is guaranteed to be the winner of the game.
In the fourth test case, the game could have been played with parameters $ X = 3 $ , $ Y = 3 $ :
In the first set, $ 3 $ plays were played: AAA. Player A is declared the winner of the set.
In the second set, $ 3 $ plays were played: AAA. Player A is declared the winner of the set.
In the third set, $ 5 $ plays were played: AABBB. Player B is declared the winner of the set.
In the fourth set, $ 5 $ plays were played: AABBB. Player B is declared the winner of the set.
In the fifth set, $ 4 $ plays were played: BBAB. Player B is declared the winner of the set.
In total, player B was the first player to win $ 3 $ sets. They are declared the winner of the game.
There is a ribbon divided into $ n $ cells, numbered from $ 1 $ to $ n $ from left to right. Initially, an integer $ 0 $ is written in each cell.
Monocarp plays a game with a chip. The game consists of several turns. During the first turn, Monocarp places the chip in the $ 1 $ -st cell of the ribbon. During each turn except for the first turn, Monocarp does exactly one of the two following actions:
move the chip to the next cell (i. e. if the chip is in the cell $ i $ , it is moved to the cell $ i+1 $ ). This action is impossible if the chip is in the last cell;
choose any cell $ x $ and teleport the chip into that cell. It is possible to choose the cell where the chip is currently located.
At the end of each turn, the integer written in the cell with the chip is increased by $ 1 $ .
Monocarp’s goal is to make some turns so that the $ 1 $ -st cell contains the integer $ c_1 $ , the $ 2 $ -nd cell contains the integer $ c_2 $ , …, the $ n $ -th cell contains the integer $ c_n $ . He wants to teleport the chip as few times as possible.
Help Monocarp calculate the minimum number of times he has to teleport the chip.
输入格式
The first line contains one integer $ t $ ( $ 1 \le t \le 10^4 $ ) — the number of test cases.
Each test case consists of two lines:
the first line contains one integer $ n $ ( $ 1 \le n \le 2 \cdot 10^5 $ );
the second line contains $ n $ integers $ c_1, c_2, \dots, c_n $ ( $ 0 \le c_i \le 10^9 $ ; $ c_1 \ge 1 $ ).
It can be shown that under these constraints, it is always possible to make a finite amount of turns so that the integers in the cells match the sequence $ c_1, c_2, \dots, c_n $ .
Additional constraint on the input: the sum of values of $ n $ over all test cases does not exceed $ 2 \cdot 10^5 $ .
输出格式
For each test case, print one integer — the minimum number of times Monocarp has to teleport the chip.
样例 #1
样例输入 #1
1
4
2
4
3
1 2 2 1
4
5
5
1 0 1 0 1
6
5
7
5 4 3 2 1
8
1
9
12
样例输出 #1
1
1
2
2
3
4
4
11
提示
In the first test case of the example, Monocarp can perform the turns as follows:
place the chip in the $ 1 $ -st cell; the numbers in the cells are $ [1, 0, 0, 0] $ ;
move the chip to the next ( $ 2 $ -nd) cell; the numbers in the cells are $ [1, 1, 0, 0] $ ;
move the chip to the next ( $ 3 $ -rd) cell; the numbers in the cells are $ [1, 1, 1, 0] $ ;
teleport the chip to the $ 2 $ -nd cell; the numbers in the cells are $ [1, 2, 1, 0] $ ;
move the chip to the next ( $ 3 $ -rd) cell; the numbers in the cells are $ [1, 2, 2, 0] $ ;
move the chip to the next ( $ 4 $ -th) cell; the numbers in the cells are $ [1, 2, 2, 1] $ .
Monocarp has found a treasure map. The map represents the treasure location as an OX axis. Monocarp is at $ 0 $ , the treasure chest is at $ x $ , the key to the chest is at $ y $ .
Obviously, Monocarp wants to open the chest. He can perform the following actions:
go $ 1 $ to the left or $ 1 $ to the right (spending $ 1 $ second);
pick the key or the chest up if he is in the same point as that object (spending $ 0 $ seconds);
put the chest down in his current point (spending $ 0 $ seconds);
open the chest if he’s in the same point as the chest and has picked the key up (spending $ 0 $ seconds).
Monocarp can carry the chest, but the chest is pretty heavy. He knows that he can carry it for at most $ k $ seconds in total (putting it down and picking it back up doesn’t reset his stamina).
What’s the smallest time required for Monocarp to open the chest?
输入格式
The first line contains a single integer $ t $ ( $ 1 \le t \le 100 $ ) — the number of testcases.
The only line of each testcase contains three integers $ x, y $ and $ k $ ( $ 1 \le x, y \le 100 $ ; $ x \neq y $ ; $ 0 \le k \le 100 $ ) — the initial point of the chest, the point where the key is located, and the maximum time Monocarp can carry the chest for.
输出格式
For each testcase, print a single integer — the smallest time required for Monocarp to open the chest.
样例 #1
样例输入 #1
1
3
2
5 7 2
3
10 5 0
4
5 8 2
样例输出 #1
1
7
2
10
3
9
提示
In the first testcase, Monocarp can open the chest in $ 7 $ seconds with the following sequence of moves:
go $ 5 $ times to the right ( $ 5 $ seconds);
pick up the chest ( $ 0 $ seconds);
go $ 2 $ times to the right ( $ 2 $ seconds);
pick up the key ( $ 0 $ seconds);
put the chest down ( $ 0 $ seconds);
open the chest ( $ 0 $ seconds).
He only carries the chest for $ 2 $ seconds, which he has the stamina for.
In the second testcase, Monocarp can pick up the key on his way to the chest.
In the third testcase, Monocarp can’t use the strategy from the first testcase because he would have to carry the chest for $ 3 $ seconds, while he only has the stamina for $ 2 $ seconds. Thus, he carries the chest to $ 7 $ , puts it down, moves $ 1 $ to the right to pick up the key and returns $ 1 $ left to open the chest.
You are given a sequence of integers $ a $ of length $ 2n $ . You have to split these $ 2n $ integers into $ n $ pairs; each pair will represent the coordinates of a point on a plane. Each number from the sequence $ a $ should become the $ x $ or $ y $ coordinate of exactly one point. Note that some points can be equal.
After the points are formed, you have to choose a path $ s $ that starts from one of these points, ends at one of these points, and visits all $ n $ points at least once.
The length of path $ s $ is the sum of distances between all adjacent points on the path. In this problem, the distance between two points $ (x_1, y_1) $ and $ (x_2, y_2) $ is defined as $ |x_1-x_2| + |y_1-y_2| $ .
Your task is to form $ n $ points and choose a path $ s $ in such a way that the length of path $ s $ is minimized.
输入格式
The first line contains a single integer $ t $ ( $ 1 \le t \le 100 $ ) — the number of testcases.
The first line of each testcase contains a single integer $ n $ ( $ 2 \le n \le 100 $ ) — the number of points to be formed.
The next line contains $ 2n $ integers $ a1, a_2, \dots, a{2n} $ ( $ 0 \le a_i \le 1,000 $ ) — the description of the sequence $ a $ .
输出格式
For each testcase, print the minimum possible length of path $ s $ in the first line.
In the $ i $ -th of the following $ n $ lines, print two integers $ x_i $ and $ y_i $ — the coordinates of the point that needs to be visited at the $ i $ -th position.
If there are multiple answers, print any of them.
样例 #1
样例输入 #1
1
2
2
2
3
15 1 10 5
4
3
5
10 30 20 20 30 10
样例输出 #1
1
9
2
10 1
3
15 5
4
20
5
20 20
6
10 30
7
10 30
提示
In the first testcase, for instance, you can form points $ (10, 1) $ and $ (15, 5) $ and start the path $ s $ from the first point and end it at the second point. Then the length of the path will be $ |10 - 15| + |1 - 5| = 5 + 4 = 9 $ .
In the second testcase, you can form points $ (20, 20) $ , $ (10, 30) $ , and $ (10, 30) $ , and visit them in that exact order. Then the length of the path will be $ |20 - 10| + |20 - 30| + |10 - 10| + |30 - 30| = 10 + 10 + 0 + 0 = 20 $ .
分析
构造题，根据题意可以推断，ans 只分别与 x 集合的差值和、y 集合差值和有关。显然，（大数-小数）+（大数-小数）的结果劣于（大数-大数）+（小数-小数）。
故此题，在进行排列后按序先分配 x 再分配 y，直接统计 x 有序集合与 y 有序集合的差值即可（注意结果除去 x，y 交界的一对差）。
参考代码
1
#include<bits/stdc++.h>
2
usingnamespacestd;
3
typedeflonglong ll;
4
constint maxn =120;
5
int a[maxn];
6
intmain(){
7
int t;cin >> t;
8
while(t--){
9
int n;cin >> n;
10
for(int i =1;i <=2* n;i++)
11
cin >> a[i];
12
sort(a +1, a +2* n +1);
13
int ans =0;
14
for(int i =2;i <=2* n;i++){
15
ans += a[i]- a[i -1];
16
}
17
ans -= a[n +1]- a[n];
18
cout << ans << endl;
19
for(int i =1;i <= n;i++)
20
cout << a[i]<<" "<< a[2* n +1- i]<< endl;
21
}
22
23
return0;
24
}
K 速战速决
[THUPC 2023 初赛] 速战速决
题目描述
小 I 与小 J 正在玩一个叫做“开火车”，又称作“拖板车”和“小猫钓鱼”的扑克游戏。游戏规则如下，注意其与一般玩法可能有不同：
You are given an array $ a_1, a_2, \ldots, a_n $ . You need to find an array $ b_1, b_2, \ldots, b_n $ consisting of numbers $ 1 $ , $ 2 $ , $ 3 $ such that exactly two out of the following three conditions are satisfied:
There exist indices $ 1 \leq i, j \leq n $ such that $ a_i = a_j $ , $ b_i = 1 $ , $ b_j = 2 $ .
There exist indices $ 1 \leq i, j \leq n $ such that $ a_i = a_j $ , $ b_i = 1 $ , $ b_j = 3 $ .
There exist indices $ 1 \leq i, j \leq n $ such that $ a_i = a_j $ , $ b_i = 2 $ , $ b_j = 3 $ .
If such an array does not exist, you should report it.
输入格式
Each test contains multiple test cases. The first line contains a single integer $ t $ $ (1 \leq t \leq 500) $ — the number of test cases. Each test case is described as follows.
The first line of each test case contains an integer $ n $ $ (1 \leq n \leq 100) $ — the length of the array $ a $ .
The second line of each test case contains $ n $ integers $ a_1, a_2, \ldots, a_n $ $ (1 \leq a_i \leq 100) $ — the elements of the array $ a $ .
输出格式
For each test case, print -1 if there is no solution. Otherwise, print $ b_1, b_2, \ldots, b_n $ — an array consisting of numbers $ 1 $ , $ 2 $ , $ 3 $ that satisfies exactly two out of three conditions. If there are multiple possible answers, you can print any of them.
In the first test case, $ b = [1, 2, 3, 1, 1, 1] $ satisfies condition $ 1 $ because for $ i = 4 $ , $ j = 2 $ : $ a_i = a_j $ , $ b_i = 1 $ , and $ b_j = 2 $ . It also satisfies condition $ 2 $ because for $ i = 6 $ , $ j = 3 $ : $ a_i = a_j $ , $ b_i = 1 $ , and $ b_j = 3 $ . However, it does not satisfy condition $ 3 $ . In total, exactly two out of three conditions are satisfied.
分析
构造题，根据分析，只有当数量超过 2 个的数的种数大于等于 2，才有可能构造出符合要求的 b 数组。
Comments
Quiet notes for this article.