P16531 [THUPC 2026 Final] Board Duel Game

From the final of the 2026 Tsinghua University Student Programming Contest and Intercollegiate Invitational (THUPC2026). Resources such as the editorial can be found at https://github.com/dapingguo8/THUPC2026-final. > After the single-player block elimination mini-game, Little T and Little S also prepared a two-player interactive board duel mini-game. > > The game is played on a special 10th-anniversary commemorative board. The board contains cells with scores on them. The two players take turns controlling their pieces to jump forward and claim the scores on cells, in order to maximize the difference between their own score and the opponent’s score.

This special board consists of $n$ cells, where the score of cell $i \ (3 \le i \le n)$ is a **positive integer** $a_k$. You decide to play a match against your teammate. At the start of the game, you occupy cell $1$ and place your piece there, and your teammate occupies cell $2$ and places his piece there. At this time, only these two cells are occupied. Both players’ initial scores are zero. You move first, and then the two players take turns. In each turn, suppose the current player’s piece is on cell $x$. Then the player must choose a step size $d \in \{1, 2, 3, 4\}$ such that $x + d \le n$ and cell $x + d$ is **not yet occupied**. Then the player adds the score $a_{x + d}$ of that cell to their own total score, and jumps their piece forward to cell $x + d$. After the jump, the player occupies this new cell (note that the cells previously occupied by this player will remain occupied by this player forever). In particular, if there is no legal step size, the player cannot move this turn and directly skips the turn. When both players cannot move, the game ends. It can be proven that the game will always end in a finite number of moves. Obviously, both you and your teammate are smart enough and will both use optimal strategies. To predict the result in advance, you need to compute the value of your total score minus your teammate’s total score when the game ends.

Each test contains multiple test cases. The first line of the input contains a positive integer $T \ (1 \le T \le 10 ^ 3)$, indicating the number of test cases. For each test case: - The first line contains a positive integer $n \ (6 \le n \le 10 ^ 5)$, indicating the number of cells on the board. - The second line contains $n - 2$ positive integers $a_3, a_4, \dots, a_n \ (1 \le a_k \le 10 ^ 9)$, where each represents the score of the corresponding cell. It is guaranteed that the sum of $n$ over all test cases does not exceed $10 ^ 5$.

For each test case, output one line containing one integer, representing your total score minus your teammate’s total score.

Below, a string of length $n$ is used to represent the game result. The character `.` indicates that the cell is not occupied by anyone, `O` indicates that the cell is occupied by you, and `X` indicates that the cell is occupied by your teammate. For the first test case, on your first move, you have the following three choices: - Choose step size $d = 2$ and jump to cell $3$. Then the game result is `OXOXXO`, and the score difference is $-6$. - Choose step size $d = 3$ and jump to cell $4$. Then the game result is `OX.OOX`, and the score difference is $5$. - Choose step size $d = 4$ and jump to cell $5$. Then the game result is `OX..OX`, and the score difference is $-1$. Therefore, the game result is `OX.OOX`, and the score difference is $5$. For the second test case, one possible game result is `OXOXOXOX`, and the score difference is $0$. For the third test case, one possible game result is `OX..OXOOOX`, and the score difference is $-7$. For the fourth test case, one possible game result is `OX..OXXXO`, and the score difference is $8$. For the fifth test case, one possible game result is `OXXXOXOO`, and the score difference is $90$. For the sixth test case, one possible game result is `OX..OXO.XO`, and the score difference is $1000000000$. Translated by ChatGPT 5