Obviously if (r, c) is originally black, then output 0. Output 1 if row r or column c is black. Output 2 if black is present. If not even black, output -1.

Java

C++

Obviously Rahul will choose the middle seat as much as possible, and Tina will hide in the 4 corners as much as possible. And when the middle position is painted pink, then Rahul will choose the position closest to the 4 corners (the maximum distance from the 4 corners).

So we calculate the distance from each point to the 4 corners, and then sort and output.

Java

C++

Obviously, the edge weight of each edge must be a prime number, and there must be exactly one edge between two adjacent edges whose edge weight is 2. Therefore, there is a solution if and only if the tree is actually a chain.

Therefore, it is only need to verify whether the tree is a chain, and then fill in 2 and 3 in turn.

Java

C++

For a certain number X, if the GCD of all multiples of X in the final array is X, then X must be in the final array also.

Because if these numbers are multiples of X, there are only two possibilities for their GCD: 1. equal to X; 2. greater than X.

For the case greater than X, we give an example to illustrate. [8, 12, 13]. When X is 2, we find that the GCD is 4. Then it means that 4 should also be in the final result array. But not 2.

So we enumerate each number in order from large to small, and check it as above.

Java

C++

Clearly a DP problem. It's just that the code implementation is slightly cumbersome.

Since k is at most $10^5$, there are actually only at most $2\cdot 10^5 + 2$ points (include the start and end points) that have an impact.

So we can build a map based on these points, and then DP on the map.

We let DP[i][j] denote the minimum cost for the i-th floor to walk to the j-th room.

Obviously, if we know the final cost of floor a, we can update the value of DP[c][d] with DP[a][b] according to the situation of the ladder.

But at this time the value of DP[c][d] is not the final cost, because it is possible to go from DP[c][e] to DP[c][d] to obtain a smaller cost. So,$$\text{DP[c][d]} =

\begin{cases}

\text{dp[c][e]}+\text{x[c]}\cdot|d-e|, & d > e\\

\text{dp[c][e]}+\text{x[c]}\cdot|e-d|, & e > d

\end{cases}$$Therefore, we only need to traverse from left to right and from right to left twice to get the final value of DP[c][d].

In the end we just need to output the value of the end point.

Java

C++

]]>Count the number of Xs where each bit is 1. If a bit has more than half of 1's, then y is 1 in that bit, otherwise it's 0.

Java

C++

For any two identical numbers, at least, we can find l and r of length 1. Also quite naturally, we would want to extend the lengths of l and r.

Obviously, if the expansion to the right, the number on the right has more restriction; if it is expanded to the left, the number on the left has more restriction.

Therefore, two adjacent numbers that are the same must end up being longer than two non-adjacent numbers.

Therefore, we only need to record the position of the last occurrence of each number, so that the maximum length corresponding to the current number can be quickly calculated each time.

Java

C++

Obviously a DP problem.

dp[i][j] represents the minimum time required to reach the i-th road sign when j road signs are removed.

By definition, obviously dp[0][j]=0. It should be noted that here I also defined dp[0][2]=0, that is to say: the quota for deleting road signs is allowed to be wasted.

Then for i not equal to 0, dp[i][i - 1 - j + x]=min{dp[j][x]+a[j]*(d[i]-d[j])}.

That is, consider the minimum time to reach the i-th road sign and there are no other road signs from j to i. Obviously it takes a[j]*(d[i]-d[j]) time to get from j to i.

Among them, it is assumed that x road signs have been deleted when reaching j. Then at this time, plus deleting all road signs between i and j, a total of x+i-1-j road signs are deleted.

Finally, find the minimum value of dp[n+1].

Java

C++

]]>Obviously, output the maximum value minus the minimum value.

Java

C++

Just try to operate on each number in turn. As long as a feasible solution is found, then output YES.

Java

C++

For x from 0 to n, We count which a[i] can generate it.

So we find the x with the least possible i from 0 to n each time, and randomly find one of the i and perform several operations on it to get x.

If the process finds that an x has no optional i, output No.

Java

C++

