Missing Subarray Sum

题目描述

There is a hidden array $a$ of $n$ positive integers. You know that $a$ is a palindrome, or in other words, for all $1\le i\le n$, $a_i=a_{n+1-i}$. You are given the sums of all but one of its distinct subarrays, in arbitrary order. The subarray whose sum is not given can be any of the $\frac{n(n+1)}{2}$ distinct subarrays of $a$.

Recover any possible palindrome $a$. The input is chosen such that there is always at least one array $a$ that satisfies the conditions.

An array $b$ is a subarray of $a$ if $b$ can be obtained from $a$ by the deletion of several (possibly, zero or all) elements from the beginning and several (possibly, zero or all) elements from the end.

输入描述

The first line of the input contains a single integer $t$ ($1\le t\le 200$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains a single integer $n$ ($3\le n\le 1000$) — the size of the array $a$.

The next line of each test case contains $\frac{n(n+1)}{2}-1$ integers $s_i$ ($1\le s_i\le 10^9$) — all but one of the subarray sums of $a$.

It is guaranteed that the sum of $n$ over all test cases does not exceed $1000$.

Additional constraint on the input: There is always at least one valid solution.

输出描述

For each test case, print one line containing $n$ positive integers $a_1,a_2,\cdots a_n$ — any valid array $a$. Note that $a$ must be a palindrome.

If there are multiple solutions, print any.

样例输入

7
3
1 2 3 4 1
4
18 2 11 9 7 11 7 2 9
4
5 10 5 16 3 3 13 8 8
4
8 10 4 6 4 20 14 14 6
5
1 2 3 4 5 4 3 2 1 1 2 3 2 1
5
1 1 2 2 2 3 3 3 3 4 5 5 6 8
3
500000000 1000000000 500000000 500000000 1000000000

样例输出

1 2 1 
7 2 2 7 
3 5 5 3 
6 4 4 6 
1 1 1 1 1 
2 1 2 1 2 
500000000 500000000 500000000

原题

Codeforces Round 941——传送门

题解

CF题解——传送门

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;vector<ll> create_arr(bool pry, vector<ll> v)
{deque<ll> dq;if (pry){dq.push_back(v[0]);}else{dq.push_front(v[0] / 2);dq.push_back(v[0] / 2);}for (int i = 1; i < v.size(); i++){dq.push_front((v[i] - v[i - 1]) / 2);dq.push_back((v[i] - v[i - 1]) / 2);}return vector<ll>(dq.begin(), dq.end());
}int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int t;cin >> t;while (t--){int n;cin >> n;int num = n * (n + 1) / 2 - 1;vector<ll> a(num);for (int i = 0; i < num; i++){cin >> a[i];a[i] <<= 1;}sort(a.begin(), a.end());vector<ll> single;// 去重for (ll x : a){if (!single.empty() && single.back() == x)single.pop_back();elsesingle.push_back(x);}vector<ll> arr = create_arr(n & 1, single); // 构造出的数组vector<ll> sum(arr.size() + 1, 0); // 前缀和数组ll s = 0;                          // 数组总和for (int i = 1; i <= arr.size(); i++){sum[i] = sum[i - 1] + arr[i - 1];s += arr[i - 1];}vector<ll> section_sum; // 区间和数组for (int i = 0; i < sum.size(); i++){for (int j = i + 1; j < sum.size(); j++){section_sum.push_back(sum[j] - sum[i]);}}sort(section_sum.begin(), section_sum.end());if (section_sum.size() <= a.size())swap(section_sum, a);int i;for (i = 0; a.rbegin()[i] == section_sum.rbegin()[i]; i++);ll x = 2 * section_sum.rbegin()[i] - s;if (single.size() > (n + 1) / 2)single.erase(find(single.begin(), single.end(), x));elsesingle.insert(lower_bound(single.begin(), single.end(), x), x);vector<ll> ans = create_arr(n & 1, single);for (ll x : ans){cout << x / 2 << ' ';}cout << '\n';}return 0;
}