Codeforces 374 Div2

I passed A and B in this round. When I saw question C, I was confused and couldn’t do it. xjb wrote a Kuansou, and then it was forked. Question D has ideas but has not been finished.

Title link and Code link

A One-dimensional Japanese Crossword

Find the interval of b into segments.

B Passwords

The password length is k, start the experiment from the smallest length, randomly search xjb in the string of this length, and ask the minimum cost and maximum cost.

Sort all characters by length, counting those less than k and those less than or equal to k.

*C Journey

The meaning of the question is to give the time to pass between each two points. The starting point is $1$ and the end point is $n$. Ask the maximum number of points that can be traveled within a given T time range. (Point $n \leq 5000 $, edge $m \leq 5000$ time $T\leq 10^9$)

Now consider this question. $dp[x][y]$ means the shortest time it takes to pass $y$ points when $x$ points are found. Then this deep search reaches the $n$ point. Record the previous node during the search process. The code is as follows:

void cal(int x)
{
	if (vis[x])
		return;
	vis[x] = 1;
	if (x == n)
	{
		dp[x][1] = 0;
	}
	for (int i = head[x]; i != -1; i = edge[i].next)
	{
		int nxt = edge[i].to;
		int t = edge[i].tim;
		cal(nxt);
		for (int j = 1; j <= n; j++)
		{
			if (dp[x][j] > t + dp[nxt][j - 1])
			{
				dp[x][j] = t + dp[nxt][j - 1];
				pre[x][j] = nxt;
			}
		}
	}
}

For this kind of problem, it is definitely necessary to record the time and quantity at the same time. Consider using one as an array subscript and the other as a variable.

*D Maxim and Array

Given the number of $n$, you can perform $+x$ or $-x$ operations on any one of them. Now you can operate $k$ times at most. What are the $n$ numbers in the case where the $n$ numbers are multiplied to the minimum.

First determine the number of 0s $x$, $x>k$, which can only be $0$.

Then judge the positive and negative signs and ignore the negative signs. If the sign is positive, consider changing the smallest positive one to a negative one, or changing the largest negative one to a positive one. (The latter situation should be taken into consideration)

After completing these operations, you will find that the problem becomes making the absolute value of their multiplication be the largest. It can be deduced that there are $n$ numbers. When operating on any one, you must choose the number $+x$ with the smallest absolute value. In this case, just maintain the minimum value in the queue continuously $+x$.

I was completely confused when I played it myself, and I was also confused when I used a line segment tree to maintain the minimum value. . . Use priority queue. . .

*E Road to Home

The meaning of the question is that the $n$ section within the range of $L$ is given. Children can sing in this $n$ section. The distance covered each time they sing is $p$. Of course, they do not need to sing. After singing a song, you have to leave a section at least $t$ long before you can sing again. How many times can you sing at most?

Considering each interval, $dp[x]$ represents the maximum number of songs sung to the right end point of the $x$ interval. $en[x]$ records its location. If there are the same number of cases, record its leftmost position.

The cleverness of this question is that you only need to record the maximum number and leftmost position after using the interval each time, instead of starting from 1 every time. The reason [this blog] (http://www.cnblogs.com/sagitta/p/5925785.html) makes it very clear.

If you read the transfer equation carefully, you will find that when transferring, you need to rest first and then sing several times in a row (rest first, then sing). We consider the singing section. If the singing section can continue to be extended by one cycle, then if it is extended at this time, it will definitely make the answer from the starting point to the current interval more optimal. The optimal answer from the starting point to each interval is transferred from the optimal answer from the starting point to the previous interval. If one less song is sung in a certain interval, Then the free time can only be used to sing one song if you are lucky So as long as you follow this greedy idea and maintain the optimal solution from the starting point to the current interval, the final result will be the optimal solution from the starting point to the end point.

The solution to this question $O(n)$ is really clever. It is much better than the one in the solution that discusses various situations according to the range of p. . .