Obviously, as long as there is only one letter in a string that appears an odd number of times, and all other letters appear an even number of times, then this string must be able to get a palindrome by adjusting the order.

Then we only need to count how many pairs of letters, such as aa, bb, cc. And these letter pairs are evenly distributed to k strings.

In the last remaining, we pick at most k letters, and they can be added to k strings as the only odd number of letters.

Java

C++

A good Trie and DP problem.

We binary search the initial value of x. We can find that for the median mid of all possible values of x, we give c such that mid+c is exactly divisible by n.

If x is on the left of mid, then $\lfloor\frac{x+c}{n}\rfloor<\lfloor\frac{mid+c}{n}\rfloor$. Otherwise $\lfloor\frac{x+c}{n}\rfloor=\lfloor\frac{mid+c}{n}\rfloor$.

The only trouble is to record each time c, and calculate the c for the current mid.

Java

C++

First, we first find the highest 1 of the final result. So add edges by the number of bits until all the nodes are being connected together.

The answer we assume at this point is a binary number with all 1s, like 111111. (Perhaps the OR of all sides less than 6 bits is not 111111, but we can ignore that for later practice.)

At this time, the highest bit 1 cannot become 0, because if this bit can be 0, it means that 5 bits are enough. If we must replace the highest bit with 0, then the higher-order edge is needed to supplement, and the value of such OR is larger.

So we start from the second highest bit, and try to change each bit to 0 in turn, and see whether it can still form a tree. That is, we try 101111 first, then 1?0111, where ? depends on the result of the first attempt.

This is done because, obviously, we want to have 0 as higher bits as possible. Therefore, when discussing whether a certain bit can be 0, the lower bits must be all 1 (to form a tree as much as possible).

Java

C++

]]>Trie + DP。

First, any number greater than 3 can be represented as the sum of 2s and 3s. So we have each of our segments of length either 2 or 3.

Then for the original n phone numbers, we add all substrings of length 2 and length 3 into the dictionary tree to be checked. The Trie will record the index and position of this substring.

Next is the DP part. dp[i] represents the solution for the first i digits. The slightly unusual thing here is that dp[i] is not a number, but an object. If dp[i]=null there is no solution.

So there are two choices for the value of dp[i]: 1. If dp[i-2] is not empty, and the letters i-1 and i can be found in the Trie, then the value of dp[i] is the Trie recorded value. 2. Similarly, we consider 3 letters to look up in the Trie, and check the value of dp[i-3]. If neither works, then dp[i] is empty.

So we only need to calculate the information of each segment from m to 1 according to the records of the Trie and DP.

Java

C++

]]>Just simulate the behavior of the robot according to the requirements of the problem.

Java

C++

First, use a map<int, set> to record all the ranges, where L is the key of the map, and R is recorded in the set. Then for each range, we enumerate D to see if [L, D-1] and [D+1, R] have appeared.

Java

C++

Binary search final result.

Then check from the n-th heap to the 3rd heap in turn.

For the i-th heap currently under inspection, we divide the stones into two categories: 1. Originally belonging to h[i], this category can be assigned to i-1 and i-2; 2. The stones that come from i+1 and i+ 2, I record as buff[i].

If the sum of h[i]+buff[i] is not enough to satisfy the result, then the result must be too large. Otherwise we can divide h[i] into i-1 and i-2 as much as possible.

Java

C++

Question D is pure mathematics, which is a pure infinite series summation. It's too boring. After all, it's almost Chinese new year, so I'm too lazy to do it.

]]>First, see whether the length of the string can be divisible by 2, and then verify whether the first half and the second half are the same.

Java

C++

Preprocess all these numbers in the beginning. After that, putting it in the map or using binary search can solve this problem.

Java

C++

Simulate from right to left. If the S of a certain bit is greater than or equal to A, the A+B of this bit must not be greater than or equal to 10. On the contrary, the S of the previous digit and the S of this digit must be equal to A+B.

If it is found during the process that it cannot be constructed, then it cannot be constructed.

Java

C++

Binary search the final result. If this result is ok, then the following conditions must be met:

