CCF CSP-S 2024 Improvement Group Preliminary Round Analysis

Certified Software Professional - Senior non-professional level software competency certification test

The code for reading the program and refining the program title is not provided in this explanation, if you need it, please go through the Related links downloading

Please correct me if I'm wrong.

solution

 $AACBB BDABD ACBCD ✓\times\timesBC ✓✓✓BCC ✓\times✓CAC AAAAA AABAA$

single-item choice

1

On a Linux system, which command should you use if you want to display the path to the current working directory?

A pwd
B cd
C ls
D echo

pwd : print working directory
cd : Jump to the specified directory
ls : List all subfiles and subfolders of the current directory
echo : Outputs the specified content

2

Suppose that each element in an array of integers of length n has a different value from each other and that the array is unordered. What is the time complexity of finding the largest element in this array?

A \(O(n)\)
B \(O(logn)\)
C \(O(nlogn)\)
D \(O(1)\)

Unordered arrays can only be found by comparing two by two, requiring a comparison of the\(n-1\) times (the first time does not need to be compared), and therefore for the\(O(n)\)

3

In C++, which of the following function calls causes an overflow?

A int foo(){ return 0;}
B int bar(){int x=1;return x; }
C void baz(){ int a[1000];baz();)
D void qux(){ return; }

There are two general types of function stack overflows: a variable within a function is too large, or the function recursion depth is too deep

here arebaz() Functions call themselves repeatedly without a termination condition and therefore overflow the

4

In a game with\(10\) Numerous players are participating and the top three will receive gold, silver and medals. If ties are not allowed and each player can only win one medal, how many different ways of awarding medals are there?

A 120
B 720
C 504
D 1000

It may be useful to pick a length of\(3\) sequence of winning gold, silver, and bronze medals in that order, then the program has\(A^{3}_{10}=10\times 9\times 8=720\) kind

5

Which of the following data structures is best suited to implement a first-in-first-out (FIFO) function?

A Stack
B. Queues
C Linear tables
D Binary search tree

The stack is first in, first out.

The latter two data structures do not have the ability to store and populate basic data

Linear tables are functionally similar to arrays

6

known (science)\(f(1)=1\)and for\(n\ge2\) there are\(f(n)=f(n-1)+f(⌊n/2⌋)\) follow\(f(4)\) The value of.

A \(4\)
B \(5\)
C \(6\)
D \(7\)

\(f(2)=f(1)+f(1)=2\)

\(f(3)=f(2)+f(1)=3\)

\(f(4)=f(3)+f(2)=5\)

7

Suppose there is a file containing\(n\) An undirected graph of four vertices and the graph is an Eulerian graph. Which of the following descriptions of the graph is not necessarily correct?

A All vertices have even degrees
B The map is connected
C There exists an Euler loop in this diagram
D The graph has an odd number of sides

Euler diagram definition: a diagram consisting only of Euler circuits

Euler's loop: i.e., a graph that can be drawn in one stroke. Formally, an Euler loop is a path that starts at any point, passes through no edges repeatedly, misses no edges, and still ends up back at that node

By definition, D is wrong and the counterexample is a square

8

Which of the following conditions must be satisfied during a binary lookup of an array?

A Arrays must be ordered
B The array must be unordered
C The length of the array must be\(2\) idempotent (math.)
D The elements of an array must be integers

Dichotomous lookup is also essentially a dichotomous answer, which needs to be guaranteed to have monotonicity

9

Consider a natural number\(n\) and a number\(m\)You need to calculate\(n\) The inverse element of (i.e.\(n\) exist\(m\) sense of the multiplicative inverse element), which of the following algorithms is most appropriate?

A Trying in sequence using the violent method
B Using the Extended Euclidean Algorithm
C Use of rapid power methods
D Use of the linear sieve method

The definition of inverse element is this:

define\(a\) in mold\(p\) Inverse dollars in the sense of\(b\) fulfillment\((\frac{c}{a})\mod p=(c\times b)\mod p\)

