补题链接：https://ac.nowcoder.com/acm/contest/31454
链接：https://ac.nowcoder.com/acm/contest/31454/A
来源：牛客网
题目描述
BaoBao the Witch is stuck in a maze with nn rows and nn columns, where the height of the cell in the ii-th row and the jj-th column is h_{i,j}h
i,j
. To get out of the maze, BaoBao has to find a path which passes through each cell exactly once. Each time she can only move into the neighboring cell sharing a same edge with the current one. But as we know, BaoBao is super lazy, so every time when she climbs up (that is to say, moving from a cell with a smaller height to another with a larger height) her happiness value will decrease. As her helping hand, your task is to find a valid path so that when moving along the path, the number of times BaoBao climbs up will not be more than the number of times she climbs down.
More formally, you need to find a sequence (x_1, y_1), (x_2, y_2), \cdots, (x_{n^2}, y_{n^2})(x
1
,y
1
),(x
2
,y
2
),⋯,(x
n
2
,y
n
2
) such that:
For all 1 \le i \le n^21≤i≤n
2
, 1 \le x_i, y_i \le n1≤x
i
,y
i
≤n;
For all 1 \le i, j \le n^2, i \neq j1≤i,j≤n
2
,i
=j, (x_i, y_i) \neq (x_j, y_j)(x
i
,y
i
)
=(x
j
,y
j
);
For all 2 \le i \le n^22≤i≤n
2
, |x_i - x_{i-1}| + |y_i - y_{i-1}| = 1∣x
i
−x
i−1
∣+∣y
i
−y
i−1
∣=1;
\sum\limits_{i=2}{n2}{[h_{x_{i-1}, y_{i-1}} < h_{x_i, y_i}]} \le \sum\limits_{i=2}{n2}{[h_{x_{i-1}, y_{i-1}} > h_{x_i, y_i}]}
i=2
∑
n
2
[h
x
i−1
,y
i−1
i
,y
i
]≤
i=2
∑
n
2
[h
x
i−1
,y
i−1
h
x
i
,y
i
], where [P][P] equals 11 when PP is true, and equals 00 when it is false.
Additionally, you discover that the heights in all cells are a permutation of n^2n
2
, so you just need to output the height of each cell in a valid path.
输入描述:
There are multiple test cases. The first line of the input contains an integer TT (1 \le T \le 1001≤T≤100) indicating the number of test cases. For each test case:
The first line contains an integer nn (2 \le n \le 642≤n≤64) indicating the size of the maze.
For the following nn lines, the ii-th line contains nn integers h_{i, 1}, h_{i, 2}, \cdots, h_{i,n}h
i,1
,h
i,2
,⋯,h
i,n
(1 \le h_{i, j} \le n^21≤h
i,j
≤n
2
) where h_{i,j}h
i,j
indicates the height of the cell in the ii-th row and the jj-th column. It’s guaranteed that all integers in the input make up a permutation of n^2n
2
.
输出描述:
For each test case output one line containing n^2n
2
separated by a space indicating the heights of each cell in a valid path. If there are multiple valid answers you can output any of them. It’s easy to prove that an answer always exists.
Please, DO NOT output extra spaces at the end of each line, or your answer may be considered incorrect!
示例1
输入
复制
1
2
4 3
2 1
输出
复制
4 3 1 2
题意：
思路：
#include链接：https://ac.nowcoder.com/acm/contest/31454/K
来源：牛客网
题目描述
BaoBao just learned how to use a data structure called link-cut tree to find cycles in a graph and decided to give it a try. BaoBao is given an undirected graph with nn vertices and mm edges, where the length of the ii-th edge equals 2^i2
i
. She needs to find a simple cycle with the smallest length.
A simple cycle is a subgraph of the original graph containing kk (3 \le k \le n3≤k≤n) vertices a_1, a_2, \cdots, a_ka
1
,a
2
,⋯,a
k
and kk edges such that for all 1 \le i \le k1≤i≤k there is an edge connecting vertices a_ia
i
and a_{(i \mod k) + 1}a
(imodk)+1
in the subgraph. The length of a simple cycle is the total length of the edges in the cycle.
输入描述:
There are multiple test cases. The first line of the input contains an integer TT indicating the number of test cases. For each test case:
The first line contains two integers nn and mm (3 \le n \le 10^53≤n≤10
5
, 1 \le m \le 10^51≤m≤10
5
) indicating the number of vertices and edges in the original graph.
For the following mm lines, the ii-th line contains two integers u_iu
i
and v_iv
i
(1 \le u_i, v_i \le n1≤u
i
,v
i
≤n) indicating an edge connecting vertices u_iu
i
and v_iv
i
with length 2^i2
i
. There are no self loops nor multiple edges. Note that the graph is not necessarily connected.
It’s guaranteed that neither the sum of nn nor the sum of mm of all test cases will exceed 10^610
6
.
输出描述:
For each test case output one line. If there are no simple cycles in the graph output “-1” (without quotes); Otherwise output kk integers separated by a space in increasing order indicating the indices of the edges in the simple cycle with the smallest length. It can be shown that there is at most one answer.
Please, DO NOT output extra spaces at the end of each line, or your solution may be considered incorrect!
示例1
输入
复制
2
6 8
1 2
2 3
5 6
3 4
2 5
5 4
5 1
4 2
4 2
1 2
4 3
输出
复制
2 4 5 6
-1
备注:
The first sample test case is shown below. The integers beside the edges are their indices (outside the parentheses) and lengths (inside the parentheses). The simple cycle with the smallest length consists of edges 22, 44, 55 and 66 with a length of 2^2 + 2^4 + 2^5 + 2^6 = 1162
2
+2
4
+2
5
+2
6
=116.
题意：
思路：
#include链接：https://ac.nowcoder.com/acm/contest/31454/F
来源：牛客网
题目描述
TheAbelian Sandpile Modelis a famous dynamical system displaying self-organized criticality. It has been studied for decades since it was introduced by Per Bak, Chao Tang and Kurt Wiesenfeld in a 1987 paper. The sandpile prediction is of wide interest in physics,
computer science, and mathematics, both for its beautiful algebraic structure and for its relevance to applications like load balancing and derandomization of models like internal diffusion-limited aggregation. The sandpile model is related to many other models and physical phenomena, like the rotor-routing model, avalanche models.
In the sandpile model, we are given an undirected graph GG whose vertices are indexed from 11 to nn. We’re also given nn integers a_1, a_2, \cdots, a_na
1
,a
2
,⋯,a
n
where a_ia
i
indicates that there are a_ia
i
chips placed on vertex ii initially. Each turn we will pick an arbitrary vertex vv such that the number of chips on vv is not smaller than the number of edges connecting vv, denoted as d_vd
v
. For each neighbor of vv, it will receive one chip from vv. Therefore, vv will lost d_vd
v
chips. This process is called firing or toppling. Firing will keep happening until no vertex vv has at least d_vd
v
chips.
It can be proven that the order of firing doesn’t affect the result. Meanwhile, it is also possible that the firing will never terminate. This instance is described as “recurrent”. Now you are given a clique and the initial number of chips. Determine whether this instance is a recurrent one. If not, please output the final number of chips for each node respectively.
A clique (also called a complete graph) is a graph where every two vertices are connected with an edge.
输入描述:
There is only one test case in each test file.
The first line of the input contains an integer nn (2 \leq n \leq 5 \times 10^52≤n≤5×10
5
) indicating the size of the clique.
The second line contains nn integers a_1, a_2, \cdots, a_na
1
,a
2
,⋯,a
n
(0 \leq a_i \leq 10^90≤a
i
≤10
9
) where a_ia
i
indicates the initial number of chips placed on vertex ii.
输出描述:
Output one line. If the given sandpile instance will terminate, output nn integers separated by a space where the ii-th integer indicates the final number of chips on the ii-th vertex. Otherwise output “Recurrent” (without quotes) instead.
Please, DO NOT output extra spaces at the end of each line or your solution may be considered incorrect!
示例1
输入
复制
5
5 0 3 0 3
输出
复制
3 3 1 3 1
示例2
输入
复制
2
1 0
输出
复制
Recurrent
备注:
For the first sample test case:
We can only select vertex 11 at the beginning. The number of chips becomes {1, 1, 4, 1, 4}{1,1,4,1,4}.We can now select vertex 33 or 55 because both of them have at least 44 chips. We select vertex 33 and the number of chips becomes {2, 2, 0, 2, 5}{2,2,0,2,5}. Selecting vertex 55 will lead to the same result.We now select vertex 55. The number of chips becomes {3, 3, 1, 3, 1}{3,3,1,3,1}. There is no vertex with at least 44 chips so the firing terminates.
For the second sample test case, we can select vertex 11 and 22 repeatedly. The firing never terminates.
题意：
思路：
#include链接：https://ac.nowcoder.com/acm/contest/31454/C
来源：牛客网
题目描述
BaoBao is playing the famous gameElden Ringthese days. It’s an open-world game in which you can control your character to travel from places to places. However, your character could also enter a trap and you need to figure out how to escape. Right now, BaoBao’s character is stuck in a 2-dimensional plane with deadly lasers. There are nn laser generators (each can be regarded as a point) shooting laser beams between every pair of them (so there are \frac{n(n-1)}{2}
2
n(n−1)
laser beams in total). The beams start and end at generator points and do not stretch to infinity.
Starting at point (0,0)(0,0), BaoBao wants to escape to point (10{10{10{10{10}}}}, 10{10{10{10{10}}}})(10
10
10
10
10
,10
10
10
10
10
) without touching any laser beam or generator. In order to do so, BaoBao can ask her friend DreamGrid to remove any number of laser generators, together with any laser beam that starts or ends at these generators. Output the minimum number of laser generators that need to be erased for the escape.
Note that BaoBao does not need to move in a specific direction to escape. Her escaping route can even be a curve if necessary.
输入描述:
There are multiple test cases. The first line of the input contains an integer TT indicating the number of test cases. For each test case:
The first line contains an integer nn (1 \le n \le 10^61≤n≤10
6
) indicating the number of laser generators.
For the following nn lines, the ii-th line contains two integers x_ix
i
and y_iy
i
(-10^9 \le x_i, y_i \le 10^9−10
9
≤x
i
,y
i
≤10
9
) indicating the location of the ii-th laser generator.
It is guaranteed that no two generators coincide, and no laser beam or generator will touch (0,0)(0,0).
It is also guaranteed that the sum of nn of all test cases will not exceed 10^610
6
.
输出描述:
For each test case output one line containing one integer indicating the minimum number of generators that need to be removed.
示例1
输入
复制
3
2
1 0
2 0
3
1 0
0 1
-1 -1
5
2 -1
1 2
-1 2
-2 -1
0 -2
输出
复制
0
1
2
备注:
The second and the third sample test cases are shown below. Solid dots and lines represent the remaining laser generators and beams, while hollow dots and dashed lines represent the removed laser generators and beams. The arrow is the escaping route.
题意：
思路：
#include