- Everyone can find at least one store, making that person's satisfaction at that store higher than the current results.
- At least one store exists so that this store can satisfy at least two people at the same time.

Java

C++

First, we count the number of occurrences of each number, denoted as count.

For the ith number, obviously we need to at least change all count[i] to i+1.

Then we add the number of steps are needed to have values from 0 to i-1.

Obviously, in order to have values from 0 to i-1, the operation that needs to be operated must be: a certain count[j]=0 (j<i-1). At this time, find the nearest k from j to the left so that count[k]>1.

So we use a list to maintain all count[k]>1, and whenever we find count[j]=0, just take one from the list and fill it up.

Therefore, we can update this list by the way after calculating the current i, and calculate the minimum cost in advance so that 0 to i have values.

Java

C++

Just take turns assigning people each time.

Taking m=3 and n=8 as an example, we make the following arrangements:

Java

C++

First, through DSU, we linked all the mines that would explode together.

So we sort all connected blocks. Then simulate second by second until all connected blocks explode.

Java

C++

There is also a question H, at a glance it is 2400, and then it seems to be more troublesome. After all, it's New Year's Eve, so be lazy.

]]>You can sort the strings directly, that is, you can directly output the string in the form of aaaabbbbccccdefg.

However, if t is "abc", and there are both a, b, and c in s, output a string of the form aaaacccbbbdefg.

Java

C++

If c=1, then the problem is transformed into dividing n-1 into a and b so that a and b are relatively prime.

Then we assume that a is a prime number, then (n-1-a)% a != 0. Obviously, as long as (n-1)% a! = 0, then (n-1-a)% a! = 0.

The problem then turns to find a prime number a such that a is not a factor of n-1.

So obviously a is 29 at most, because if all prime numbers below 29 are divisible by n-1, then n-1 is at least 2*3*5*...*23.

Therefore, only need to enumerate a.

Java

C++

First of all, if a certain a[i] itself is between 1 and n, then we prefer not to change this value.

For other values, we consider from small to large, and each time we see if it can be used to fill in the smallest and unfilled numbers.

Java

C++

We inquire 3 people each time. That is, the first query 1, 2, 3; the second query 4, 5, 6. **This requires $\frac 1 3 n$ queries.**

On this basis, if we know the specific location of a certain impostor and crewmate, then for a certain 3 people above, we only need 2 queries to get the identity of each person inside.

Take the query result of 1, 2, and 3 as 0, and we know that 8 is impostor and 9 is crewmate as an example.

Obviously, there is at most 1 crewmate among the two people 1, 2, then if we query 1, 2, and 9 are 0, then 1 and 2 must be impostor. Similarly, if 2, 3, and 9 are 0, then 2 and 3 are both impostor.

But if 1, 2, 9 are 1, it means that there is one and only one crewmate between 1 and 2. If 2, 3, and 9 are also 1, then 2 must be crewmate. Otherwise, 1 must be crewmate.

Conversely, if the query result of 4, 5, 6 is 1, then we use 8 to test.**This process requires $\frac 2 3 n$ queries.**

Now, our problem is how to find out the specific location of a pair of impostor and crewmate.

First, if the query result of 1, 2, 3 is 0, and the query result of 2, 3, 4 is 1. Then there is one and only one impostor in 2 and 3. At the same time, 1 must be impostor, and 4 must be crewmate.

Therefore, if the results of the first round of queries are not all the same, we must be able to get the above situation through two additional queries.

For example, the result of 1, 2, 3 is 0, and the result of 7, 8, 9 is 1. Then we query 2, 3, 7 and 3, 7, 8, and these 4 queries must have the above situation.**This situation requires 2 queries.**

If the results of the query are all the same, and there are at least $\frac 1 3 n$ of impostor or crewmate. Then out of every three people, exactly one person is different from the result.

For example, that the results of the first round are all 0. If 1 is a crewmate, then at least one of the results of queries 1, 4, 5 and 1, 5, 6 should be 1. Otherwise, 1 must be impostor.

If we try 1 and 2 and find that both are impostor, then 3 must be the crewmate.**This situation requires up to 4 queries.**

So in summary, we need at most n+4 queries.