(coll.) fail (a student)\(p\) The fast power (+ Fermat's Little Theorem) can only be used to find the inverse when it is prime, while the Extended Euclidean Algorithm is a more generalized method of finding the inverse, which only needs to satisfy the mutual prime of the two numbers

A more detailed method for finding the inverse element can be found viathis article Chapter 5.3.1 understands

10

When designing a hash table, appropriate hash functions and conflict resolution strategies need to be used in order to minimize conflicts. It is known that a hash table has\(n\) key-value pairs, the loading factor of the table is\(a(0<a\le 1)\) . In conflict resolution using the open address method, the worst case time complexity of finding an element is

A \(O(1)\)
B \(O(logn)\)
C \(O(1/(1-a))\)
D \(O(n)\)

The open-address method resolves conflicts: assume that the current element\(x\) Need to put in address\(p\) But now\(p\) Position already has an element, direct placement will lead to conflicts, so consider looking backward sequentially to find the first position that does not have an element placed in it to place, which prevents conflicts (traversing to the end and then starting again from the beginning)

Thus the worst case scenario requires traversing the entire table once, with a complexity of\(O(n)\)

Cope loading factor definition: loading factor defines a threshold, when the number of entries in the hash table exceeds the product of the loading factor and the current capacity, then the hash table should be expanded, rehash operation (i.e., rebuild the internal data structure), after the expansion of the hash table will have twice the original capacity.

11

Suppose there is a tree\(h\) Layered complete binary tree which contains at most how many nodes?

A \(2^h-1\)
B \(2^{h+1}-1\)
C \(2^h\)
D \(2^{h+1}\)

Since each node has two sons, each layer has twice as many nodes as the previous layer

Summarize points as\(1+2^{1}+2^{2}+\cdots+2^{h-1}=2^{h}-1\)

12

There is a\(10\) A complete graph of two vertices with an edge between every two vertices. How many graphs of length\(4\) The ring?

A \(120\)
B \(210\)
C \(630\)
D \(5040\)

Since the graphs are completely connected, taking any four points must guarantee that they form a ring

Because the points on the ring are disordered, many people will consider computing the\(C^{4}_{10}=\frac{10\times 9\times 8\times 7}{4\times 3\times 2\times 1}=210\)However, this is wrong.

Consider what went wrong.

Earlier we said that taking any four points must guarantee that they form a ring

But the ring1 2 3 4 homocyclic (chemistry)2 1 3 4 is not the same ring; the former has1->2->3 of the connecting edges, the latter having2->1->3 The connecting edges of the ring are clearly not the same ring

The correct approach is to consider repeated rings:

perceive1 2 3 4 2 3 4 1 3 4 1 2 4 1 2 3 is duplicated, and so on, with four possible starting nodes for each possible combination, thus duplicating the computation of the\(4\) substandard

Further, noting that1 2 3 4 4 3 2 1 are duplicates, and similarly, each of the above inverses is the same as the original, so the answer is\(\frac{A^{4}_{10}}{2\times 4}=630\)

13

For an integer\(n\). Definitions\(f(n)\) because of\(n\) The sum of the digits of each of the Ask what makes\(f(f(x))=10\) least natural number\(x\) How much is it?

A \(29\)
B \(199\)
C \(299\)
D \(399\)

Substitution of options is sufficient

\(f(29)=11,f(f(29))=2\)

\(f(199)=19,f(f(199))=10\)

\(f(299)=20,f(f(299))=2\)

\(f(399)=21,f(f(399))=3\)

14

There is a length of\(n\) The string of 01 with the\(k\) classifier for individual things or people, general, catch-all classifier\(1\) , two neighboring characters can be exchanged per operation. In the worst-case scenario placing this\(k\) classifier for individual things or people, general, catch-all classifier\(1\) What is the number of swaps required to move to the rightmost side of the string?

A \(k\)
B \(\frac{k\times (k-1)}{2}\)
C \((n-k)\times k\)
D \(\frac{(2n-k-1)\times k}{2}\)

D The source of this number: make all the numbers line up on the far left, then move them one by one from right to left, and then think the answer is\((n-1)+(n-2)+(n-3)\cdots+(n-k)\)

In fact, when lining up the later numbers, since there are already lined up numbers on the right, there is no need to compare and exchange the new numbers with the lined up numbers, so the number of exchanges for each number is only\((n-k)\) times, total\(k(n-k)\) substandard

15

As shown in the figure is a sheet containing\(7\) A directed graph of vertices, if some of the edges are to be divided so that the edges from node\(1\) go to node\(7\) There is no feasible path and the minimum number of edges to delete, how many total sets of feasible deletion edges are there?

A \(1\)
B \(2\)
C \(3\)
D \(4\)

A picture that could have been uglier

Come up here and notice first.\(\{8,9\}\) is legal and there is no solution that deletes only one edge, so the optimal solution is\(2\)

The set of feasible edges

\(\{8,9\}\)
\(\{5,6\}\)
\(\{6,8\}\)
\(\{1,6\}\)

Reader

1

analyze

The bitwise operations within the logic() function are determined using an enumeration of the

(coll.) fail (a student)\(x=0,y=0\) when(0 & 0) ^ ((0 ^ 0) | (~0 & 0))=0 ^ (0 | 0)=0
(coll.) fail (a student)\(x=0,y=1\) when(0 & 1) ^ ((0 ^ 1) | (~0 & 1))=0 ^ (1 | 1)=1
(coll.) fail (a student)\(x=1,y=0\) when(1 & 0) ^ ((1 ^ 0) | (~1 & 0))=0 ^ (1 | 0)=1
(coll.) fail (a student)\(x=1,y=1\) when(1 & 1) ^ ((1 ^ 1) | (~1 & 1))=1 ^ (0 | 0)=1

Therefore, it is a logical or operation

Observe that the recursion() function is very much like the quick sort algorithm, but with a maximum recursion depth limit, and will only do at mostdepth Layer recursion, soThe results of this sorting algorithm are not necessarily ordered

Because the quick sort will only perform at most\(\log n\) layer, so when the\(d\ge \log b\) When the output sequence is ordered

title

(coll.) fail (a student)\(1000\ge d\ge b\) When the output sequence is ordered

\(d\ge b\ge \log b\)Correct.

When inputting the5 5 1 When the output is1 1 5 5 5

A brute force simulation reveals that the initial array of5 5 1 1 5, the sort function only goes one level, the sort is incomplete, and the output value is5 1 1 5 5

Suppose the arrayc The length is unbounded and the time complexity of the algorithm implemented in this program is\(O(b)\) (used form a nominal expression)

This sorting algorithm spends at each level\(O(b)\) traverses the array once, however the algorithm has a total of\(d\) layers, so the complexity is\(O(bd)\)

function (math.)int logic(int x,int y) The function of the

By bit or, see above for details

When the input is10 100 100 When the output of the first\(100\) lit. the number of individuals is

\(d\ge \log b\)The output array is ordered, i.e., let's ask for a maximal number

Try substituting options to determine which number can be passed\(0\) until (a time)\(99\) inner numbers\(i\) pass (a bill or inspection etc)(a|i)%(b+1) Get that can be found\(98\) Illegal (non-existent)\(a\) hit the nail on the head\(1\) (the binary bits of the\(95\) lawful, and therefore for\(95\)

In detail, in the binary sensea=1010but (not)98=1100010, it is clear that if a number isa|i form, then the fourth place must be\(1\), similarly.98+101=11000111 Also not legal (need to consider this because(98+101)%101=98), and therefore\(98\) unlawful

2

analyze

Observe the dp part of the solve() function

discoveriesint k = (j<<1)|(s[i]-'0') This sentence, in fact, is the equivalent of the\(j\) and then splicing another number after it, and then updating the spliced number with the number before the splice, since all the numbers on the splice ares[i] The contents of thei is a positive-order traversal with initial state\(0\), then we find that this dp array has been trying to splice the new characters in s after the existing ones, and that such splicing is ordered so that only the later characters can be spliced after the earlier ones, and combining these three conditions we can summarize:This dp array is used in the statisticss The number of subsequence programs of

But there are limits to this number of scenarios, and we describe some of these limits below.

Noting that only the\([0,2^{m-1}-1]\) The only numbers that can be used to update the answer are those within the binary, which corresponds to all numbers not larger than\(m\) A binary number of bits, so thats greater than\(m\) Subsequent sequences of bits are not counted
An additional limitation is thatif(j !=0 || s[i]=='1')This is the biggest difference between this function and solve2(), which means that when a subsequence starts with\(0\) The time, due to thej=0,k=0and therefore cannot be updated, i.e.This function requires that the subsequence begin with a\(1\)

The function then counts alli*dp[i] value, value*number of programs=sum

Based on the above conditions, we can summarize the function:Find s all in terms of\(1\) beginning with, no more than\(m\) The sum of the decimal values of the subsequences of the bit

Let's look at solve2(), which enumerates all of the\([0,2^{n}-1]\) of all cases, converted to binary that is, all no more than\(n\) bits of the binary number, and subsequently, if the binary bits of the\(1\)If you have a character in this bit, you splice the s in this bit to the end of an existing character (num = num * 2 + (s[j]-'0') sentence), you can see that solve2() is also looking for subsequence values, so let's talk about the limitations of solve2()

Notice that although we enumerate all possible cases, only thecnt<=m number in order to update the answer, which means that at most the final subsequence can be spliced with the\(m\) number of individuals

That is to say this function functions as:Find s all up to\(m\) The sum of the decimal values of the subsequences of the bit

It can be noticed that the difference between the two lies in whether or not to take the\(1\) beginning

title

Suppose the arraydp The length is unbounded and the time complexity of the algorithm implemented by the function solve() is\(O(n2^{m})\)

The core algorithm and complexity bottleneck of the solve() function is two layersfor loop, based on the solve() function'sfor loop boundaries, one can derive its complexity as\(T(n2^{m-1})\)namely\(O(n2^{m})\)(Equivalent to multiplying by a constant\(2\)）

importation11 2 10000000001 When the program outputs two numbers32 cap (a poem)23

For solve2()

\(m=1\) Time: 11 numbers, with a contribution of\(2\times 1+9\times 0=2\)

\(m=2\) Hours:10 there are\(9\) Species.01 there are\(9\) Species.11 there are\(1\) species, contributing to\(2\times 9+1\times 9+3=30\)

total contribution\(2+30=32\)

For solve()

\(m=1\) Time: 11 numbers, with a contribution of\(2\times 1+9\times 0=2\)

\(m=2\) Hours:10 there are\(9\) Species.01 there are\(0\) species (not legal).11 there are\(1\) species, contributing to\(2\times 9+1\times 0+3=21\)

total contribution\(2+21=23\)

The biggest pitfall in this question is that solve2() comes before the actual output.

(coll.) fail (a student)\(n\le 10\) The return value of solve() will always be less than the value of\(4^{10}\)

It can be found that its subsequences contribute up to\(\sum^{10}_{i=1}C^{i}_{10}\times (2^{i}-1)\) (The approach here is not what is needed for this question; if you want to know why this equation is the case, go to the following "when the\(n\le 6\) The maximum possible return value of solve() is " go find that question".)

But on the exam it is clear that we are not good at counting such large numbers, because all the subsequences we find are smaller than\(1111111111\)And we have a total of\(2^{10}\) numbers, and each of them will be no more than\(2^{10}\)and therefore must be less than\(2^{10}\times 2^{10}=2^{20}=4^{10}\), and is therefore correct, which is why the questioner set this number to\(4^{10}\) intention

(coll.) fail (a student)\(n=10\) both (... and...)\(m=10\) How many inputs make the results of the two rows exactly the same when

According to the analysis just presented, there can be no reason to\(0\) at the beginning andmarketablesubsequences, that is, whenever a sequence of\(0\), it must be ensured that none of the numbers that follow have a value, i.e., they are all\(0\)

It's easy to see.0000000000，1000000000，1100000000，1110000000，1111000000，1111100000，1111110000，1111111000，1111111100，1111111110，1111111111 All meet the requirements for a total of\(11\) kind

(coll.) fail (a student)\(n\le 6\) The maximum possible return value for solve() is

Consider the limiting case, i.e.\(111111\)and\(m\ge n\), at which point each bit contributes maximally to the answer, i.e., the answer is also maximized, then the number of bits is\(1\) There are a total of subsequences of\(C^{1}_{6}\) individuals, and because every one of them is for the\(1\), so the value of each is\(1\)and, by the same token, the digits are\(2\) There are a total of subsequences of\(C^{2}_{6}\) each of which has a value of\(3\), and so on, it can be found that its subsequence contribution is at most\(\sum^{6}_{i=1}C^{i}_{6}\times (2^{i}-1)=665\) classifier for individual things or people, general, catch-all classifier

as\(n=8,m=8\)The maximum possible difference between the return values of solve and solve2 is

It's the exact opposite of the question above that had the exact same result, and in this question we need a question that ends in\(0\) The sequence that begins with the subsequence that has the largest value, then it's easy to think that the beginning of this sequence must be\(0\), in order to maximize the value of the latter, we construct the01111111 Such a sequence as the answer

The question asks us to compute the difference, which is actually the difference in terms of the\(0\) The sum of the subsequence weights at the beginning of the sequence, removing the beginning of the\(0\), which is also equivalent to finding\(n=7,m=7\) hour1111111 of the subsequence weights of the sum, and going back to that earlier question, the answer is\(\sum^{7}_{i=1}C^{i}_{7}\times (2^{i}-1)=2059\) classifier for individual things or people, general, catch-all classifier

3

analyze

firstly, let's look at\(p\) array, which can be found to be used in the Echidna sieve (localized code within the init() function), and finally sieve out the\(p_{i}=1\) then\(i\) prime number

Then observe the variableconst P1,P2,B1,B2,K1,K2

included among theseP1,P2 is used to take the modulus, and these last two sets of variables, one set is used to give theH initial values, and another set is used to generate thep1,p2 array (in the main function) and found that the format is similar tolinear congruence (math.), the judgment acts to generate random numbers, i.e., thep1,p2,H The starting values of all three variables are randomized, presumably by a hashing algorithm

For this hash structureH, we can observe these points as follows:

H Addition of definitions(math.) the law of exchange is not satisfied
H There are two hash parameters inh1,h2The other parameterl Record the number of merges and also participate in the operation

The multiple choice question below asks us.H of what the merge looks like, and the options listed later are all tree operations, from which it is hypothesized that the algorithm istree hash (computing)The initial value of a node is determined by whether the node number is prime or not, and the final hash value of a node is determined by the combination of its initial value, left subtree value, and right subtree value.When the subtree corresponding to two nodes (here, the subtree structure and the nodes in the subtree of thep The hash values of these two nodes are equal when (the array states) are identical

The program then performs sorting and de-duplication, which is outside the scope of the tree hash algorithm, the usefulness of which is shown in the following topic

title

Assuming that the program can automatically set themaxn change inton+1, the time complexity of the implemented algorithm is\(O(n\log n)\)

The total complexity is sifting + sorting + de-duplication =\(T(n\log\log n+n\log n+n)=O(n\log n)\)

The bottleneck in time complexity is in init().

init(): \(T(n+n\log\log n)\)

solve(): \(T(2n+n\log n)\)

Obviously solve() is bigger.

If the constant is modifiedB1 maybeK1 values, the program may output different results!

The first line of the program outputs the hash value, and although modifying the parameters inside the hash does not affect the hash judgment (regardless of hash conflicts), it still results in a change in the hash value, and therefore correctly

In the solve() function, theh[] The order of merging can be seen as

\(2i\) is the left subtree.\(i\) It's current.\(2i+1\) is a right subtree, thenh[i]=h[2*i]+h[i]+h[2*i+1] denotes left-center-right, i.e., middle-order traversal.

importation\(10\)The first line of the output is

Violently simulating a hash passes this question

But there is clearly a better solution, considering that this hash is expanded each time by multiplying the\(2^{l}\), plus a new hash value, which is a very nice property if we think of the hash value of a particular bit as a\(m\) bit binary number, such a merge would tell us that the binary number corresponding to the\(l\) must be equal to\(m\), because the initial state for\(l=1\) of the node, the value of which happens to be\(1\), so each time it is merged, it will be exactly the right and left sides of the\(h1\) values are stitched together to form a new binary number

We can therefore directly utilize this property for\(n=10\) A mid-order traversal of a complete binary tree of the type8 4 9 2 10 5 1 6 3 7 to a binary number (if the bit number is prime it is\(1\)otherwise\(0\)For details, seeH constructor), i.e.\(0001010011_{d}=83\)

importation16The second line of the output is

I.e., I asked:\(n=16\) When the subtree hashes are different, there are several nodes with different subtree hashes (different hashes are defined above, i.e., the subtree structure or the nodes in the subtree of thep different array states exist)

can be found9 10 12 14 15 16 It's the same.11 13 It's the same. The rest are different.

thus providing\(16-(6-1)-(2-1)=10\) classifier for individual things or people, general, catch-all classifier

refinement of procedures

1

analyze

upper_bound() The function has a fixed role, meaning "find the subscript of the first value in an ordered sequence that is greater than the given element", according to the following callupper_bound(b,b+n,...) It can also be noticed that the interval here is left-closed and right-open

get_rank() function is the equivalent of the check() function in Dichotomous Answers, where the purpose is to check the rank of the current sum over all sums. Here, it is written asupper_bound(b,b+n,sum-a[i])-bSuppose we fix\(a_{i}\)So what's going on in\(b\) array than in the\(sum-a_{i}\) Smaller element values with\(a_{i}\) The sum of must also be more than\(sum\) is small, so we'll just add it to the current\(sum\) before the ranking, which is the meaning of this function

solve() which is the dichotomous answer function, the dichotomous possible\(sum\) value, find the value of the rank that is exactly\(k\) The one that

The program is relatively simple, the main difficulty may be in the format of the dichotomy, if you normally use a dichotomy that is notl=mid+1,r=mid format, then it may be easy to pick the wrong

title

Choose the right endpoint of the dichotomous interval, the dichotomous range is a given array, many people will choose wronglyan-a-1, however since it is left closed and right open, it should be chosenan-a
Now we're looking for the first one to be greater than\(a_{i}\) figures, noting thatr=mid Two things should be stated, firstly that the current point is legal (otherwise it should be tuned directly to the\(mid-1\)), the second indicates that the current value is larger, and the legal indicates that it is strictly greater than the lookup value, so choose thea[mid] > ai
Returns the address of the element to look up, which is looked up here at the first\(l\) element, since the address starts at\(a+0\) Starts at the beginning and therefore returns\(a+l\)
Still picking the right endpoint of the bisection interval, since the bisection is\(sum\) values, the maximum value should be the addition of the largest element on both sides, and since the elements on both sides are monotonically non-decreasing, it is sufficient to choose the last two, noting that the last elements are\([n-1]\) fault\([n]\)
As with the second question, let's analyze that firstly the current answer is not legitimate and secondly the current answer should be ranked smaller, so we need to put the\(sum\) The value of becomes larger, and the illegality indicates that you can't take an equal, so chooseget_rank(mid) < k

2

analyze

The strict second short-circuit algorithm, i.e., finding the second short-circuit that is strictly greater than the shortest short-circuit, is first analyzed to analyze the logic of the second short-circuit algorithm:

Run the shortest circuit, record the current shortest circuit and the second short circuit respectively
If there is no current path, then the newly found path becomes the shortest path
If the newly found path is shorter than the current shortest path, then the newly found becomes the shortest path and the previous shortest path becomes the second shortest path
If the newly found path is less than the shortest path but greater than the second shortest path, then the newly found path becomes the second shortest path

In this way, we are able to find the shortest and second short circuits

The question asks for the output path, so presumablypre array is an array of recorded paths thatdis The array follows the general shortest-circuit algorithm, which records the shortest circuit from the node to the starting point, and what's strange here is that the two pointerspre2 cap (a poem)dis2, they are arrays belonging to the sub-short-circuit, you can understand that they are also independent arrays, just using thepre cap (a poem)dis room

In other words.dis[a]=(dis+n)[a-n]=dis2[a-n]，dis2[a]=(dis+n)[a]=dis[a+n]

Then look at the additive edge, the chained forward star is used and the additive edge function isadd

Analyze this belowupd function (math.)

Those who have written about the dij algorithm should be able to see that this is a slack operation, since there are pairs ofdis The comparison, assignment, and prioritization queues of thepush()and it can be seen that the function returns true after a successful relaxation, otherwise it is false, and of the function's arguments, thea is the predecessor number of the node.b is the node number.d It's the distance of the update thatp It's a priority queue.

What runs in the solve() function is a more normal dij

title

The goal here is to use the current shortest-circuitdis Go update the sub-short-circuitdisBecause of these twodis are in two different arrays, so they may not be the same, but the slack operation can only be performed if the two arrays are the same, so there needs to be some unification, so the precursor here is clearly thepre[b]The node number should ben+bBecause we're updating thedis2[b]Becausedis2=dis+nSo here's what it should ben+bThe distance is the shortest distancedis[b]
The test ispair<> the keyword question.pair<> When sorting, the first keyword will be prioritized, and when the same, the second keyword will be sorted, so here we should obviously prioritize the nodesdis instead of the node number, so it should bed comes first, and then it should bedis The small one is in front, because the priority queue puts the big one in front, so in order to realize that the small one is in front, we should insert a negative one, and just make it positive when we take it out
A lot of people would just go for a no-brainer.0x3fBecause it's easy to remember and won't blow up.int, and is large enough, but the question already defines the maximum value for usconst int infSo let's just follow theinf assign a value0x1f
This is the place where the shortest circuit has already been relaxed and failed, now it's time to try to relax the second short circuit, which, as in the second question above, is numbered asn+bBecause we haven't updated it yet.dis2So you can't use it here.dis2[a]+cIt can only be done withdis[a]+c
The above judgment statement tells us that nowa (particle used for comparison and "-er than")n is larger (and must be larger) than2n (small), so we directly tunedis2[a] would be out of bounds (but callingdis[a] (that is, it can), and to keep it from crossing the line, we should call thedis2[a-n]namelydis2[a%n]