比赛链接：
https://codeforces.com/contest/1637
A. Sorting Parts
题目大意：
长度为 \(n\) 的序列，可以选择一个 \(len (1 <= len <= n - 1)\)，对前 \(len\) 个元素进行非递减排序，对后 \(n - len\) 个元素进行非递减排序。判断是否能使该序列不成为非递减序列。
思路：
只要序列本身有非递减的部分，那么就一定可以选择一个 \(len\) 使序列非递减。
代码：
#include <bits/stdc++.h>
using namespace std;
int T, n;
void solve(){
cin >> n;
vector <int> a(n);
for (int i = 0; i < n; i++)
cin >> a[i];
cout << ((!is_sorted(a.begin(), a.end())) ? "YES\n" : "NO\n");
}
int main(){
cin >> T;
while (T--)
solve();
return 0;
}
B. MEX and Array
题目大意：
将序列 \(b\) 分成 \(c\) 段，\([l_1, r_1], [l_2, r_2], ... ,[l_c, r_c]\)，定义它的 \(cost\) 为 \(c + \sum_{i = 1}^c mex(b_{l_i}, b_{l_i + 1}, .. ,b_{r_i})\)，现给定一个序列 \(a\)，求其所有子区间的 \(cost\) 之和。
思路：
容易发现，分段子区间的时候，将每一段的长度都分成 1 就能实现 \(cost\) 的最大化。
接下来就是实现的过程，可以通过暴力去遍历每一段区间，计算 0 的数量，然后求出答案。时间复杂度为 \(O(n^3)\)。
也可以通过 \(dp\) 来实现，定义 \(dp_{i, j}\) 为 [i, j] 区间中 0 的数量，转移方程就是 \(dp_{l, r} = max(1 + mex({a_l, a_{l + 1}, ... , a_r}), max_{c = l}^{r - 1} (dp_{l, c}, dp_{c + 1, r}))\)。
我们可以发现，其实只要知道所有区间 0 的总数和所有区间的总长度，就可以计算出答案了。在第 \(i\) 个位置上的 0，总共参与了 \(i * (n - i + 1)\) 个区间的计算，这样子一遍遍历就可以计算出 0 的总数。
而所有区间的总长为 \(\sum_{i = 1}^n i * (n - i + 1)\)，一遍遍历，O(n) 的时间复杂度。
代码：
计算区间总长及 0 的总数
#include <bits/stdc++.h>
using namespace std;
int T, n;
void solve(){
cin >> n;
int ans = 0;
vector <int> a(n);
for (int i = 0; i < n; i++)
cin >> a[i];
for (int i = 0; i < n; i++){
ans += (i + 1) * (n - i);
if (a[i] == 0) ans += (i + 1) * (n - i);
}
cout << ans << "\n";
}
int main(){
cin >> T;
while (T--)
solve();
return 0;
}
C. Andrew and Stones
题目大意：
有 n 堆石子，可以选择三个下标 1 <= i < j < k <= n，第 j 堆石子要 >= 2，从第 j 堆中取出 2 个石子，一个放到第 i 堆，一个放到第 k 堆，求最小的步数让所有石子都放到第 1 堆和第 n 堆，若不能实现输出 -1。
思路：
容易发现（我没发现qwq）只有有一堆石子 >= 2，我们就可以实现把所有石子放到 1 和 n 堆中，而最优的步骤就是让石子数是偶数的石子堆的石子放到奇数的堆，然后重复操作，如果没有偶数堆，选择 >= 2 的石子堆，然后去构造偶数的石子堆。
还有一种特殊情况，那就是 n = 3，而第 2 堆石子的数量是奇数的时候，这时候没办法构造偶数堆，所以没法实现把所有石子都移动到 1 和 n 两堆中。
代码：
#include <bits/stdc++.h>
using namespace std;
#define LL long long
LL T, n;
void solve(){
cin >> n;
vector <LL> a(n);
for (int i = 0; i < n; i++)
cin >> a[i];
if (*max_element(a.begin() + 1, a.end() - 1) == 1 || (n == 3 && a[1] % 2)) cout << "-1\n";
else{
LL ans = 0;
for (int i = 1; i < n - 1; i++)
ans += (a[i] + 1) / 2;
cout << ans << "\n";
}
}
int main(){
cin >> T;
while (T--)
solve();
return 0;
}
D. Yet Another Minimization Problem
题目大意：
给定长为 \(n\) 的两个序列 \(a\) 和 \(b\)，定义序列 \(a\) 的 \(cost\) 为 \(\sum_{i = 1}^n \sum_{j = i + 1}^n (a_i + a_j)^2\)，通过交换 \(a[i]\) 和 \(b[i]\)，使 \(a\) 的 \(cost\) + \(b\) 的 \(cost\) 最小。
思路：
将 cost 式子进行变形：
\(\sum_{i = 1}^n \sum_{j = i + 1}^n (a_i + a_j)^2\)
= \(\sum_{i = 1}^n \sum_{j = i + 1}^n (a_i^2 + a_j^2 + 2 a_i a_j)\)
= \(\sum_{i = 1}^n \sum_{j = i + 1}^n (a_i^2 + a_j^2) + \sum_{i = 1}^n \sum_{j = i + 1}^n 2 a_i a_j\)
定义 s = \(\sum_{i = 1}^n a_i\)
原式 = \((n - 1) \sum_{i = 1}^n a_i^2 + \sum_{i = 1}^n (a_i * (s - a_i))\)
= \((n - 1)\sum_{i = 1}^n a_i^2 + s^2 - \sum_{i = 1}^n a_i^2\)
= \((n - 2)\sum_{i = 1}^n a_i^2 + (\sum_{i = 1}^n a_i)^2\)
所以，总的 cost 就是 \((n - 2)\sum_{i = 1}^n (a_i^2 + b_i^2) + (\sum_{i = 1}^n a_i)^2 + (\sum_{i = 1}^n b_i)^2\)
前面部分的值是固定的，要实现总的 cost 的最小，即让 \((\sum_{i = 1}^n a_i)^2 + (\sum_{i = 1}^n b_i)^2\) 最小。
我们可以设 k = \(\sum_{i = 1}^n a_i + \sum_{i = 1}^n b_i\)，cost 就变成 \(s^2 + (k - s)^2\)。即当 s 与 k - s 越接近，答案就越小。
可以通过 dp 求出所有 s 的可能，找到 cost 最小的那个就行了。
代码：
#include <bits/stdc++.h>
using namespace std;
#define all(x) (x).begin(), (x).end()
#define fi first
#define LL long long
#define se second
const int N = 2e5 + 10;
const int mod = 1;
LL T = 1, n;
string s;
void solve(){
cin >> n;
int s = 0;
vector <int> a(n), b(n);
for (int i = 0; i < n; i++)
cin >> a[i], s += a[i];
for (int i = 0; i < n; i++)
cin >> b[i], s += b[i];
vector <int> v(s + 1, 0);
v[0] = 1;
for (int i = 0; i < n; i++)
for (int j = s; j >= 0; j--)
if (v[j]){
if (j + a[i] <= s) v[j + a[i]] = 1;
if (j + b[i] <= s) v[j + b[i]] = 1;
v[j] = 0;
}
int k = 0;
for (int i = 0; i <= s; i++)
if (v[i]){
if (abs(2 * i - s) < abs(2 * k - s)) k = i;
}
int ans = 0;
for (int i = 0; i < n; i++)
ans += (a[i] * a[i] + b[i] * b[i]);
ans *= (n - 2);
ans += (k * k + (s - k) * (s - k));
cout << ans << "\n";
}
int main(){
cin >> T;
while(T--)
solve();
return 0;
}
题目大意：
思路：
代码：