Problem A
题解
分解为以下两种情形考虑：
- 当数列已经排序时，无论 $len$ 取值为多少，都不可能成为未排序数列
- 当数列未排序时，则一定有 $i > j\ ,\ a_i < a_j$，那么，只要取 $len = i$，使得该条件继续成立，数列依旧为未排序数列
所以，只需检查数列是否已经按照非递减顺序排序即可（题目规定为是否可以成为非递减序列）
代码实现
int main()
{
int t;
cin >> t;
for (int i = 0; i < t; i++)
{
int n;
cin >> n;
vector<int> a(n);
for (auto &u : a)
cin >> u;
if (!is_sorted(a.begin(), a.end())) // is_sorted()函数检查区间内是否为升序排序
cout << "YES\n"; // 返回迭代器指向第一个破坏排序的元素
else
cout << "NO\n";
}
}
Problem B
题解
对于长度为 $k\ (k>1)$ 的序列，我们可以将它分解成 $k$ 个长度为 $1$ 的序列来进行计算，下面证明其正确性：
考虑以下两种情况：
- 序列中不包含 $0$
- 序列中包含 $0$
显然，对于第一种情况，因为在序列中不包含 $0$，所以其中所有子序列的 $mex = 0$，要取得最大值，我们要把序列尽可能多的分开，所以这种情况下的最大代价为 $k$
对于第二种情况，序列的代价为 $mex + 1$，但显然有 $mex \leq k$，所以含 $0$ 序列的代价最大为 $1 + k$
也就是说，序列中非 $0$ 元素的贡献最大为 $1$，$0$ 元素的贡献最大为 $2$
所以我们只需要统计所有子序列的元素个数，对于元素 $0$ 记为两次即可（元素在每一个子序列中都有贡献）
代码实现
int main()
{
int t, n;
cin >> t;
while(t--)
{
cin >> n;
int a, ans = 0;
for(int i = 0; i < n; ++i)
{
cin >> a;
if(!a)
ans += (i + 1) * (n - i);
ans += (i + 1) * (n - i);
}
cout << ans << endl;
}
return 0;
}
Problem C
题解
考虑以下绝对不可能达成要求的两种情况：
- 对于所有$1 < i < n$ , $a_i = 1$
- $n = 3$ 且 $a_2$ 是奇数
对于不满足以上条件的其余情况，有以下可能：
- 所有石头都在堆 $1$ 和 $n$ 中，那么，自然成立
- 在堆 $i\ (1<i<n)$ 中至少有一个非零的偶数：从这个偶数中拿出 $2$，分解成两个 $1$，一份给予一个奇数，另一份放入堆 $1$ 或者 $n$ 中。那么，我们每次操作， 都会使得奇数的数量 $-1$，并且造出一个新的偶数，所以这种情况也可以达成要求
- 在堆 $i\ (1<i<n)$ 中所有数都是奇数：那么因为不满足所有奇数都是 $1$，所以必然存在一个大于 $1$ 的奇数，从这个数中取出 $2$，那么就退化到了上面的案例
所以，对于堆 $i\ (1<i<n)$ 中的石头来说，我们只需要求出每个堆需要几次操作才能移除所有石头即可，对于偶数堆来说，需要 $\dfrac{a_i}{2}$ 次，对于奇数堆来说，需要 $\dfrac{a_i + 1}{2}$ 次
代码实现
void solve() {
int n;
cin >> n;
vector<int> a(n);
for (auto &x : a)
cin >> x;
if (*max_element(a.begin() + 1, a.end() - 1) == 1 (n == 3 && a[1] % 2 == 1)) {
cout << "-1\n";
return;
}
long long answer = 0;
for (int i = 1; i < n - 1; i++)
answer += (a[i] + 1) / 2;
cout << answer << '\n';
}
int main() {
ios::sync_with_stdio(false), cin.tie(nullptr);
int tests;
cin >> tests;
while (tests--)
solve();
}
