[ICPC2021 Nanjing R] Windblume Festival

单击此处下载原神

题面翻译

给一个长度为 nnn 环形整数序列 aaa, 每次操作可以任意选择一个下标 xxx,令 $ a_x = a_x – a_{(x\bmod n)+1}$,之后移除 a ( x m o d   n ) + 1 a_{(x\bmod n)+1}a(xmodn)+1

最后会剩下一个元素,要求最大化这个元素。

数据范围 1 ≤ n ≤ 1 06, − 1 09≤ ai≤ 1 09 1\le n\le10^6,-10^9\le a_i\le 10^91n106,109ai109

题目描述

The Windblume Festival in Mondstadt is coming! People are preparing windblumes for Barbatos and for those they love and adore. The Windblume Festival is also an opportunity to improve the relationships people have.

During the festival, a famous game will be played every year, invented by Jean, the Acting Grand Master of the Knights of Favonius. In the game, nnn players numbered from 111 to nnn stand in a circle, each holding an integer with them. Each turn, one player will be removed. The game will end when there is only one player left.

For each turn, let kkk be the number of players remaining and ai a_iai be the integer player iii holds. Two adjacent players, xxx and ( x m o d   k + 1 )(x \bmod k + 1)(xmodk+1) are selected and player ( x m o d   k + 1 )(x \bmod k + 1)(xmodk+1) is removed from the game. Player xxx’s integer will then change from ax a_xax to ( ax− a x m o d   k + 1)(a_x – a_{x \bmod k + 1})(axaxmodk+1). Player yyy in this turn will become player ( y − 1 )(y – 1)(y1) in the next turn for all x < y ≤ kx < y \le kx<yk, though the integer they hold will not change.

Jean wants to know the maximum possible integer held by the last remaining player in the game by selecting the players in each round optimally.

输入格式

There are multiple test cases. The first line of the input contains one integer TTT indicating the number of test cases. For each test case:

The first line contains one integer nnn ( 1 ≤ n ≤ 1 06 1 \le n \le 10^61n106) indicating the initial number of players.

The next line contains nnn integers ai a_iai ( − 1 09≤ ai≤ 1 09 -10^9 \le a_i \le 10^9109ai109) where ai a_iai is the integer held by player iii at the beginning.

It is guaranteed that the sum of nnn of all test cases will not exceed 1 06 10^6106.

输出格式

For each test case output one line containing one integer indicating the maximum possible integer.

样例 #1

样例输入 #1

541 -3 2 -41191 66 73 71 32 83 72 79 84 33 931291 66 73 71 32 83 72 79 84 33 33 931391 66 73 71 32 83 72 79 84 33 33 33 9310

样例输出 #1

107137467790

提示

For the first sample test case follow the strategy shown below, where the underlined integers are the integers held by the players selected in each turn.

{ 1‾, − 3 , 2 ,− 4‾}\{\underline{1}, -3, 2, \underline{-4}\}{1,3,2,4} (select x = 4x = 4x=4) →\to { − 3 ,2 , − 5‾}\{-3, \underline{2, -5}\}{3,2,5} (select x = 2x = 2x=2) →\to {− 3 , 7‾}\{\underline{-3, 7}\}{3,7} (select x = 2x = 2x=2) →\to { 10 }\{10\}{10}.

以上来自以上来自以上来自原神 洛谷洛谷洛谷

解题思路

我们先列出 3 种情况:只有负数,只有正数,正负数都有。

  • 只有负数:以 −11,−4,−5,−45−11,−4,−5,−45 11,4,5,45 为例,发现得数最大为: 5757 57
  • 只有正数:以 11,4,5,4511,4,5,45 11,4,5,45 为例,发现得数最大为: 5757 57
  • 正负数都有:以 −11,4,−5,45−11,4,−5,45 11,4,5,45 为例,发现得数最大为: 6565 65

我们发现,如果 nnn 个数中正负数都有,输出的值即为所有数的绝对值之和;如果 nnn 个数中只有正数或负数,那输出的数为所有数的绝对值之和,减去最小的绝对值的两倍。

说得简单一点,就是模拟。

AC Code

#include using namespace std;#define int long longconst int Maxn = 1e6 + 10;int T, n, a[Maxn];int minn = INT_MAX, sum1, sum2;int ans;inline void solve() {minn = INT_MAX, sum1 = sum2 = 0;ans = 0;cin >> n;if (n == 1) {cin >> a[0];cout << a[0] << endl;return;}for (int i = 1; i <= n; i++) {cin >> a[i];}bool flag = 1;for (int i = 1; i <= n; i++) {if (a[i] > 0) {flag = 0;break;}}if (flag) {for (int i = 1; i <= n; i++) {a[i] = abs(a[i]);}}for (int i = 1; i <= n; i++) {minn = min(minn, a[i]);sum1 += a[i];sum2 += abs(a[i]);}if (minn < 0) {ans = sum2;} else {ans = sum1 - minn * 2;}cout << ans << endl;}inline void work() {cin >> T;while (T--) {solve();}}signed main() {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);work();return 0;}