A. Volleyball

Subtask 1,2

In the process of reading the input, we can maintain two variables sx,sy, which respectively indicate that the first team currently scored sx points, and the second team currently scored sy points. After reading a line, update the values of these two variables, and then determine whether the current round has ended

The process of judgment is as follows

1. If sx25 and sx>sy+1 , then the first team wins

2. If sy25 and sy>sx+1 , then the second team wins

3. Otherwise, the current round is not over yet

If a team wins two games, then exit the loop directly and output which team wins the overall game

B. Majhong

Subtask 1

Simply enumerate all possible decompositions.

Subtask 2

In this case, it is impossible to form a 'Chow' as there are only n different kinds of tiles. Therefore, only 'Pong' can be used. At this time, a hand of tiles is legal if and only if the number of tiles with each symbol is a multiple of x, the number of tiles required by a 'Pong'.

The time complexity of this algorithm is O(n).

Subtask 3

It's easy to see that for the smallest available tile, matching 'Pong' is always better than matching 'Chow'. So the legality of a hand can be checked by enumerating from the first tile to the nth tile.

Each time when we visit the ith tile, let m be the number of remaining tiles with the ith symbol. We first use them to form mx 'Pongs'. In order to use up the remaining tiles with the ith symbol, we have to use m mod x tiles of each synbol in range [i,i+y1] to form 'Chows'. If there are not enough tiles, the current hand must be illegal.

The time complexity of this procedure O(n2). This algorithm can be further improved to O(n) by differencing array a.

C. The 80/20 Rule

Subtask 1

Consider performing a state pressure enumeration for all n individuals, enumerating which people are selected by us, and then calculating A,B separately to determine the answer, time complexity O(2n)

Subtask 2

First we will sort the data in descending order from largest to smallest. For each prefix, we will calculate the corresponding numbers A and B . Let sum be the sum of the data, and prei to represent the sum of the data in the prefix [1,i], by enumerating i, we can get A=in, B=preisum, then find the maximum value of BA for all i. As for sorting, you can use sorting algorithms such as bubble sort, selection sort, and insertion sort to achieve a time complexity of O(n2)

Subtask 3

You can use algorithms such as merge sort, or use the built-in sort to achieve a time complexity of O(nlogn).

D. Matrix

Subtask 1,2

It is easy to find that the final result has nothing to do with the order of operations. You can enumerate whether each p is reversed, and then judge whether it is legal one by one.

Time complexity O(n22n).

Subtask 3,4

It is easy to find that Li,i must be equal to 0, and Li,j must be equal to Lj,i. Consider coloring each position by the number of operations parity:

Among them, red represents the grid on the diagonal, and the purple box on the diagonal represents (pi,pi), blue represents an odd number of operations, and purple represents an even number of operations. It can be seen that the number of the matrix A in the purple area, white area, and red area must be 0.

That is, if P={pi}, Q={x|x[1,n],xP}, then i,j inP,Ai,j=0 and i,jQ,Ai,j=0.

Consider constructing an undirected graph G=(V,E) with n points, and the edge (i,j)E if and only if Ai,j=1. It is easy to find that there is no edge in the point set corresponding to P, and there is no edge in the point set corresponding to Q. That is, G must be a bipartite graph at this time.

It is easy to prove that G is a bipartite graph is also a sufficient condition for a solution.

Assuming that the corresponding point set of P is a black point, then the construction scheme is equivalent to a black-and-white coloring scheme of the given graph, so that the lexicographical order of the black point set is as small as possible under the premise that the number of black points is as small as possible.

It is easy to prove that among the two coloring schemes for each connected block, the scheme with the smallest possible lexicographical order of the set of black points must be better on the premise of greedily taking the number of black points as small as possible.

Finally, all the black dot labels can be sorted and output.

Time complexity O(n2).

E. Sequence

Subtask 1

Output the bitwise OR of all numbers.

Subtask 2,3

We can design a dp algorithm:

Denote fi as the value and minimum value of splitting the first i into several substrings, obviously fi=min{fj1+S(j,i)}, where S(l,r) represents the value of the substring [l,r].

Brute force can do it in O(n2).

