题解
知识点：贪心。
代码
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
bool solve() {
int n;
cin >> n;
int cnt = 0;
for (int i = 1;i <= n;i++) {
int x;
cin >> x;
if (x == 1) cnt++;
}
int rst = n - cnt / 2 * 2;
cout << rst + cnt / 2 << '\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;
}
B
题解
知识点：贪心。
代码
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
bool solve() {
int a, b, c, d;
cin >> a >> b >> c >> d;
if (a == 0) {
cout << min(b + c + d, 1) << '\n';
return 1;
}
else {
int ans = a + 2 * min(b, c) + min(a, abs(b - c) + d) + (abs(b - c) + d > a);
cout << ans << '\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
题意
给一个长为 \(n\) 的排列，每次操作可以任选两个数，其中小的挪到开头，大的挪到末尾，问最少几次操作可以使得排列有序。
题解
知识点：贪心，枚举，双指针。
注意到，操作不影响没有被操作过的数字的相对位置，因此考虑排列中不需要操作的数字。显然，最终被保留的数字应该是连续上升的一个子序列，如 23456 是，而 13456 不是因为 \(1\) 和 \(3\) 中间没有 \(2\) 。
假设我们操作了某一组数 \((x,y)\) ，那么 \((x,y),(x-1,y+1),\cdots ,(1,n)\) 一定都需要操作一遍才能保证这些数字有序。因此只有中间的数我们不需要操作，所以我们保留的数字应该从中间开始往外拓展。
若 \(n\) 为奇数，则从中点 \(\dfrac{1+n}{2}\) 开始往两边扩展；若 \(n\) 为偶数，先保证 \(\left\lfloor \dfrac{1+n}{2} \right\rfloor ,\left\lceil \dfrac{1+n}{2} \right\rceil\) 有序，再从这两个数两边扩展，如果不有序直接输出 \(\dfrac{n}{2}\) 。
为了方便找到某个数的位置，我们可以先处理数到位置的映射 \(pos\) ，再利用双指针 \(l,r\) 指向扩展的边界，向两边同时扩展，如果有一边扩展不了那就不需要继续了，最后结果是 \(l-1\) 。
代码
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int pos[200007];
bool solve() {
int n;
cin >> n;
for (int i = 1;i <= n;i++) {
int x;
cin >> x;
pos[x] = i;
}
int l = (1 + n) / 2, r = (1 + n + 1) / 2;
if (pos[l] > pos[r]) {
cout << n / 2 << '\n';
return 1;
}
while (1 < l && r < n) {
if (pos[l - 1] > pos[l] || pos[r] > pos[r + 1]) break;
l--;
r++;
}
cout << l - 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
题意
给你 \(n\) 个长为 \(m\) 的排列 \(a_i\) 。
定义一个排列 \(p\) 的值为满足 \(p_i = i,i \in[1,k]\) 中 \(k\) 的最大值。
定义两个排列 \(p,q\) 的乘法 \(p \cdot q\) 为 \(r_i = q_{p_i}\) 。
对于给定的 \(n\) 个排列中，对于每个排列 \(a_i\) 找到另一个排列 \(a_j\) （ \(j\) 可以等于 \(i\) ）使得 \(a_i \cdot a_j\) 的值最大，求出这 \(n\) 个最大值。
题解
知识点：枚举。
先考虑两个排列 \(p,q\) 乘积的求值过程，即如何求出 \(q_{p_1} = 1,\cdots,q_{p_k} = k\) 中 \(k\) 最大值。
显然 \(q_{p_1} = 1\) ，即 \(q\) 中 \(1\) 的位置是 \(p_1\) ，我们就能得到 \(k\) 至少是 \(1\) ，以此类推直到 \(q_{p_i} \neq i\) 就能得到 \(k = i-1\) ，复杂度是 \(O(n^2m^2)\) ，先考虑先优化枚举过程。
既然我们要知道某个数的位置，那么我们可以先预处理出 \(q\) 所有数字出现的位置 \(pos\) 。我们发现 \(q_{p_i} = i\) 等价于 \(pos_i = p_i\) ，即 \(i\) 出现的位置等于 \(p_i\) 那么自然可以得到 \(q_{p_i} = i\) ，由此我们从 \(pos_1 = p_1\) 开始找到最大的 \(k\) 满足 \(pos_k = p_k\) 即可。现在复杂度是 \(O(n^2m)\) ，考虑优化 \(n\) 次查找。
我们发现查找的过程，其实就是一个 \(p\) 和 \(n\) 个 \(pos\) 匹配最长前缀的过程，可以用字典树 trie 解决，复杂度是 \(O(nm)\) 。但这里 \(m\) 不大（其实是我不会字典树），我们可以将排列用十进制压缩成一个整数，用 map 记录 \(n\) 个排列的前缀信息来解决。设 \(mp_i\) 为 \(n\) 个排列的 \(pos\) 前 \(i\) 个数的前缀信息，例如排列 \(pos = [3,1,4,2]\) 前三个数字的信息就是 \(314\) ，记录在 \(mp_3\) 中。例如，我们查找 \(p = [4,3,2,1]\) 前 \(2\) 个数的匹配信息时，只要判断 \(mp_2\) 中有无 \(43\) 即可。到此为止，我们对 \(p\) 从前 \(1\) 个数依次查找，最多查找 \(m\) 次就可以找到最大的 \(k\) 了，复杂度是 \(O(nm\log n)\) 。
时间复杂度 \(O(nm \log n)\)
空间复杂度 \(O(nm)\)
代码
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int a[50007][11];
int pos[11];
map<ll, int> mp[11];
bool solve() {
int n, m;
cin >> n >> m;
for (int i = 1;i <= m;i++) mp[i].clear();
for (int i = 1;i <= n;i++) {
for (int j = 1;j <= m;j++) {
cin >> a[i][j];
pos[a[i][j]] = j;
}
ll _t = 0;
for (int j = 1;j <= m;j++) {
_t = _t * 10 + pos[j] - 1;
mp[j][_t] = 1;
}
}
for (int i = 1;i <= n;i++) {
ll _t = 0;
int ans = m;
for (int j = 1;j <= m;j++) {
_t = _t * 10 + a[i][j] - 1;
if (!mp[j][_t]) {
ans = j - 1;
break;
}
}
cout << ans << ' ';
}
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;
}