Java

C++

]]>We assume a[1]<a[2]<a[3]. So naturally b[7]=a[1]+a[2]+a[3], b[6]=a[2]+a[3], b[5]=a[1]+a[3].

So a[1]=b[7]-b[6], a[3]=b[5]-a[1]. Finally a[2]=b[7]-a[1]-a[3].

Java

C++

If the first character of the current string is equal to the last character of the previous string, then continue. If unequal is found, then a string must be missed here, just add it.

If the whole process is always equal, just add a character at the end.

Java

C++

Obviously this d is either the greatest common divisor of all odd digits or the greatest common divisor of all even digits. And this d must not divide any remaining number.

Java

C++

Obviously, we can perform the operation with as large a number as possible, and make the result of each operation to be 0 as much as possible.

Java

C++

This is a problem of solving a linear equation (take n=5 as an example):$$\begin{cases}

1\cdot a_1 + 5\cdot a_2 + 4\cdot a_3 + 3\cdot a_4 + 2\cdot a_5=b_1 \\

2\cdot a_1 + 1\cdot a_2 + 5\cdot a_3 + 4\cdot a_4 + 3\cdot a_5=b_2 \\

3\cdot a_1 + 2\cdot a_2 + 1\cdot a_3 + 5\cdot a_4 + 4\cdot a_5=b_3 \\

4\cdot a_1 + 3\cdot a_2 + 2\cdot a_3 + 1\cdot a_4 + 5\cdot a_5=b_4 \\

5\cdot a_1 + 4\cdot a_2 + 3\cdot a_3 + 2\cdot a_4 + 1\cdot a_5=b_5 \\

\end{cases}$$

So, $15\cdot a_1 + 15\cdot a_2 + 15\cdot a_3 + 15\cdot a_4 + 15\cdot a_5=b_1+b_2+b_3+b_4+b_5$. And so, $a_1+a_2+a_3+a_4+a_5=\frac {b_1+b_2+b_3+b_4+b_5} {15}$。

We let $sum=\frac {b_1+b_2+b_3+b_4+b_5} {15}$

So that $$\begin{cases}

4\cdot a_2 + 3\cdot a_3 + 2\cdot a_4 + 1\cdot a_5=b_1-1\cdot sum \\

-1\cdot a_2 + 3\cdot a_3 + 2\cdot a_4 + 1\cdot a_5=b_2-2\cdot sum \\

-1\cdot a_2 + -2\cdot a_3 + 2\cdot a_4 + 1\cdot a_5=b_3-3\cdot sum \\

-1\cdot a_2 + -2\cdot a_3 + -3\cdot a_4 + 1\cdot a_5=b_4-4\cdot sum \\

-1\cdot a_2 + -2\cdot a_3 + -3\cdot a_4 + -4\cdot a_5=b_5-5\cdot sum \\

\end{cases}$$

We found that in the above formula, two adjacent expressions can find a value of a (not including $a_1$).

Finally, we can calculate $a_1$ based on other $a_i$.

During this process, we need to verify several points: 1. sum should be an integer; 2. $a_i$ cannot exceed the range; 3. $a_1$ must be calculated twice to ensure that there is a solution.

Regardless of the value of sum or the value of a, the solution process is $O(n)$.

Java

C++

Direct brute force search is enough. Because it is not difficult to find that adding 0 to the right is actually very difficult. In fact, adding 0 is difficult. Because 0 is added to the right and reversed, 0 will disappear. So the value that may appear is actually very limited, so direct brute force search is enough.

It is recommended to refer to the Java code. C++ has some optimizations due to the stack issue in the DFS process, which reduces the readability.

Java

C++

This is a very good problem of Disjoint-set and offline processing.

]]>First, we can directly consider all items together.

Let's consider the following example (I modified it a little bit based on the sample data):

We consider the result after several exchanges when k=2:

We carefully observe the above example, we noticed: 10-15 is a continuous interval, because the difference between 15 and 18 is 3, and the difference between all items between 10-15 does not exceed k.

In the end, the red letters must be arranged in order from right to left.

