2022 Hangdian Multi-School Seven Black Magic (Sign-in)

Title link: Hangdian Multi-School 7 - Virtual Judge

Sample input:

31 1 1 11 2 3 43 4 5 6

Sample output:

2 44 88 16

Abstract meaning: multiple sets of samples, each set of samples is given four numbers e, l, r, b, representing the numbers of 11, 01, 10, 00 respectively, of which

11: The bricks are white on both sides

01: The brick is black on the left and white on the right

10: The left side of the brick is white and the right side is black

00: The brick is black on both sides

When the adjacent faces of two bricks are black, then the two bricks will be combined into one brick. We place the above bricks in a certain order, and ask us the minimum number of bricks and the maximum number of bricks.number.

Analysis: This is a greedy problem. Let's talk about the minimum number of bricks first. We make the bricks of 10 and 01 match as much as possible.Neighbor , then this can reduce one brick each time, and if there are 10 or 01 bricks, we can also put 00 bricks in one and then combine with 01 or 10 bricksThe blocks are adjacent, so that the 00 bricks will all disappear. We select a 10 and a 01 adjacent each time, so that the minimum value can be obtained. It should be noted that there is no 00 brick, and special judgment is required.

Let's talk about the case with the most values. This is also very simple. According to the greedy strategy, we Put the 01 bricks on the leftmost and connect them together, and thenPut 10 bricks together on the far right, and finally use 11 bricks to cross and place 00 bricks in the middle, so we only need to discuss the relationship between the number of 00 bricks and the number of 11 bricks, if 00 bricksIf the number is greater than the number of 11 bricks + 1, then there will be several 00 bricks connected together, otherwise there will be no black and black connection.

Here is the code:

#include#include#include#include#include