A,B 两人玩游戏，游戏规则如下：
整场游戏有多轮，每轮游戏先胜 X 局的人获胜，每场游戏先胜 Y 局的人获胜。
你在场边观看了比赛，但是你忘记了 X 和 Y ，只记得总共比了 1≤n≤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≤t≤104) - the number of test cases. The description of the test cases follows.
The first line of each test case contains an integer n(1≤n≤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 A and B . If si=A , it means that player A won the i -th play. If si=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:
A — if player A is guaranteed to be the winner of the game.
B — if player B is guaranteed to be the winner of the game.
? — if it is impossible to determine the winner of the game.
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.
分析
根据题意，其实每次都是赛到出现结果了才结束，所以每次的最后一局的胜负其实就是整场游戏的胜负。
参考代码
#include<bits/stdc++.h>using namespace std;typedef long long ll;const int maxn = 3e4 + 20;int p[maxn];int n;string s;void solve() { cin >> n >> s; cout << s.back() << endl;}int main() { int t;cin >> t; while(t--) solve(); return 0;}
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 c1 , the 2 -nd cell contains the integer c2 , …, the n -th cell contains the integer cn . 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≤t≤104 ) — the number of test cases.
Each test case consists of two lines:
the first line contains one integer n ( 1≤n≤2⋅105 );
the second line contains n integers c1,c2,…,cn ( 0≤ci≤109 ; c1≥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 c1,c2,…,cn .
Additional constraint on the input: the sum of values of n over all test cases does not exceed 2⋅105 .
输出格式
For each test case, print one integer — the minimum number of times Monocarp has to teleport the chip.
样例 #1
样例输入 #1
441 2 2 151 0 1 0 155 4 3 2 1112
样例输出 #1
12411
提示
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≤t≤100 ) — the number of testcases.
The only line of each testcase contains three integers x,y and k ( 1≤x,y≤100 ; x=y ; 0≤k≤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
35 7 210 5 05 8 2
样例输出 #1
7109
提示
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.
#include<bits/stdc++.h>using namespace std;typedef long long ll;const int maxn = 120;int main() { int t;cin >> t; while (t--) { int x, y, k;cin >> x >> y >> k; int ans; if (y <= x)ans = x; else { if (y <= x + k)ans = y; else { x += k; ans = y + (y - x); } } cout << ans << endl; } return 0;}
作为系列的忠实玩家，你想知道有多少人参加了关服前的投票，但是运营只公开了最终的投票结果：对于一项包含 N 个选项的投票，选择第 i 个选项的玩家比例为 Pi（1≤i≤N）。运营在公布结果时进行了四舍五入，所有的 Pi 仅保留到小数点后第 L 位。假设实际有 K 位玩家参加了投票，其中有 Di 位玩家选择了第 i 个选项，则应该有
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 (x1,y1) and (x2,y2) is defined as ∣x1−x2∣+∣y1−y2∣ .
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≤t≤100 ) — the number of testcases.
The first line of each testcase contains a single integer n ( 2≤n≤100 ) — the number of points to be formed.
The next line contains 2n integers a∗1,a2,…,a∗2n ( 0≤ai≤1000 ) — 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 xi and yi — 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
2215 1 10 5310 30 20 20 30 10
样例输出 #1
910 115 52020 2010 3010 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 交界的一对差）。
参考代码
#include<bits/stdc++.h>using namespace std;typedef long long ll;const int maxn = 120;int a[maxn];int main() { int t;cin >> t; while (t--) { int n;cin >> n; for (int i = 1;i <= 2 * n;i++) cin >> a[i]; sort(a + 1, a + 2 * n + 1); int ans = 0; for (int i = 2;i <= 2 * n;i++) { ans += a[i] - a[i - 1]; } ans -= a[n + 1] - a[n]; cout << ans << endl; for (int i = 1;i <= n;i++) cout << a[i] << " " << a[2 * n + 1 - i] << endl; } return 0;}
K 速战速决
[THUPC 2023 初赛] 速战速决
题目描述
小 I 与小 J 正在玩一个叫做“开火车”，又称作“拖板车”和“小猫钓鱼”的扑克游戏。游戏规则如下，注意其与一般玩法可能有不同：
有 2n 张牌，其中对于整数 1≤i≤n，牌面为 i 的牌恰好有 2 张。
游戏开始时，小 I 和小 J 各拿其中 n 张牌组成双方的初始手牌。
维护一个公共牌堆（可以将其看作一个栈），初始没有牌。小 I 与小 J 依次行动，小 I 先手。一次行动时，行动方依次进行以下操作：
第一个数组 a，合法数组可以是 b=[1,2,3,1,1,1]。当 i=4,j=2 时，满足性质一。当i=6,j=3 时满足性质二。数组 b 无法满足性质三，所以恰好满足两条，合法。
题目描述
You are given an array a1,a2,…,an . You need to find an array b1,b2,…,bn consisting of numbers 1 , 2 , 3 such that exactly two out of the following three conditions are satisfied:
There exist indices 1≤i,j≤n such that ai=aj , bi=1 , bj=2 .
There exist indices 1≤i,j≤n such that ai=aj , bi=1 , bj=3 .
There exist indices 1≤i,j≤n such that ai=aj , bi=2 , bj=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≤t≤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≤n≤100) — the length of the array a .
The second line of each test case contains n integers a1,a2,…,an(1≤ai≤100) — the elements of the array a .
输出格式
For each test case, print -1 if there is no solution. Otherwise, print b1,b2,…,bn — 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 : ai=aj , bi=1 , and bj=2 . It also satisfies condition 2 because for i=6 , j=3 : ai=aj , bi=1 , and bj=3 . However, it does not satisfy condition 3 . In total, exactly two out of three conditions are satisfied.
分析
构造题，根据分析，只有当数量超过 2 个的数的种数大于等于 2，才有可能构造出符合要求的 b 数组。
参考代码
#include<bits/stdc++.h>using namespace std;const int maxn = 120;int a[maxn];// int cnt[maxn];int n;void solve() { cin >> n; // fill(cnt, cnt + sizeof(cnt), 0); int cnt[maxn] = {}; for (int i = 0;i < n;i++) { cin >> a[i]; cnt[a[i]]++; } int cntn = 0; for (int i = 1;i <= 101;i++) { if (cnt[i] >= 2) cntn++; } if (cntn < 2) { cout << -1 << endl; return; } bool ck[maxn] = { false }; bool f = true; for (int i = 0;i < n;i++) { int x = a[i]; if (cnt[x] >= 2 && !ck[x]) { if (f) { cout << 2 << " "; f = false; } else { cout << 3 << " "; } ck[x] = true; } else { cout << 1 << " "; } } cout << "\n";}int main(){ int t;cin >> t; while (t--) solve(); return 0;}