Subtask 4

Then we find a fact: for an i, there are only O(loga) different S(j,i).Because if the bitwise OR's value is changed with j increasing, there must be a bit which is changed from 0 to 1.

Then we can find k intervals [l1,r1],...,[lk,rk] for a fixed i, satisfying 1=l1r1<l2r2<...<lkrk=i , so that for each interval j[1,k] satisfies x,y[lj,rj],S(x,i)=S(y,i) , and its S is different for positions in different intervals

At the same time, for each interval, the minimum value of f in the interval can be maintained, then violently process all intervals with different S(j,i) and the minimum value of fj1, time complexity O(nloga), can pass all data.

F. Tree

Subtask 1

Simply enumerate 2n edge cutting schemes, and find the centroid for each connected block.

Complexity O(2n).

Subtask 2

For each node u, set u as the root of the whole tree and use a tree DP to calculate the probability that u is the centroid of its component. For each node v, let f[v][i] be the probability that the subtree of node u when the root is u includes exactly i nodes. Array f can be calculated in O(n2) time, and then the probability can be calculated by enumerating the number of nodes in the same connected component as node u.

The total time complexity is O(n3).

Subtask 4

The point i becomes the centroid if and only if its interval [l,r] satisfies il>ri or ri>il, the number of solutions can be directly calculated. Complexity O(n2).

Subtask 5

Let us consider the probability that the uth node is not a centroid. Node u is not a centroid if and only if there is a node v that (1) the edge between u and v is preserved, and (2) after edge (u,v) is deleted, the number of nodes belongs to the same component as node u is strictly smaller than that of node v.

Choose an arbitrary node as the root of the whole tree. Let f[u][i] be the probability that exactly ith node in the subtree of node u belonged to the connected component of node u after cutting off the edges. f can be calculated in O(n2) by a simple tree DP.

Now, for each node u, for each node v that is a neighbor of u, and for each integer k, we need to calculate the probability that when u is set as the root of the whole tree, (1) u and v belongs to the same connected component, and (2) the number of nodes in the subtree of v that belongs to the connected component of node v is larger than a half that of node u.

Such a probability can be calculated from the array g defined as the following. For node u,v where (u,v) is an edge on the tree and integer x, gu,v,x represents the probability that after setting node u as the root, the number of nodes in the component of u that are not in the subtree of node v is exactly x.

Though g can be calculated by a tree DP, a trivial algorithm costs O(n3) times. An important trick here is that gu,v,x contributes to the result only when the number of nodes belongs to both the component of u and the subtree of v is strictly larger (or strictly smaller) than x, and thus the value of gu,v,x can be merged to gu,v,size(v)+1 when xsize(v)+1.

Using this property, it can be proven that the time complexity of the tree DP is improved to O(n2).

G. Palinomial


For each query, multiply all the polynomials in the query interval violently, and directly judge whether the obtained polynomial is a palindrome polynomial. The time complexity is O(q×(ki)2).


Consider accelerating the polynomial multiplication process of Subtask 1, then divide and conquer + NTT can be solved in the time complexity of O(q×(ki)×log).


It can be found that when each position is a linear function, we can find that only the linear function that itself is a palindrome polynomial and a first-order function whose solution is the reciprocal of each other can be a palindrome polynomial. We can consider using this property to maintain the set of each primary function of this interval and the set of each primary function of the reciprocal solution by using the set hash, and check whether they are the same.


There may be two methods of this package. One is to brute force each polynomial to turn it into a function and then use the previous package to do it, which may not be particularly easy to implement.

Or it is realized by a violent method accidentally discovered by the questioner, that is, violent maintenance of several items before and after the multiplication of polynomials. After violent verification, it is correct, and it is left to the reader to prove it by myself.


When a n degree polynomial F satisfies [xi]F(x)=[xni]F(x), we can find that F(x)=xnF(1x) , that is, we actually only need to judge whether F(x) and xnF(1x) are the same.

Quickly determine whether two high-order polynomials are the same. If violence is used, it is related to the degree, and the complexity is unacceptable. We use polynomial hashing here.

