Codeforces Round 983 (Div. 2) E. Balanced
原题链接
题意
给一个长度为 （且 为奇数） 首尾相连的数组 ，每次操作你可以将 分别加上 注意 时， 指的是 ，同理， 时， 指的是 。
请你找出一个操作序列，即每个位置上需要操作几次，将 中所有元素变成相同值。
题解
设第 个位置上需要操作 次，最后得到的值为 ，则有：
作差分可得
即 ，由于 已知，记为 ，再将正负两两组合，即 ，再令 ，则 。
显然有
然后取 中偶数项可以发现，结合 也是偶数的条件，有
发现还差一项 ，加上 ，得到
于是结合 可以解得 ，再依次代入 中求得所有 。
然后任取 的值，通过 求的 为奇数时的 ，然后通过 转移到 为偶数的情况，因而求得所有 的值，最后如果有小于 的值则全部加上一个偏置即可。
而无解的情况即为 为奇数，不能得到合法的 ，因此无解。
时间复杂度：
代码
模拟一遍上述过程即可
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
| #include <bits/stdc++.h>
using namespace std;
using ll = long long;
void solve()
{
int n;
cin >> n;
vector<ll> a(n + 1);
for (int i = 1; i <= n; i++) cin >> a[i], a[i] = -a[i];
vector<ll> b(n + 1);
for (int i = 1; i <= n; i++) {
b[i] = a[i] - a[i == n ? 1 : i + 1];
}
ll sum = accumulate(b.begin() + 1, b.end(), 0ll);
if (sum & 1) {
cout << -1 << "\n";
return;
}
sum /= 2;
vector<ll> y(n + 1);
ll tmp = 0;
for (int i = 2; i <= n; i += 2) {
tmp += b[i];
}
y[1] = tmp + b[1] - sum;
for (int i = 2; i <= n; i++) {
y[i] = b[i] - y[i - 1];
}
vector<ll> x(n + 1);
x[1] = 0;
for (int i = 3; i <= n; i += 2) {
x[i] = x[i - 2] - y[i - 2];
}
x[n - 1] = y[n - 1] + x[1];
for (int i = n - 3; i >= 1; i -= 2) {
x[i] = y[i] + x[i + 2];
}
ll mn = *min_element(x.begin() + 1, x.end());
for (int i = 1; i <= n; i++) {
x[i] -= mn;
cout << x[i] << " \n"[i == n];
}
}
int main()
{
ios::sync_with_stdio(false), cin.tie(0);
int t;
cin >> t;
while (t--) {
solve();
}
return 0;
}
|