A. Sorting Parts
我们可以贪心的选择len等于1，所以当原来是数组是排好序的，就输出”NO“，否则输出”YES“。
void solve(){
cin >> n;
vector<int>q(n);
for(int i = 0; i < n; i ++ ) cin >> q[i];
if(!is_sorted(all(q))){
cout << "YES" << endl;
}else{
cout << "NO" << endl;
}
}
B. MEX and Array
对于任意一个长度为len的一个子段s来讲，产生的最大贡献是把所有的子段拆成长度为1的子段，此时的贡献是 \(f_{max} = len + \sum_{i = 1}^{len}{MEX(s_i)}\)
证明：
子段s有两种情况：
1.包含0。
2.不包含0。
第一种产生 的贡献是 \(1 + MEX(s)\),第二种的贡献是 1 ,显然两种情况的贡献都小于\(f_{max}\)。
所以本题可以暴力枚举所有的子段，然后统计出其中0的个数\(sum1\)，以及子段的长度\(sum2\), 答案\(ans = sum1 + sum2\)。
void solve()
{
cin >> n;
for(int i = 1; i <= n; i ++ ) cin >> a[i];
LL ans = 0;
for(int i = 1; i <= n; i ++ ){
for(int j = 1; j <= n - i + 1; j ++ ){
for(int k = i; k <= i + j - 1; k ++ ){
ans += a[k] == 0;
}
ans += j;
}
}
cout << ans << endl;
}
C. Andrew and Stones
如果中间的都是1，或者只有一个奇数，则无法完成任务，结论是显然的。
证明：如果中间都是1，则无法进行操作，如果中间只有一个奇数，那么执行若干次后也变成1，无法继续操作。如果中间存在一个大于等于2石子堆的，可以贪心的分1个石子给其他的奇数堆，则奇数堆也变成了偶数堆，依次递归可以处理完所有石子。
计算最小的操作次数：假设中间的石子堆中石子数目为\(num\),两种情况：
如果\(num\)为偶数，需要的操作次数为\(num / 2\)。
如果\(num\)为奇数，我们要把它变成大于\(num\)的最小的偶数，所以操作次数为\((num + 1) / 2\)
综上：对于每一堆石子需要的操作次数为\((num + 1) / 2\)。
void solve()
{
cin >> n;
int cnt1 = 0, cnt0 = 0;
for(int i = 1; i <= n; i ++ ){
cin >> a[i];
if(i > 1 && i < n && a[i] == 1) cnt1 ++;
}
if(cnt1 == n - 2 || (n == 3 && a[2] % 2)){
cout << -1 << endl;
return;
}
LL ans = 0;
for(int i = 2; i <= n - 1; i ++ )
ans += a[i] + 1 >> 1;
cout << ans << endl;
return;
}