Let the hash function G(F(x))=gn+1+(i=0n[xi]F(x)gi)(modp) This hash function can be easily maintained by using a segment tree, and we consider proving its correctness.

If the hash functions of two polynomials of the same degree F(x),G(x) are the same, it must satisfy i=0n([xi]F(x)[xi]G(x))gi=0(modp) We consider that when F(x) and G(x) are different, the polynomial H(x)=i=0n([xi]F(x)[xi]G(x))xi is at most a polynomial of degree n when the modulus p is a prime number, with at most n zeros. If x is taken randomly, then the probability that H(x) is 0 is np . The probability that two polynomials are different but the hash function is the same is np .

So we set p to be a prime number at the level of 109, the probability of a single query success is 1np, and the probability of q success is (1np)q is about 0.00004 , so a single hash cannot meet our requirements, a double hash is needed, and the probability of successful q times is (1(np)2)q , about 0.999 .

So far, the problem can be solved within the complexity of O(qlogn)

H. Virus Experiment

Subtask 1

Violence takes out the chain of each query, and then simulates it.

Time complexity O(qn2).

Subtask 2

The brute force takes out the chain of each query, and uses the hash to determine whether each prefix is a palindrome.

Time complexity O(qn).

Subtask 3

This part is mainly divided into various root sign practices and practices with larger constants.

One root approach is to use a tree-move and then use a two-way PAM to solve. Time complexity O(nq|Σ|), where |Σ| represents the character set size.

Subtask 4

Consider making all queries off-line, sorted by left endpoint position. PAM(Palindrome tree) is used to maintain the palindrome tree and the depth of each node during the scan from right to left. For each query, use tree multiplication to find the node corresponding to the first palindrome prefix, and its depth on the palindrome tree is the answer.

Time complexity O(qlogn).

Subtask 5

First make all queries off-line, and then divide and conquer. For each node, the center processes all queries that pass through the node in its connected block.

For the query u,v, let the subtree where u is located be L, and the subtree where v is located be R, and discuss according to the position of the palindrome:

Case 1

The red line segment is the palindrome prefix position, and the blue line is the palindrome center.

Let Su denote the string from root to u.

The entire palindrome is in L, which is equivalent to the number of suffixed palindrome substrings of Su. You can pass dfs and maintain revocable PAM statistics, where the number of suffixed palindrome substrings is the depth of the node in the fail tree of PAM.

The total complexity of this part is O(n|Σ|logn).

Case 2

The palindrome reaches the R subtree passing the root, and the center of the palindrome remains in the L subtree.

According to the properties of the palindrome, the string can be divided into three parts x,s,x. where x is the prefix of Su and x is the suffix of Sv. Satisfy s is a palindrome and x=x.

Lemma 1: If s and s+t are both palindromes, then s+t+t must be a palindrome.

Lemma 2: All palindromic prefixes of a string can be divided into O(logn) arithmetic progressions.

We use Lemma 2 to decompose Su into a palindrome prefix. For each arithmetic sequence, it is expressed in the form of s=si+aij,j[0,bi]. (si represents the string formed by repeating the string s by i, and s+t represents the string formed by splicing the strings s and t before and after.)

Consider the case of s=s0+aj,j[0,b], at this time Su is divided into s0+aj+y, we might as well decompose Sv into ak+y+z form, where |y|=|y|:

x must be represented as ai+y,ib. According to Lemma 1, a cannot be a prefix of y and y. At this time if:

For palindrome decomposition, PAM of Case 1 can be used to find the deepest ancestor that does not satisfy the arithmetic progression for each node. For computing the decomposition of Sv, you can maintain a hash of a2i and then multiply the computation.

The total complexity of this part is O(qlog2n).

Case 3

The palindrome is centered in the R subtree. Similar to Case 2, we decompose the palindrome into x,s,x, at this time x=x.

Similarly, we decompose s into the form of s0+ai,ib, and decompose Su into the form of y+ai, and down |yfroms| takes out y.

Similarly, categorize whether y is a prefix of a, and if not, check for unique x. Otherwise the result is the difference between the feasible powers of the two sides.

The complexity of this part is O(qlog2n).

Total complexity O(n|Σ|logn+qlog2n).