There is a $$$n$$$-node tree with a special node $$$m$$$, Alice and Bob play a game on this tree, in which in each operation they must select an edge on the part of the tree where it exists, delete the edge and split the tree into two parts, keeping the part with the special node $$$m$$$ and deleting the other part. When there is only one node left in the tree, it is not possible to delete the edge, and the operator loses the game.
In each game, Alice starts, and the two players take turns, knowing that they will do the optimal operation in each round, so who wins the game if the special nodes $$$m$$$ are numbered from $$$1$$$ to $$$n$$$, respectively?
In the first line, an integer $$$t(1\le t \le 10^4)$$$, representing the number of data sets.
For each group of data:
The first line, one integer $$$n(1\le n \le 3·10^5)$$$, represents the number of nodes in the tree.
For the next $$$n-1$$$ rows, two integers $$$u,v(1\le u,v \le n)$$$ per row, representing one edge of the tree, ensuring that the input data is a tree.
It is guaranteed that the sum of $$$n$$$ within the same test point does not exceed $$$3·10^5$$$.
For each set of data, output a line of string $$$ans$$$ of length $$$n$$$, with the $$$i$$$ th character representing who wins the game if the special node $$$m$$$ is $$$i$$$. If Alice wins, $$$ans[i]$$$ is the character 'A'; otherwise $$$ans[i]$$$ is the character 'B'.
4 2 1 2 3 1 2 3 2 4 1 2 1 3 1 4 4 1 2 4 2 3 4
AA ABA AAAA AAAA
Nanami traveled to the Kingdom of Rectangles, where there are all kinds of rectangles. Here, she also finds a rectangular clearing of size $$$n\times m$$$ with the coordinates of the lower left corner of the clearing being $$$(0,0)$$$ and the coordinates of the upper right corner being $$$(n,m)$$$.
Nanami is a curious girl who places and removes rectangles within the empty space, and she wants to ask you if every square of that empty space is covered and only covered only $$$1$$$ time after each operation.
In the first line, an integer $$$t(1\le t \le 10^4)$$$, representing the number of groups in each data set.
For each group of data:
In the first row, three integers $$$n,m,q(1\le n,m \le 10^9;1\le q \le 2·10^5)$$$, representing the size of the matrix and the number of operations, respectively.
The next $$$q$$$ rows, each with $$$5$$$ integers $$$op,a,b,c,d(0\le op \le 1;0\le a\lt c \le n;0\le b\lt d \le m)$$$, represent the type of operation and the position of the matrix where the operation is performed. Where $$$op=0$$$ represents the removal matrix and $$$op=1$$$ represents the placement matrix, it is guaranteed that the removed matrices were originally placed and that for each removal, if more than one matrix position is duplicated, only $$$1$$$ is removed.
It is guaranteed that the sum of $$$q$$$ within the same test point does not exceed $$$2·10^5$$$.
After each operation, output a line "YES" if every square in the empty space is covered and only $$$1$$$ times; otherwise, output a line "NO".
You can output "YES" and "NO" in any case form (e.g., the strings "yES", "yes", and "Yes" will all be treated as affirmative answers).
3 3 4 6 1 0 0 3 4 1 0 0 3 4 0 0 0 3 4 0 0 0 3 4 1 0 0 2 4 1 2 0 3 4 1 1 1 1 0 0 1 1 4 3 8 1 0 0 4 3 1 0 0 4 3 1 0 0 4 3 1 0 0 4 2 0 0 0 4 3 0 0 0 4 3 1 0 2 4 3 0 0 0 4 3
YES NO YES NO NO YES YES YES NO NO NO NO NO NO YES
Nanami is playing Minecraft, where the map can be thought of as a $$$n\times m$$$ grid. Monsters are constantly appearing from outside this grid, so Nanami needs to build a wall of obstacles to protect her house. When monsters move, they can move to any empty grid that has an adjacent edge to the current grid.
The grid contains the following three types: '.' for empty grids, '#' for grids with obstacles, and 'H' for Nanami's house; Nanami can place a new obstacle at any grid point that does not have an obstacle or a house.
At the same time, Minecraft has a setting where the cost of placing an obstacle on different grid points is different. In other words, there is a two-dimensional matrix $$$a$$$, and the price of placing an obstacle at grid point $$$(i,j)$$$ is $$$a_{i,j}$$$.
Nanami wants to ask you what is the smallest price she would have to pay if she wanted to protect all her houses.
In the first line, an integer $$$t(1\le t \le 333)$$$, representing the number of data sets.
For each group of data:
The first line, two integers $$$n,m(3\le n,m \le 1000)$$$, represents the size of the Minecraft map.
The next consecutive $$$n$$$ rows, each consisting of '.' , '#' or 'H', representing the map of Minecraft.
The next consecutive $$$n$$$ lines, each with $$$m$$$ integers $$$a_{i,j},\dots,a_{i,m}(0\le a_{i,j}\le 10^5)$$$, represent the price of placing an obstacle $$$a_{i,j}$$$ at grid point $$$(i,j)$$$.
It is guaranteed that a house (i.e. 'H') will not appear on the map boundary and that there is at least one 'H' on the map.
It is guaranteed that all corresponding positions of matrix $$$a$$$ that do not have '.' are $$$0$$$, and that the prices of the locations corresponding to '.' are greater than $$$0$$$. The price of the corresponding location is greater than $$$0$$$.
Ensure that the sum of $$$n\times m$$$ within the same test point does not exceed $$$3000$$$.
For each set of data, first output a line of integers $$$c$$$, representing the minimum price Nanami will pay. Next, output $$$n$$$ lines of string of length $$$m$$$, with each character being '.', '#' or 'H', representing Nanami's solution for placing the obstacle. , '#' or 'H', representing Nanami's solution for placing obstacles. Note that Nanami can only place obstacles in spaces, and cannot move existing obstacles or her house.
Any obstacle solution that meets the requirements of the question will be considered correct.
5 3 3 .#. #H. .#. 1 0 1 0 0 2 1 0 1 3 3 ### #H# ### 0 0 0 0 0 0 0 0 0 5 6 #...#. ...H.. ##..## ...#.# ###... 0 1 2 2 0 9 1 1 9 0 3 1 0 0 1 1 0 0 9 9 9 0 9 0 0 0 0 8 8 8 4 4 .##. .H.# ..H. .#.. 23 0 0 75 13 0 42 0 1 25 0 1 17 0 13 96 6 5 ..... .H... ..... ..... .H... ...#. 2 1 2 1 1 2 0 3 2 1 2 2 1 2 1 3 2 3 1 1 1 0 2 2 2 2 2 1 0 1
2 .#. #H# .#. 0 ### #H# ### 7 #.###. .#.H.# ###.## ...#.# ###... 28 .##. #H.# #.H# .##. 15 .#... #H#.. .#... .#... #H#.. .#.#.
Nanami has given you an array $$$a$$$ of length $$$n$$$ which she needs you to color.
But before you color it, she gives you $$$m$$$ requirements, each of which is denoted as $$$x,y,l,r(x\neq y;0\le l\le r \le 2)$$$, which means that for two positions $$$x,y$$$, the number of positions that are colored must be greater than or equal to $$$l$$$ and less than or equal to $$$r$$$.
Nanami wants to ask you, what is the smallest possible value of the maximum minus the minimum of the numbers of all the colored positions, provided that all the $$$m$$$ requirements are met?
If no position is colored, then the value is $$$0$$$.
In the first line, an integer $$$t(1\le t\le 10^4)$$$, representing the number of data sets.
For each group of data:
First row, two integers $$$n,m(2\le n\le 10^5;1\le m\le 10^5)$$$, representing the length of the array and the number of coloring requirements.
Second row, $$$n$$$ integers $$$a_1,a_2,\dots,a_n(-10^8\le a_i \le 10^8)$$$, representing the array $$$a$$$.
The third to $$$m+2$$$ rows, each with four integers $$$x,y,l,r(1\le x,y\le n;x\neq y;0\le l\le r \le 2)$$$, represent a coloring request.
It is guaranteed that the sum of $$$n+m$$$ within the same test point will not exceed $$$10^5$$$.
For each set of data, if a coloring scheme exists, then first output a line of integers representing the maximum minus the smallest possible minimum value of the digits at all positions that are colored. Next, on the second line, output a binary string $$$s$$$ of length $$$n$$$. If $$$s_i=0$$$, the $$$i$$$th position is not colored; if $$$s_i=1$$$, the $$$i$$$th position is colored.
If no color scheme exists, only one integer line $$$-1$$$ is output.
Any coloring scheme that satisfies the requirements of the question is considered correct.
5 5 2 -1 2 1 3 100 2 1 1 2 3 5 1 2 2 2 0 0 1 2 0 0 1 2 1 1 3 1 916 916 916 1 3 0 2 8 4 62 -43 -27 -25 73 -87 17 34 4 5 1 2 4 6 0 1 2 6 2 2 2 7 0 2 6 5 -4458 8270 5697 1102 2620 -5323 1 5 0 1 2 6 0 1 4 2 2 2 2 1 0 1 5 2 1 1
1 01100 -1 0 000 160 01001100 7168 010100
There are $$$n$$$ ropes $$$s$$$ on the table, each of integer length. In each round, Alice and Bob do the following:
Alice chooses any two ropes and splices them together end to end. In other words, Alice chooses any two differently numbered ropes $$$i,j$$$ and creates a rope $$$k$$$ of length $$$s_k=s_i+s_j$$$, while the $$$i,j$$$ ropes disappear.
Bob chooses any rope of length greater than $$$1$$$ and splits this rope into two ropes of integer lengths. In other words, Bob chooses a rope $$$k$$$ of length greater than $$$1$$$ and creates two ropes $$$i,j$$$ of length $$$s_i,s_j$$$, where $$$s_i+s_j=s_k$$$ and the rope $$$k$$$ disappears.
The two of them will perform $$$x$$$ rounds of operations, with Alice starting each round, and Alice wants the length of the longest of the ropes to be as large as possible at the end of the operation, while Bob wants the length of the longest of the ropes to be as small as possible at the end of the operation. What is the length of the longest rope out of all $$$n$$$ ropes at the end of all operations, if they both make optimal decisions each time.
In the first line, an integer $$$t(1\le t\le 10^4)$$$, representing the number of data sets.
For each group of data:
First row, two integers $$$n,k(2\le n\le 5·10^5;1\le x\le 5·10^5)$$$, representing the number of ropes and the number of rounds operated.
The second line, $$$n$$$ integers $$$s_1,\dots,s_n(1\le s_i\le 10^9)$$$, represents the length of each rope.
It is guaranteed that neither $$$n$$$ nor $$$x$$$ will sum to more than $$$5·10^5$$$ within the same test point.
For each set of data, output a line of integers representing the length of the longest rope out of all the ropes at the end of all the operations, provided that both Alice and Bob will make the optimal decision each time.
5 3 1 1 2 3 5 100 5 5 5 5 5 8 2 1 3 2 5 6 10 3 6 6 3 1 1 1 1 1 4 2 2 1 1
3 5 10 3 1
No two snowflakes in the world are same.
Nanami sees an object that looks like a snowflake, but she wonders if it is a real snowflake.
She thinks that a real snowflake should consist of a regular polygon inside and a separate identical (isomorphic) "subtree" containing vertices at each vertex of the square polygon. A tree is an undirected acyclic connected graph.
She now gives you an object that looks like a snowflake, and she wants you to decide if it is a real snowflake.
We say that two trees $$$T_1,T_2$$$ are isomorphic if and only if there exists a one-to-one mapping function from a node on $$$T_1$$$ to a node on $$$T_2$$$ while preserving the consistency of the root node.
In the first line, an integer $$$t(1\le t \le 10^4)$$$, representing the number of data sets.
For each group of data:
The first row, two positive integers $$$n,m(3\le n\le 5·10^5;0\le m \le \min(5·10^5,\frac{n-(n-1)}{2}))$$$, represents the number of vertices and edges on the object.
The next consecutive $$$m$$$ rows, each with two positive integers $$$u,v$$$, represent an undirected edge on the object, with the guarantee that the edge will not be given repeatedly and that there is no self-loop in the graph.
There is no guarantee that the given graph is connected.
It is guaranteed that the sum of all $$$n$$$ and $$$m$$$ within the same test point does not exceed $$$5·10^5$$$.
For each set of data, output a line of the string "YES" if the object is a positive snowflake; otherwise, output "NO".
You can output "YES" and "NO" in any case form (e.g., the strings "yES," "yes," and "Yes" will all be treated as positive answers).
5 6 6 1 2 2 3 3 1 1 5 4 2 3 6 4 3 1 2 2 4 3 2 4 4 1 3 3 2 2 4 1 4 9 12 1 2 2 3 3 1 2 4 5 4 2 5 1 7 6 7 1 6 8 3 3 9 8 9 6 6 1 2 2 3 3 1 4 5 6 5 6 4
YES NO YES NO NO
3 9 9 1 2 3 2 3 1 3 4 5 3 2 6 1 7 8 2 9 1 12 12 1 2 3 2 3 1 3 4 5 3 2 6 1 7 8 2 9 1 8 6 4 5 7 9 4 3 1 2 2 3 3 4
YES NO NO
You can see pictures of Examples in contest materials.
Nanami buys $$$n$$$ servers, which are numbered $$$1,\dots,n$$$, in order to train a large language model. Any $$$i$$$ server is connected to any $$$i+1$$$ server by a unidirectional wire that transfers power $$$(i \lt n)$$$.
Initially, each server also has its own battery, which provides $$$a_1,\dots,a_n$$$. At the same time, Nanami can add a battery that provides $$$b$$$ of power to any of the servers, and the power provided by this battery can also be transmitted by wires.
In the process of training a large language model, a number of consecutive servers need to be numbered to compute together, so each of these servers needs to have at least $$$k$$$ points of power to provide (either its own battery or power transferred from a previous server).
Nanami wants to ask you, given that the wires between the $$$l-1$$$ and $$$l$$$ servers are cut off $$$(l \gt 1)$$$, what is the minimum number of batteries she needs to add to the $$$l$$$ servers to provide at least $$$k$$$ points of power if she wants to have at least $$$k$$$ points of power available to the $$$l$$$ servers numbered from $$$l$$$ to $$$r$$$?
The first line, an integer $$$n(1\le n\le 2·10^5)$$$, represents the number of servers.
The next line has $$$n$$$ integers $$$a_1,\dots,a_n(1\le a_i\le 10^9)$$$, representing the amount of power provided by the batteries that each server also comes with.
The third line, an integer $$$q(1\le q\le 2·10^5)$$$, represents the number of queries.
The next $$$q$$$ lines, each with three integers $$$l,r,k(1\le l\le r\le n;1\le k\le 10^9)$$$, represent the number of times the query is asked to disconnect the wires between the $$$l-1$$$ and $$$l$$$ servers $$$(l \gt 1)$$$, and if the servers numbered $$$l$$$ through $$$r$$$ are to have at least $$$k$$$ points of power, she will need to add a battery to the servers numbered $$$l$$$ to $$$r$$$ to provide a minimum of $$$k$$$ points of power. What is the minimum number of batteries she needs to add to the server numbered $$$l$$$ to provide power?
Each query is independent, which means that Nanami doesn't actually add batteries, and the original batteries are not consumed.
There are $$$q$$$ lines, and for each query, an integer line is output representing the minimum amount of power that Nanami will need to provide by adding batteries to the server numbered $$$l$$$.
10 3 5 7 9 8 2 2 1 1 3 7 2 5 10 6 7 1 2 6 2 9 10 7 1 10 7 1 4 10 1 5 7
11 0 0 10 29 16 6
10 12 1 18 7 10 1000000000 999999999 13 25 999999979 10 6 10 18 7 8 500000520 3 7 825490234 4 10 129038019 1 2 3 5 8 377 2 9 7 7 10 438925 1 5 17 2 4 114514
0 1028 2476470667 258076021 0 367 6 0 37 343516
There are two types of blocks, sizes $$$1\times 2$$$ and $$$1\times 3$$$, and there is a long slot of $$$2\times n$$$ where you can rotate the blocks (or not) and then put them into this slot. Once the blocks are placed in the slot, they must not extend beyond the boundaries of the slot.
If there are some positions in the slot that need to be covered by blocks and only once, and some positions that cannot be covered by blocks, can the coverage requirement be satisfied with both types of blocks?
In the first line, an integer $$$t(1\le t\le 10^4)$$$, representing the number of data sets.
For each group of data:
On the first line, an integer $$$n(3\le n\le 10^5)$$$, representing the length of the slot.
For the next two lines, a binary string of length $$$n$$$ each, if the string is $$$0$$$ at that position, it means that this place should not be covered by blocks; otherwise, it means that this place should be covered by blocks.
It is guaranteed that the sum of $$$n$$$ within the same test point does not exceed $$$10^5$$$.
For each set of data, output a line "YES" if some placement scheme exists that would fulfill the requirement; otherwise, output a line "NO".
You can output "YES" and "NO" in any case form (e.g., the strings "yES", "yes", and "Yes" will all be treated as positive answers).
4 3 010 111 3 001 111 5 01101 11111 8 01001101 11011011
NO YES YES NO
Miss YiYi has a $$$n\times n$$$ field of golden sunshine sunflowers, two squares in the field are connected when and only when the two squares have a common edge, now some squares have been planted with sunflowers, now please help her plant at most $$$\lfloor \frac{n\times n}{2} \rfloor$$$ more sunflowers, so that all squares with sunflowers form a connected block (i.e. any pair of squares with sunflowers can reach each other through the sunflower squares). grids form a connected block (i.e., any pair of grids planted with sunflowers can reach each other through the sunflower grid).
Where $$$\lfloor x \rfloor$$$ represents the downward rounding of $$$x$$$, e.g. $$$\lfloor \frac{1}{2} \rfloor=0$$$, $$$\lfloor \frac{9}{2} \rfloor=4$$$ and $$$\lfloor \frac{16}{2} \rfloor=8$$$.
In the first line, an integer $$$t(1\le t \le 50)$$$, representing the number of data sets.
For each data group:
The first row, an integer $$$n(1\le n \le 50)$$$, represents the size of the flower field.
The next $$$n$$$ lines are of length $$$n$$$ consisting only of '#' and '.' strings consisting only of '#' and '.', with '#' representing the grid where the sunflowers are planted and '.' represents the space subgrid.
For each set of data, output a $$$n$$$ line of length $$$n$$$ consisting only of '#' and '.' which is a string consisting of only '#' and '.', with '#' representing the grid where the sunflowers are planted and '.' represents the space sub-grid, which represents your planting scheme, and you cannot move the position of the original sunflower.
It can be proved that there must exist a planting scheme that satisfies Miss YiYi's needs under the conditions required by the question, and any scheme that satisfies the requirements of the question is correct.
6 1 . 2 #. .# 3 #.# .#. #.# 4 ..#. .... ##.# ..#. 5 #...# ..... #...# ..... #...# 6 .....# ...... ...... ...... ..##.. #.....
. ## ## ### .#. ### ..## ...# #### ..#. #...# ##### #...# ##### #...# ..#### ..#... ..#... ..#... ..##.. ###...
The only difference between the easy and hard versions is the different restrictions on $$$n,\sum |a|,x$$$.
Given a sequence $$$a$$$ of length $$$n$$$ and an integer $$$x$$$, you need to partition the sequence into disjoint $$$k$$$ segments. We call these $$$k$$$ segments $$$[[l_1,r_1],[l_2,r_2],\dots,[l_k,r_k]]$$$ and the division needs to satisfy $$$l_1=1,r_k=n,r_i=l_{i+1}-1(i \lt k)$$$.
Please find the minimum value of $$$\sum_{idx=1}^k\sum_{i={l_{idx}}}^{r_{idx}}\sum_{j=i}^{r_{idx}}[(\sum_{s=i}^{j}a_s)=x]$$$, i.e., the minimum of the sum of the number of subsections of each segment of the division that sums to $$$x$$$.
$$$[expr]$$$ represents the boolean value of the expression $$$expr$$$, i.e., $$$[expr]=1$$$ if $$$expr$$$ is true; otherwise, $$$[expr]=0$$$.
A subsegment of a sequence $$$a_1,a_2,\dots,a_n$$$ is the existence of two subscripts $$$l,r$$$ satisfying $$$1\le l\le r\le n$$$, then $$$[a_l,a_{l+1},\dots,a_r]$$$ is a subsegment of the sequence, and $$$\sum_{i=l}^{r}a_i$$$ is the sum of the subsegments.
In the first line, two integers $$$n,k,x(1\le n\le3000;1\le k\le\min(20,n);|x|\le 9·10^6)$$$, representing the length of the sequence, the number of segments dividing the sequence, and the value of the integer $$$x$$$, respectively.
In the second line, a sequence $$$a$$$ of length $$$n$$$, where $$$|a_i|\le 3000$$$.
Outputs an integer representing the minimum of the sum of the number of sub-segments of each segment of the division that sums to $$$x$$$ across all division schemes.
4 2 2 2 2 -2 0
2
9 3 0 0 -1 -1 1 -1 1 1 -1 -1
3
1 1 3000 3000
1
6 2 -2 2 3 2 -1 0 3
0
In the first set of samples, take the following division $$$[[1,1],[2,4]]$$$ and the answer is $$$1+1=2$$$.
In the second set of samples, take the following division $$$[[1,5],[6,7],[8,9]]$$$ and the answer is $$$3+0+0=3$$$.
The only difference between the easy and hard versions is the different restrictions on $$$n,\sum |a|,x$$$.
Given a sequence $$$a$$$ of length $$$n$$$ and an integer $$$x$$$, you need to partition the sequence into disjoint $$$k$$$ segments. We call these $$$k$$$ segments $$$[[l_1,r_1],[l_2,r_2],\dots,[l_k,r_k]]$$$ and the division needs to satisfy $$$l_1=1,r_k=n,r_i=l_{i+1}-1(i \lt k)$$$.
Please find the minimum value of $$$\sum_{idx=1}^k\sum_{i={l_{idx}}}^{r_{idx}}\sum_{j=i}^{r_{idx}}[(\sum_{s=i}^{j}a_s)=x]$$$, i.e., the minimum of the sum of the number of subsections of each segment of the division that sums to $$$x$$$.
$$$[expr]$$$ represents the boolean value of the expression $$$expr$$$, i.e., $$$[expr]=1$$$ if $$$expr$$$ is true; otherwise, $$$[expr]=0$$$.
A subsegment of a sequence $$$a_1,a_2,\dots,a_n$$$ is the existence of two subscripts $$$l,r$$$ satisfying $$$1\le l\le r\le n$$$, then $$$[a_l,a_{l+1},\dots,a_r]$$$ is a subsegment of the sequence, and $$$\sum_{i=l}^{r}a_i$$$ is the sum of the subsegments.
In the first line, two integers $$$n,k,x(1\le n\le 10^5;1\le k\le\min(20,n);|x|\le 10^7)$$$, representing the length of the sequence, the number of segments dividing the sequence, and the value of the integer $$$x$$$, respectively.
In the second line, a sequence $$$a$$$ of length $$$n$$$, where $$$|a_i|\le 10^5$$$.
Extra restrictions for the hard version: guarantee $$$\sum_{i=1}^n |a_i|\le 10^7$$$.
Outputs an integer representing the minimum of the sum of the number of sub-segments of each segment of the division that sums to $$$x$$$ across all division schemes.
4 2 2 2 2 -2 0
2
9 3 0 0 -1 -1 1 -1 1 1 -1 -1
3
1 1 3000 3000
1
6 2 -2 2 3 2 -1 0 3
0
In the first set of samples, take the following division $$$[[1,1],[2,4]]$$$ and the answer is $$$1+1=2$$$.
In the second set of samples, take the following division $$$[[1,5],[6,7],[8,9]]$$$ and the answer is $$$3+0+0=3$$$.
Finally, Nanami leaves you a note that says:
Here's the last question: Given a sequence $$$a$$$ of length greater than or equal to $$$2$$$, you must remove an integer $$$c$$$ from the sequence and get an integer $$$d$$$ strictly less than $$$c$$$ that already exists in the sequence, what is the maximum value of the integer $$$d$$$ that you can get?
In the first line, an integer $$$t(1\le t \le 100)$$$, representing the number of data sets.
For each data group:
The first line, an integer $$$n(2\le n \le 100)$$$, represents the length of the sequence.
The second line, $$$n$$$ integers $$$a_1,\dots,a_n(1\le a_i \le 100)$$$, represents the sequence $$$a$$$.
It is guaranteed that for each sequence, there must exist two subscripts $$$i,j$$$ satisfying $$$i\neq j$$$ and $$$a_i\neq a_j$$$.
For each set of data, output a line of integers representing the maximum value you can get for the integer $$$d$$$.
5 2 1 2 3 1 2 3 3 1 4 2 5 1 2 9 4 3 7 5 2 1 1 3 1 4
1 2 2 4 4