P11218 【MX-S4-T2】「yyOI R2」youyou Does Not Like Summer

Original problem link: 。

youyou has a $2 \times n$ grid, where each cell may be black or white. Now youyou and yy are going to play a game on this grid: - First, youyou chooses a **connected component**, which is allowed to be empty. - Then yy may choose at most $m$ columns in the grid, and swap the colors of the upper and lower cells in each chosen column. A cell set $S$ is called a connected component if and only if any two cells in $S$ can be connected through some cells in $S$ that are **edge-adjacent** (i.e. 4-connected). youyou wants to maximize the final value of (the number of black cells minus the number of white cells) inside the connected component, while yy wants to minimize it. You need to compute: when both players use optimal strategies, what is the final value of (black cells minus white cells) in the connected component?

**This problem has multiple test cases**. The first line contains two integers $c, T$, representing the subtask ID and the number of test cases. If $c = 0$, this subtask is the sample. For each test case, the first line contains two integers $n, m$, representing the number of columns in the grid and the number of swap operations. The next two lines each contain a length-$n$ binary string of $0$ and $1$, describing the colors of the grid. Here, $1$ means a black cell, and $0$ means a white cell.

For each test case, output one line with one number, meaning the final value of (black cells minus white cells).

**[Sample Explanation #1]** In the following, $(x, y)$ denotes the cell in row $x$ and column $y$. For the first test case, youyou chooses the two cells $(1,2)$ and $(2,2)$. No matter how yy swaps, the difference between the number of black cells and the number of white cells is at least $2$. It can be proven that there is no better solution. For the second test case, youyou chooses the eight cells $(1,1),(1,2),(1,3),(1,4),(2,4),(2,5),(2,6),(2,7)$. No matter how yy swaps, the difference between the number of black cells and the number of white cells is at least $4$. It can be proven that there is no better solution. **[Sample #2]** See the attached files ```summer/summer2.in``` and ```summer/summer2.ans```. This sample satisfies the constraints of subtasks $4\sim 7$. **[Sample #3]** See the attached files ```summer/summer3.in``` and ```summer/summer3.ans```. This sample satisfies the constraints of subtasks $10\sim 11$. **[Sample #4]** See the attached files ```summer/summer4.in``` and ```summer/summer4.ans```。 For the first test case, it satisfies special property A. For the second test case, it satisfies special properties B and C. For the third test case, it satisfies special property B. For the fourth test case, it satisfies special property C. For the fifth test case, it satisfies special property D. This sample satisfies $T = 5$ and $\sum n \le 2\times10^6$. **[Sample #5]** See the attached files ```summer/summer5.in``` and ```summer/summer5.ans```。 This sample satisfies the constraints of subtasks $23 \sim 25$. **[Constraints]** This problem has $25$ subtasks, each worth $4$ points. | Subtask ID | $\sum n$ | Special Properties | | :----------: | :-----------------: | :------: | | $1 \sim 3$ | $\le 18$ | None | | $4 \sim 7$ | $\le 100$ | None | | $8 \sim 9$ | $\le10^3$ | None | | $10 \sim 11$ | $\le2\times10^5$ | None | | $12 \sim 13$ | $\le 2 \times 10^6$ | A| | $14 \sim 15$ | $\le 2 \times 10^6$ | B and C| | $16 \sim 17$ | $\le 2 \times 10^6$ | B | | $18 \sim 19$ | $\le 2 \times 10^6$ | C | | $20 \sim 22$ | $\le 2 \times 10^6$ | D | | $23 \sim 25$ | $\le 2 \times 10^6$ | None | Special property A: it is guaranteed that there is no column where the upper and lower cells are one black and one white. Special property B: it is guaranteed that there is no column where both cells are black. Special property C: it is guaranteed that there is no column where both cells are white. Special property D: it is guaranteed that for any position, its color is generated randomly with equal probability of being black or white. For all testdata, it is guaranteed that $1\le T \le 5$, $1 \le m \le n \le 2\times 10^6$, and $\sum n \le 2\times10^6$。 Translated by ChatGPT 5