Similarly, 18 itself is a interval, and 30-31 is a interval.

Now we try to change k from 2 to 3. Naturally, now the entire 10-18 will be a continuous whole interval. So it is natural:

Therefore, the solution is more obvious:

- First, we process all queries offline. We will process k from small to large in order.
- As k increases, we use Disjoint-set to maintain the interval.
- For each interval, we record the index of the rightmost point and the number of items in the interval.
- Finally, we maintain a prefix sum so that we can quickly calculate the impact on the final total value when we merge the two intervals.

Java

C++

]]>Just simulate according to the description of the problem.

Java

C++

Obviously, when the maximum value is at the right end of the array, the array no longer changes.

After each operation, the rightmost value will become the first number from right to left that is greater than the current rightmost value.

Therefore, we only need to find out how many operations have passed before the rightmost value becomes the maximum value of the array.

Java

C++

Obviously, except to the last delivery, each delivery will need to return to the origin. Therefore, the last delivery should be as far as possible.

At the same time, delivery to the furthest place should be as full as possible.

Therefore, we take the goods back and forth from far to near, and finally we subtract the distance of the last return with the goods.

Java

C++

First of all, if there are duplicate numbers, then we can achieve the interchange position of the two numbers by adding two identical numbers and a different number. Therefore, if there are the same numbers, it must be YES.

And for the case where there is no repeated number. We can observe that after each operation, the number of reversed pairs of the array will only change by 2. For example, [1,2,3,4,5], after we perform operations on 2,3,4, it becomes [1,4,2,3,5], and the number of reverse pairs has changed from 0 to 2.

Therefore, we only need to use the segment tree to maintain the number of reverse-order pairs. If the number is even, then YES, otherwise NO.

Java

C++

]]>Obviously, when x>0, x cannot be divisible by x+1. Therefore, we can set a[i]=a[i-1]+1.

Java

C++

First, the difference between a and b cannot exceed 1. From the figure below, we can see that to link two "a" (blue), there must be a "b" (red):

The structure is shown in the figure below:

Java

C++

First of all, if someone has the greatest strength in a certain picture, then he must be able to win.

And if one person may win, then if another person can defeat this person on a certain picture, then the other person also may win.

So we can use recursion directly.

Java

C++

The key to this problem is to find that WB and BW can be placed anywhere in most cases.

]]>First of all, we need to notice that after the domino is painted, there are actually only 4 states: BW, WB, WW, BB.

So we naturally began to think about how to construct an valid painting method. It is not difficult to find that the final construction must be like this: BB, WB, WB, …, WB, WW, BW, BW, …, BW, BB, WW, BB, WW.

In other words: 1. As long as BB and WW exist, then WB and BW actually have no effect on the structure. 2. The number of BB must be the same as the number of WW.

Of course, one exception is the absence of BB and WW. In this case, either all WB or all BW.

So, obviously, the number of letter B and the number of letter W must be the same. (Because the numbers of BB and WW are equal, and WB and BW do not affect the number of B and W)

And this conclusion is almost the same in reverse: when the number of letter B and letter W are the same, this coloring must be valid. Because when the numbers are the same, excluding WB and BW, the number of the remaining letter B is still the same as the number of letter W, so the number of remaining BB and WW must be the same.

So the number of coloring methods is: $C_{2n-\text{count('W')}-\text{count('B')}}^{n - \text{count('W')}}$.

But there is one exception. If all are WB and BW, because there is no BB and WW, then the painting method which include both WB and BW is invalid.

Obviously, "W?" and "?B" can only be painted as WB. "?W" and "B?" can only be painted as BW. And "??" can do both.

let use invalid to represent the number of invalid painting methods, then $invalid=2^{\text{count('??')}}$.

But there are exceptions here. If all can be painted by WB, invalid-=1. Similarly, if all can be painted BW, invalid-=1.

So, the final result is: $C_{2n-\text{count('W')}-\text{count('B')}}^{n - \text{count('W')}} - \text{invalid}$.

Java

C++

]]>First, we can compare the digits of x. If the digits are different, we will continue to multiply the number with less digits by 10 until the digits are the same.

