A
题意
给一个数组 \(a\) ，要求重排列以后 \(a[i] \neq a[1,i-1]\) ，其中 \(a[1,i-1]\) 是前 \(i-1\) 项和。
如果无解则输出 NO ；否则，给出一个合法的重排列后的 \(a\) 。
题解
知识点：贪心。
显然先从大到小排序。
若 \(a_1 = a_2\) ，则需要用其他一个数字替换 \(a_1\) ，若此时 \(a[1] = a[n]\) 则没有数字换无解；否则可以交换 \(a_1,a_n\) 。
否则，直接输出即可。
时间复杂度 \(O(n\log n)\)
空间复杂度 \(O(n)\)
代码
#include <bits/stdc++.h>
#define ll long long
using namespace std;
int a[57];
bool solve() {
int n;
cin >> n;
for (int i = 1;i <= n;i++) cin >> a[i];
sort(a + 1, a + n + 1, [&](int a, int b) {return a > b;});
if (a[1] == a[2]) {
if (a[1] == a[n]) return false;
swap(a[1], a[n]);
}
cout << "YES" << '\n';
for (int i = 1;i <= n;i++) cout << a[i] << " \n"[i == n];
return true;
}
int main() {
std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int t = 1;
cin >> t;
while (t--) {
if (!solve()) cout << "NO" << '\n';
}
return 0;
}
B
题意
构造一个 \(n \times n\) 的矩阵，其中元素为整数 \([1,n^2]\) ，每个数字必须使用且只使用一次。
问，所有相邻元素的差的绝对值最多能有多少种，输出最多的那个矩阵。
题解
知识点：构造。
注意到值的范围是 \([1,n^2-1]\) ，猜测可以取满。
我们可以构造类似：
\[\begin{pmatrix} 1 & 25 & 2 & 24 & 3\\ 21 & 5 & 22 & 4 & 23\\ 6 & 20 & 7 & 19 & 8\\ 16 & 10 & 17 & 9 & 18\\ 11 & 15 & 12 & 14 & 13\\ \end{pmatrix} \]从第一行左边开始，走之字形，从 \(1,n^2\) 交替递增递减进行。
时间复杂度 \(O(n^2)\)
空间复杂度 \(O(n^2)\)
代码
#include <bits/stdc++.h>
#define ll long long
using namespace std;
int a[57][57];
bool solve() {
int n;
cin >> n;
int l = 1, r = n * n, f = 0;
for (int i = 1;i <= n;i++) {
for (int j = 1;j <= n;j++) {
a[i][j] = f ? r-- : l++;
f ^= 1;
}
if (!(i & 1)) reverse(a[i] + 1, a[i] + n + 1);
}
for (int i = 1;i <= n;i++) {
for (int j = 1;j <= n;j++) cout << a[i][j] << ' ';
cout << '\n';
}
return true;
}
int main() {
std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int t = 1;
cin >> t;
while (t--) {
if (!solve()) cout << -1 << '\n';
}
return 0;
}
C
题意
有编号 \(1\) 到 \(n\) 的选手，任意两个选手之间会进行且只进行一次比赛，编号大的赢。
你同样也是参赛选手，但你与 \(i\) 号选手比赛的获胜条件是你需要花费 \(a_i\) 的时间否则就会输掉，你共有 \(m\) 的时间可花费。
最终根据获胜场次排名，场次相同的排名相同，排名顺位。例如其他选手获胜场次为 \(3,3,3,2,1\) ，若你获胜 \(3\) 场那你和前三个选手并列第一，若你获胜 \(2\) 场那你和第四个选手并列第 \(4\) 。
问，你最多能排第几。
题解
知识点：贪心，二分。
首先，每个选手都已经有固定胜利场次了，\(i\) 号选手赢 \(i-1\) 场排名 \(n-i+1\) 。
假设你赢了 \(k\) 场，因为 \(\geq k+2\) 号选手，你无论输赢他们都赢的场次一定大于你的；\(\leq k\) 号选手，你无论输赢他们赢的场次一定小于等于你的。因此，你的排名只可能被 \(k+1\) 号选手影响。
若 \(k\) 场中赢了 \(k+1\) 号选手，那么你的排名是第 \(n-k\) 名；否则，\(k+1\) 号选手会比你多赢一场，你的排名是第 \(n-k+1\) 名。
假设最多能赢 \(k\) 场，那么你的排名 \(\geq n-k+1\) ；若赢了 \(<k\) 场，则排名一定 \(\leq n-k+1\) 。因此，我们优先希望赢的最多，再考虑能不能赢 \(k+1\) 号选手。
我们先贪心的求出 \(a_i\) 从小到大排序后的前缀和 \(sum_i\) ，用二分查找最后一个 \(sum_i \leq m\) 则此时 \(i = k\) 。随后，我们判断 \(sum_k\) 中是否已经包括了 \(a_{k+1}\) 。我们可以分类讨论：
- 满足 \(sum_{k-1} + a_{k+1} \leq m\) ，若没有包括 \(a_{k+1}\)，那就可以将第 \(k\) 大的 \(a_i\) 换成 \(a_{k+1}\) 使其包括；若已经包括 \(a_{k+1}\) ，这个不等式自然成立。因此，排 \(n-k\) 名。
- 否则，\(a_{k+1}\) 一定没有被包括，并且不能被替换进去。因此，排 \(n-k+1\) 名。
特判 \(k = 0,n\) 的情况。
时间复杂度 \(O(\log n)\)
空间复杂度 \(O(n)\)
代码
#include <bits/stdc++.h>
#define ll long long
using namespace std;
int a[500007];
int sum[500007];
bool solve() {
int n, m;
cin >> n >> m;
for (int i = 1;i <= n;i++) cin >> a[i], sum[i] = a[i];
sort(sum + 1, sum + n + 1);
for (int i = 1;i <= n;i++) sum[i] += sum[i - 1];
int k = upper_bound(sum + 1, sum + n + 1, m) - sum - 1;
if (k == 0) cout << n + 1 << '\n';
else if (k == n) cout << 1 << '\n';
else if (sum[k - 1] + a[k + 1] <= m) cout << n - k << '\n';
else cout << n - k + 1 << '\n';
return true;
}
int main() {
std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int t = 1;
cin >> t;
while (t--) {
if (!solve()) cout << -1 << '\n';
}
return 0;
}
D
题意
给一个数组 \(a\) ，执行 \(n-2\) 次操作，第 \(i\) 次操作将 \(a_{i+1}\) 任选一个相邻元素加上 \(a_{i+1}\) ，另一个相邻元素减去 \(a_{i-1}\) 。
问最终能生成多少种数组，不同数组至少有一个元素不同。
题解
知识点：线性dp。
设 \(f[i][j]\) 表示为考虑了前 \(i\) 个数，且下一个操作数为 \(j\) 的方案数。
初始条件是 \(f[2][a[2]] = 1\) ，因为第一个数不操作，从 \(i = 2\) 开始。转移方程为：
\[\begin{aligned} f[i+1][a[i+1]+j] = f[i+1][a[i+1]+j] + f[i][j]\\ f[i+1][a[i+1]-j] = f[i+1][a[i+1]-j] + f[i][j]\\ \end{aligned} \]注意到 \(j = 0\) 时，两个方程是同一个，只能执行一次。
可以滚动数组优化空间。
时间复杂度 \(O(n \sum a_i)\)
空间复杂度 \(O(n + \sum a_i)\)
代码
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int mod = 998244353;
int main() {
std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int n;
cin >> n;
vector<int> a(n + 1);
int sum = 0;
for (int i = 1;i <= n;i++) cin >> a[i], sum += a[i];
vector<int> f(2 * sum + 1);
f[a[2] + sum] = 1;
for (int i = 2;i <= n - 1;i++) {
vector<int> g(2 * sum + 1);
for (int j = 0;j <= 2 * sum;j++) {
if (!f[j]) continue;
if (j == sum) g[sum + a[i + 1]] = (g[sum + a[i + 1]] + f[j]) % mod;
else {
g[sum + a[i + 1] + (j - sum)] = (g[sum + a[i + 1] + (j - sum)] + f[j]) % mod;
g[sum + a[i + 1] - (j - sum)] = (g[sum + a[i + 1] - (j - sum)] + f[j]) % mod;
}
}
f = g;
}
int ans = 0;
for (int i = 0;i <= 2 * sum;i++) ans = (ans + f[i]) % mod;
cout << ans << '\n';
return 0;
}
E
题意
有 \(n\) 个boss，对于第 \(i\) 个boss，A击杀需要 \(a_i\) 次尝试，B击杀需要 \(b_i\) 次尝试。
A和B轮流尝试，每次进行 \(k\) 次尝试，A先尝试，各自的尝试是独立的。
如果某轮尝试总数大于等于自己需要的尝试次数，则这个boss算作自己击杀的。
每次boss被某人击杀后，则A和B同时开始尝试下一个boss，尝试计数清零。
问， \(k \in [1,n]\) 取哪些能保证每个boss都是A击杀的。
题解
知识点：数论，差分。
为了使得每次都是A先击杀boss，我们要保证A击杀boss的轮数要小于等于B，即 \(k\) 要满足 \(\lceil \frac{a_i}{k} \rceil \leq \lceil \frac{b_i}{k} \rceil\) 。
显然 \(a_i\leq b_i\) 时，所有 \(k\) 都成立。
当 \(a_i > b_i\) 时，我们可以枚举 \(k\) 的倍数，若某个倍数 \(k'\) 满足存在 \(i\) 使得 \(b_i \leq k' < a_i\) 则 \(\lceil \frac{a_i}{k} \rceil > \lceil \frac{b_i}{k} \rceil\) 不合法；否则 \(\lceil \frac{a_i}{k} \rceil = \lceil \frac{b_i}{k} \rceil\) 合法。对此，我们可以用一个数组 \(d\) 记录所有被 \([b_i,a_i)\) 的覆盖区间，这个可以用差分做到。
时间复杂度 \(O(n \log n)\)
空间复杂度 \(O(n)\)
代码
#include <bits/stdc++.h>
#define ll long long
using namespace std;
int a[200007], b[200007];
int d[200007];
bool solve() {
int n;
cin >> n;
for (int i = 1;i <= n;i++) cin >> a[i], d[i] = 0;
for (int i = 1;i <= n;i++) cin >> b[i];
for (int i = 1;i <= n;i++) {
if (a[i] > b[i]) {
d[b[i]]++;
d[a[i]]--;
}
}
for (int i = 1;i <= n;i++) d[i] += d[i - 1];
vector<int> ans;
for (int i = 1;i <= n;i++) {
bool ok = 1;
for (int j = i;j <= n;j += i) {
if (d[j]) {
ok = 0;
break;
}
}
if (ok) ans.push_back(i);
}
cout << ans.size() << '\n';
for (int i = 0;i < ans.size();i++) cout << ans[i] << " \n"[i == ans.size() - 1];
return true;
}
int main() {
std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int t = 1;
cin >> t;
while (t--) {
if (!solve()) cout << -1 << '\n';
}
return 0;
}