版权声明： 本博客所有文章除特别声明外，均采用 BY-NC-SA 许可协议。转载请注明出处！
title: "比赛记录 - Hello 2023" date: 2023-01-04 02:10:31 categories:
进度: 5 / 8
<!-- more -->Thalia is a Legendary Grandmaster in chess. She has $n$ trophies in a line numbered from $1$ to $n$ (from left to right) and a lamp standing next to each of them (the lamps are numbered as the trophies)
A lamp can be directed either to the left or to the right, and it illuminates all trophies in that direction (but not the one it is next to). More formally, Thalia has a string $s$ consisting only of characters 'L' and 'R' which represents the lamps' current directions. The lamp $i$ illuminates:
She can perform the following operation at most once:
Thalia asked you to illuminate all her trophies (make each trophy illuminated by at least one lamp), or to tell her that it is impossible to do so. If it is possible, you can choose to perform an operation or to do nothing. Notice that lamps cannot change direction, it is only allowed to swap adjacent ones
Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \leq t \leq 10\,000$). The description of the test cases follows
The first line of each test case contains a positive integer $n$ ($2 \leq n \leq 100\,000$) — the number of trophies
The second line of each test case contains a string $s$ of length $n$ consisting only of characters 'L' and 'R' — the $i$-th character describes the direction of the $i$-th lamp
It is guaranteed that the sum of $n$ over all test cases does not exceed $100\,000$
For each test case print $-1$ if it is impossible to illuminate all trophies by performing one operation (or doing nothing). Otherwise, print $0$ if you choose not to perform the operation (i.e., the trophies are illuminated by the initial positioning of the lamps), or an index $i$ ($1 \leq i < n$) if you choose to swap lamps $i$ and $i+1$
If there are multiple answers, print any
6
2
LL
2
LR
2
RL
2
RR
7
LLRLLLR
7
RRLRRRL
-1
1
0
-1
3
6
In the first example, it is possible to swap lamps $1$ and $2$, or do nothing. In any case, the string "LL" is obtained. Not all trophies are illuminated since trophy $2$ is not illuminated by any lamp — lamp $1$ illuminates nothing and lamp $2$ illuminates only the trophy $1$
In the second example, it is necessary to swap lamps $1$ and $2$. The string becomes "RL". Trophy $1$ is illuminated by lamp $2$ and trophy $2$ is illuminated by lamp $1$, hence it is possible to illuminate all trophies
In the third example, all trophies are initially illuminated — hence, not performing any operation is a valid solution
In the last two examples performing swaps is not necessary as all trophies are illuminated initially. But, the presented solutions are also valid
MKnez wants to construct an array $s_1,s_2, \ldots , s_n$ satisfying the following conditions:
More formally, $s_i \neq 0$ must hold for each $1 \leq i \leq n$. Moreover, it must hold that $s_1 + s_2 + \cdots + s_n = si + s{i+1}$ for each $1 \leq i < n$
Help MKnez to construct an array with these properties or determine that it does not exist
Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \leq t \leq 100$). The description of the test cases follows
The only line of each test case contains a single integer $n$ ($2 \leq n \leq 1000$) — the length of the array
For each test case, print "YES" if an array of length $n$ satisfying the conditions exists. Otherwise, print "NO". If the answer is "YES", on the next line print a sequence $s_1,s_2, \ldots, s_n$ satisfying the conditions. Each element should be a non-zero integer in the range $[-5000,5000]$, i. e. $-5000 \leq s_i \leq 5000$ and $s_i \neq 0$ should hold for each $1 \leq i \leq n$
It can be proved that if a solution exists then there also exists one which satisfies the additional constraints on the range
If there are several correct answers, print any of them
2
2
3
YES
9 5
NO
In the first test case, $[9,5]$ is a valid answer since $9+5$ (the sum of the two adjacent elements $s_1+s_2$) is equal to $9+5$ (the sum of all elements). Other solutions include $[6,-9], [-1,-2], [-5000,5000], \ldots$
For the second test case, let us show why some arrays do not satisfy the constraints:
This is not a proof, but it can be shown that the answer is "NO"
Baltic, a famous chess player who is also a mathematician, has an array $a_1,a_2, \ldots, a_n$, and he can perform the following operation several (possibly $0$) times:
Baltic's favorite number is $m$, and he wants $a_1 + a_2 + \cdots + a_m$ to be the smallest of all non-empty prefix sums. More formally, for each $k = 1,2,\ldots, n$ it should hold that
$$ a_1 + a_2 + \cdots + a_k \geq a_1 + a_2 + \cdots + a_m. $$
Please note that multiple smallest prefix sums may exist and that it is only required that $a_1 + a_2 + \cdots + a_m$ is one of them
Help Baltic find the minimum number of operations required to make $a_1 + a_2 + \cdots + a_m$ the least of all prefix sums. It can be shown that a valid sequence of operations always exists
Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \leq t \leq 10\,000$). The description of the test cases follows
The first line of each test case contains two integers $n$ and $m$ ($1 \leq m \leq n \leq 2\cdot 10^5$) — the size of Baltic's array and his favorite number
The second line contains $n$ integers $a_1,a_2, \ldots, a_n$ ($-10^9 \leq a_i \leq 10^9$) — the array
It is guaranteed that the sum of $n$ over all test cases does not exceed $2\cdot 10^5$
For each test case, print a single integer — the minimum number of required operations
6
4 3
-1 -2 -3 -4
4 3
1 2 3 4
1 1
1
5 5
-2 3 -5 1 -20
5 2
-2 3 -5 -5 -20
10 4
345875723 -48 384678321 -375635768 -35867853 -35863586 -358683842 -81725678 38576 -357865873
1
1
0
0
3
4
In the first example, we perform the operation $a_4 := -a_4$. The array becomes $[-1,-2,-3,4]$ and the prefix sums, $[a_1, \ a_1+a_2, \ a_1+a_2+a_3, \ a_1+a_2+a_3+a_4]$, are equal to $[-1,-3,-6,-2]$. Thus $a_1 + a_2 + a_3=-6$ is the smallest of all prefix sums
In the second example, we perform the operation $a_3 := -a_3$. The array becomes $[1,2,-3,4]$ with prefix sums equal to $[1,3,0,4]$
In the third and fourth examples, $a_1 + a_2 + \cdots + a_m$ is already the smallest of the prefix sums — no operation needs to be performed
In the fifth example, a valid sequence of operations is:
The array becomes $[-2,-3,5,-5,20]$ and its prefix sums are $[-2,-5,0,-5,15]$. Note that $a_1+a_2=-5$ and $a_1+a_2+a_3+a_4=-5$ are both the smallest of the prefix sums (and this is a valid solution)
Boris thinks that chess is a tedious game. So he left his tournament early and went to a barber shop as his hair was a bit messy
His current hair can be described by an array $a_1,a_2,\ldots, a_n$, where $a_i$ is the height of the hair standing at position $i$. His desired haircut can be described by an array $b_1,b_2,\ldots, b_n$ in a similar fashion
The barber has $m$ razors. Each has its own size and can be used at most once. In one operation, he chooses a razor and cuts a segment of Boris's hair. More formally, an operation is:
Notice that some razors might have equal sizes — the barber can choose some size $x$ only as many times as the number of razors with size $x$
He may perform as many operations as he wants, as long as any razor is used at most once and $a_i = b_i$ for each $1 \leq i \leq n$ at the end. He does not have to use all razors
Can you determine whether the barber can give Boris his desired haircut?
Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \leq t \leq 20\,000$). The description of the test cases follows
The first line of each test case contains a positive integer $n$ ($3\leq n\leq 2\cdot 10^5$) — the length of arrays $a$ and $b$
The second line of each test case contains $n$ positive integers $a_1, a_2, \ldots, a_n$ ($1 \leq a_i \leq 10^9$) — Boris's current hair
The third line of each test case contains $n$ positive integers $b_1, b_2, \ldots, b_n$ ($1 \leq b_i \leq 10^9$) — Boris's desired hair
The fourth line of each test case contains a positive integer $m$ ($1 \leq m \leq 2\cdot 10^5$) — the number of razors
The fifth line of each test case contains $m$ positive integers $x_1,x_2, \ldots, x_m$ ($1 \leq x_i \leq 10^9$) — the sizes of the razors
It is guaranteed that the sum of $n$ and the sum of $m$ over all test cases do not exceed $2\cdot 10^5$
For each test case, print "YES" if the barber can cut Boris's hair as desired. Otherwise, print "NO"
You can output the answer in any case (upper or lower). For example, the strings "yEs", "yes", "Yes", and "YES" will be recognized as positive responses
7
3
3 3 3
2 1 2
2
1 2
6
3 4 4 6 3 4
3 1 2 3 2 3
3
3 2 3
10
1 2 3 4 5 6 7 8 9 10
1 2 3 4 5 6 7 8 9 10
10
1 2 3 4 5 6 7 8 9 10
3
1 1 1
1 1 2
12
4 2 4 3 1 5 6 3 5 6 2 1
13
7 9 4 5 3 3 3 6 8 10 3 2 5
5 3 1 5 3 2 2 5 8 5 1 1 5
8
1 5 3 5 4 2 3 1
13
7 9 4 5 3 3 3 6 8 10 3 2 5
5 3 1 5 3 2 2 5 8 5 1 1 5
7
1 5 3 4 2 3 1
3
19747843 2736467 938578397
2039844 2039844 2039844
1
2039844
YES
NO
YES
NO
YES
NO
YES
In the first test case, Boris's hair is initially $[3,3,3]$. Let us describe a sequence of $2$ operations the barber can perform:
In the third test case, no operation has to be done since Boris's hair is already as desired
In the fourth test case, no cuts will be able to increase the third element in $[1,1,1]$ in a way that the array becomes $[1,1,2]$
显然 $b_i\leq a_i,~\forall i\in 1..n$ 且 $b_i\in c,~\forall a_i\ne b_i$ 时才可能可行
我们将需要修剪的 $i$ 按 $b_i$ 升序排列, 每次尽可能修建尽可能大的范围, 不难发现所有的 $i$ 至多被修剪一次, 维护修建范围的边界即可
This is an interactive problem
Anya has gathered $n$ chess experts numbered from $1$ to $n$ for which the following properties hold:
Anya does not know, for each pair, who is the player who beats the other
To organize a tournament, Anya hosts $n-1$ games. In each game, she chooses two players. One of them wins and stays, while the other one is disqualified. After all the games are hosted only one player will remain. A player is said to be a candidate master if they can win a tournament (notice that the winner of a tournament may depend on the players selected by Anya in the $n-1$ games)
Since Anya is a curious girl, she is interested in finding the candidate masters. Unfortunately, she does not have much time. To speed up the process, she will organize up to $2n$ simuls (short for "simultaneous exhibition", in which one player plays against many)
In one simul, Anya chooses exactly one player who will play against some (at least one) of the other players. The chosen player wins all games they would win in a regular game, and the same holds for losses. After the simul finishes, Anya is only told the total number of games won by the chosen player (but not which ones). Nobody is disqualified during a simul
Can you help Anya host simuls and determine the candidate masters?
The winning players in each pair could be changed between the simuls, but only in a way that preserves the results of all previous simuls. These changes may depend on your queries
Firstly, the jury sends one integer $n$ ($3 \leq n \leq 250$) which should be read — the number of players. After that, your program may ask queries or report an answer
To ask a query, print "? $i \; s_1 s_2 \ldots s_n$" (without quotes), where $i$ is the index of the player who will play against some of the other players in the simul. $s$ is a binary string that denotes the players they play against. $i$ plays against every player $j$ for which $s_j = 1$ holds (and $s_j = 1$ should hold for at least one $1 \leq j \leq n$). Please note that $s_i = 0$ must hold since a player cannot play against themselves, otherwise, the query is considered to be incorrect
After this, you should read an integer — the number of games player $i$ has won
When you have identified the answer, you must print "! $c_1 c_2 \ldots c_n$" (without quotes) and terminate your program. $c$ is a binary string which represents the candidate masters. Player $i$ is a candidate master if $c_i=1$ holds, otherwise, they are not
If you ask more than $2n$ queries or if one of the queries is malformed, the interaction terminates immediately and your program receives verdict Wrong Answer
After printing a query do not forget to output the end of line and flush the output. Otherwise, you will get Idleness limit exceeded. To do this, use:
fflush(stdout) or cout.flush() in C++;System.out.flush() in Java;flush(output) in Pascal;stdout.flush() in Python;Hacks are disabled in this problem
3
1
1
1
? 1 010
? 2 001
? 3 100
! 111
5
0
3
4
? 5 10110
? 2 10111
? 1 01111
! 10000
In the first example, the first query describes a simul in which player $1$ plays against player $2$ (and no one else). The answer to the query is $1$, meaning that player $1$ won the only game they played. We can conclude that $1$ beats $2$. Similarly, the second query tells us that $2$ beats $3$ and the third query tells us that $3$ beats $1$. All players are candidate masters in this case as
In the second example, the third query describes a simul in which player $1$ plays against every other player. The answer to the query is $4$, meaning that they won every game they played. It can be concluded that player $1$ also beats every other player. They can never lose, hence they are the only player who can remain at the end of every possible tournament, and the only possible candidate master
不难看出题目等价于:
有一个含 $n$ 个点的竞赛图, 你可以进行至多 $2n$ 次询问, 每次询问可以问某点在含该点的某个子图中的出度, 问该竞赛图中所有满足如下条件的点 $v$:
$$ \operatorname{dis}(v,v')\in\mathbb{N},~\forall v'\in V\setminus{v} $$
我们有引理
{% note danger no-icon %}
<a id="lm-E-1">引理 - E-1</a> 竞赛图 $T=\lang V,E\rang$ 中出度最大的点到任意点的距离不超过 $2$
<details open> <summary>证明</summary> 假设出度最大的点为 $v$, 与之相邻的点集为 $V_1$, $V_2=V\setminus(V_1\cup\{v\})$ 任取 $V_2$ 中的点 $u$, 若 $\operatorname{dis}(v,u)>2$, 则说明 $V_1\cup\{v\}$ 中所有的点均不与 $u$ 相邻, 由竞赛图的性质, $d_{out}(u)\geq|V_1|+1>d_{out}(v)$, 矛盾 </details>{% endnote %}
进一步, 竞赛图中出度最大的点满足要求
另外, 若该竞赛图是强连通的, 则所有点均满足条件, 否则, 我们考虑所有的强连通分量 $T_1,T_2,\dots,T_k$ (按拓扑序排列), 则
$$ d{out}(u)>d{out}(v),~\forall u\in T_i, v\in T_j, i<j $$
不难发现 $T_1$ 中的点即为所求
我们只需 $n$ 次查询获得所有点的出度, 之后按出度排序后计算 $T_1$ 即可
官方题解说可以将查询次数控制在 $n-1$, 也许可以进一步利用竞赛图的性质来优化算法
Misha had been banned from playing chess for good since he was accused of cheating with an engine. Therefore, he retired and decided to become a xorcerer
One day, while taking a walk in a park, Misha came across a rooted tree with nodes numbered from $1$ to $n$. The root of the tree is node $1$
For each $1\le i\le n$, node $i$ contains $a_i$ stones in it. Misha has recently learned a new spell in his xorcery class and wants to test it out. A spell consists of:
Misha can perform at most $2n$ spells and he wants to remove all stones from the tree. More formally, he wants $a_i=0$ to hold for each $1\leq i \leq n$. Can you help him perform the spells?
A tree with $n$ nodes is a connected acyclic graph which contains $n-1$ edges. The subtree of node $i$ is the set of all nodes $j$ such that $i$ lies on the simple path from $1$ (the root) to $j$. We consider $i$ to be contained in its own subtree
The first line contains a single integer $n$ ($2 \leq n \leq 2\cdot 10^5$) — the size of the tree
The second line contains an array of integers $a_1,a_2,\ldots, a_n$ ($0 \leq a_i \leq 31$), describing the number of stones in each node initially
The third line contains an array of integers $p_2,p_3,\ldots, p_n$ ($1 \leq p_i \leq i-1$), where $p_i$ means that there is an edge connecting $p_i$ and $i$
If there is not a valid sequence of spells, output $-1$
Otherwise, output a single integer $q$ ($0 \leq q \leq 2n$) in the first line — the number of performed spells
In the second line output a sequence of integers $v_1,v_2,\ldots,v_q$ ($1 \leq v_i \leq n$) — the $i$-th spell will be performed on the subtree of node $v_i$. Please note that order matters
If multiple solutions exist, output any. You don't have to minimize the number of operations
2
13 13
1
1
1
7
5 2 8 3 4 1 31
1 1 2 2 3 3
-1
9
3 31 1 2 7 30 7 3 1
1 1 1 2 5 5 3 4
6
3 2 3 1 2 2
Please refer to the following pictures for an explanation of the third test. Only the first $4$ spells are shown since the last $2$ do nothing. The first picture represents the tree initially with the number of stones for each node written above it in green. Changes applied by the current spell are highlighted in red
The time has finally come, MKnez and Baltic are to host The Game of the Century. For that purpose, they built a village to lodge its participants
The village has the shape of an equilateral triangle delimited by three roads of length $n$. It is cut into $n^2$ smaller equilateral triangles, of side length $1$, by $3n-3$ additional roads which run parallel to the sides. See the figure for $n=3$. Each of the $3n$ roads is made of multiple (possibly $1$) road segments of length $1$ which connect adjacent intersections
The direction has already been chosen for each of the $3n$ roads (so, for each road, the same direction is assigned to all its road segments). Traffic can only go in the specified directions (i. e. the roads are monodirectional)
You are tasked with making adjustments to the traffic plan so that from each intersection it is possible to reach every other intersection. Specifically, you can invert the traffic direction of any number of road segments of length $1$. What is the minimal number of road segments for which you need to invert the traffic direction?
Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \leq t \leq 10\,000$). The description of the test cases follows
The first line of each test case contains a positive integer $n$ ($1\leq n\leq 10^5$) — the size of the triangular village's sides
Three lines follow, each containing a binary string of length $n$ which describes the traffic directions of the roads
The $i$-th of the following three lines contains a binary string $s_i$ of length $n$ representing the direction of each road parallel to the road segment denoted by $i$ in the picture above. In particular, the $j$-th character of $s_i$ is "1" if the $j$-th shortest road (parallel to the road segment denoted by $i$ in the picture) has the same direction of the road segment denoted by $i$ in the picture, while it is "0" if it has the opposite direction. So the first character of $s_i$ describes the direction of the road containing only $1$ road segment, while the last character describes the direction of the road containing $n$ road segments
It is guaranteed that the sum of $n$ over all test cases does not exceed $10^5$
For each test case, print the minimum number of road segments for which you need to invert the traffic direction
3
3
001
001
010
1
0
0
0
3
111
011
100
2
0
3
The first example corresponds to the picture in the statement. There exist multiple solutions that invert the traffic direction of exactly $2$ road segments, but inverting only $1$ road segment never makes it possible to reach every intersection from any other. One of the possible solutions is shown in the picture below in which the inverted road segments are highlighted in blue
In the second example, the answer is $0$ since it is already possible to reach every intersection from any other
Iron and Werewolf are participating in a chess Olympiad, so they want to practice team building. They gathered $n$ players, where $n$ is a power of $2$, and they will play sports. Iron and Werewolf are among those $n$ people
One of the sports is tug of war. For each $1\leq i \leq n$, the $i$-th player has strength $s_i$. Elimination rounds will be held until only one player remains — we call that player the absolute winner
In each round:
Iron already knows each player's strength and is wondering who can become the absolute winner and who can't if he may choose how the teams will be formed in each round, as well as the winning team in case of equal strengths
The first line contains a single integer $n$ ($4 \leq n \leq 32$) — the number of players participating in tug of war. It is guaranteed that $n$ is a power of $2$
The second line consists of a sequence $s_1,s_2, \ldots, s_n$ of integers ($1 \leq s_i \leq 10^{15}$) — the strengths of the players
In a single line output a binary string $s$ of length $n$ — the $i$-th character of $s$ should be $1$ if the $i$-th player can become the absolute winner and it should be $0$ otherwise
4
60 32 59 87
1001
4
100 100 100 100
1111
8
8 8 8 8 4 4 4 4
11110000
32
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32
00000000000000001111111111111111
16
1 92875987325987 1 1 92875987325986 92875987325985 1 92875987325988 92875987325990 92875987325989 1 1 92875987325984 92875987325983 1 1
0100110111001000
In the first example, players $1$ and $4$ with their respective strengths of $60$ and $87$ can become the absolute winners
Let's describe the process for player $1$. Firstly, we divide the players into teams $[1,3]$ and $[2,4]$. Strengths of those two teams are $60+59=119$ and $32+87=119$. They they are equal, Iron can choose to disqualify any of the two teams. Let his choice be the second team
We are left with players $1$ and $3$. Since $1$ has greater strength ($60>59$) they win and are declared the absolute winner as they are the last remaining player
In the third example, the strengths of the remaining players may look like $[8,8,8,8,4,4,4,4] \rightarrow [8,8,4,4] \rightarrow [8,4] \rightarrow [8]$. Each person with strength $8$ can become the absolute winner and it can be proved that others can't