Then compare the adjusted p. If p is the same, then compare x.

Java

C++

Obviously x mod y <x. Therefore, we always choose x as the minimum value of the array, and then y can be chosen from the remaining numbers.

Java

C++

Binary search for the value of k. Calculate the total damage according to the problem description each time.

Java

C++

This problem needs to think clearly about the ways of constructing it. With the construction method the DP will be more obvious.

Starting from L, just DFS. Look for the cell that is a + each time, and then continue to search based on the + cell.

On the problem, C++ is easier to TLE than Java. Because the values of n and m vary widely, the speed of C++ dynamically generating and initializing a two-dimensional array seems not as fast as Java.

Java

C++

]]>First, we consider what options are available to meet the conditions.

Obviously [0, 1, 2, 3, 4, 5] is eligible, because for any i, x[i]-MEX(x[1],..., x[i])=-1. Similarly, [0, 1, 2, 3, 4, 5, 5, ... ,5] also meets the conditions.

The total number of all possibilities of this construction is actually clear: we use dp[x] to represent the possible number of subsequences starting from 0 and ending with x.

So obviously for each i, dp[x[i]]+=dp[x[i]]+dp[x[i]-1]. In other words, for the current x[i], either the previous number is also equal to x[i], or the previous number is equal to x[i]-1

At the same time, we noticed another construction method, such as: [0, 1, 2, 3, 5]. At this time x[i]-MEX(x[1],..., x[i])=5-4=1 (when i=5).

A special feature of this construction method is that the further expansion of this construction has certain restrictions.

First of all [0, 1, 2, 3, 5, 4] is not eligible, because when i=6, x[i]-MEX(x[1],..., x[i])=4- 6=-2. Therefore, it is not difficult to find that there are actually only two expansion methods: 1. [0, 1, 2, 3, 5, 3, 5, 3, ...]; 2. [0, 1, 2, 3, 5, 5 , 5,...].

So for this construction, we use end[x] to represent the total number of all possibilities starting from 0 and ending with x (not including x+2).

So for each i, end[x[i]-2]+=end[x[i]-2]+dp[x[i]-2]. In other words, take x[i]=5 as an example, or add a new 5 after [0,1,2,3,5,3,...] (end[x[i]-2] , Because all the previous cases can continue a 5), or it is the first time to add 5 after [0,1,2,3] (dp[x[i]-2], because it is the first time, 0-3 Is continuous).

At the same time end[x[i]]+=end[x[i]]. In other words, still taking 5 as an example, if it was [0,1,2,3,4,5,7,5,7,...] before, we can add another 5.

The final result is equal to the sum of all end[i] and dp[i].

Java

C++

]]>We first consider how to construct an array A that matches the input.

It is not difficult to imagine that if there is such an i such that l1<i<r1 and l2<i<r2, then if the corresponding x1 and x2 are not equal, then a[i] can be equal to x1&x2.

That is to say, if one of the binary bit of x1 or x2 is 0, then a[i] must be 0 in this binary bit.

So naturally, for any binary bit, similar to parentheses pairing, we can find the starting and ending positions that must be 0. And then construct A.

Then we consider how to find the result based on this array A.

Obviously, for any subsequence, if there are odd numbers of 1 in a binary bit, the last XOR must also be 1 in this bit. Otherwise, it is 0.

On the other hand, when calculating the addition of the final result, it is obvious that adding through decimal numbers or adding through binary numbers is the same.

Therefore, in general, we perform calculations bit by bit.

For a certain binary bit i (0<i<31). To make this bit have an impact on the result, obviously we only consider the case where this bit is 1.

Therefore, suppose that in the entire array A, the number of 1s is a in the i-th bit. Then we choose b numbers from these 1s (b must be an odd number), and then choose any number of numbers that are 0.

Therefore, for the i-th bit, the result is: $(1<<i) \cdot\sum\limits_{b \text { is odd}} C_a^b \cdot 2^{n-a}$. That is $(1<<i) \cdot 2^{n-a} \cdot\sum\limits_{b \text { is odd}} C_a^b$。

Java

C++

]]>