程序员进阶之算法练习（八十一）
题目1
题目链接 题目大意： 给出n个整数的数组，现在可以对数组进行以下操作： 选择数组中任意两个不同的整数a[i]和a[j]，令a[i]=x，a[j]=y，其中满足x*y = a[i] * a[j];
可以进行任意次操作，最后令数组的元素之和尽可能大。
输入： 第一行，整数𝑡 表示t个样例 𝑡 (1≤𝑡≤4000). 每个样例2行，第一行整数 𝑛 (2≤𝑛≤50) 第二行整数𝑎1,𝑎2,…,𝑎𝑛 (1≤𝑎𝑖≤1e6)
输出： 每个样例一行，输出数组的整数和 乘以 2022。
Examples input 3 3 2 3 2 2 1 3 3 1000000 1000000 1 output 28308 8088 2022000000004044
样例解释： 样例1，第一次操作可以选择2和3，变成6和1，数组为[6, 1, 2]；第二次操作选择6和2，得到数组[12, 1, 1]；最终结果为(12+1+1) * 2022 = 28308；
题目解析： 题目的要求是尽可能让数组的元素和尽可能大，我们知道，对于正整数x和y，我们有[x * y, 1] 要大于[x, y]，那么只要把所有数字集中到一个数组即可。
class Solution {
static const int N = 201010;
int a[N];
public:
void solve() {
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
lld sum = n - 1, tmp = 1;
for (int i = 0; i < n; ++i) {
cin >> a[i];
tmp *= a[i];
}
sum += tmp;
cout << sum * 2022 << endl;
}
}
}
ac;题目2
题目链接 题目大意： 给出一个字符串s，现在想要从字符串s中找到最长的子序列，并且该子序列不是回文串； 问，最长的子序列长度为多少；
输入： 第一行，整数𝑡 表示t个样例 𝑡 (1≤𝑡≤1000) 每个样例一行，字符串s （1≤|𝑠|≤50)
输出： 如果不存在子序列，输出-1； 如果存在符合要求子序列，输出最大长度；
Examples input 4 abacaba aaa codeforcesecrofedoc lol
output 6 -1 18 2
题目解析： 如果字符串s全部是相同的字符，那么必然无解，因为无论怎么选择都是回文串； 如果字符串存在不同的字符，那么必然可以构造一个非回文串（去掉任何一个偶数数量的字符即可）；
class Solution {
static const int N = 201010;
char s[N];
public:
void solve() {
int t;
cin >> t;
while (t--) {
cin >> s;
int all = 1, n = strlen(s);
for (int i = 1; i < n; ++i) all = all && (s[i] == s[0]);
if (all) cout << -1 << endl;
else {
bool pl = 1;
int x = 0, y = n - 1;
while (x < y) {
if (s[x] != s[y]) pl = 0;
++x;
--y;
}
cout << (pl ? n - 1 : n) << endl;
}
}
}
}
ac;题目3
题目链接 题目大意： 给出一个n x m的整数矩阵，现在我们定义矩阵和为： 对于矩阵中每一个位置，都计算一遍该位置到左上角所组成的子矩阵，将子矩阵的最大值减去最小值。 （参考链接截图） ∑𝑖=1-𝑛 ∑𝑗=1-𝑚 (1≤𝑥≤𝑖, 1≤𝑦≤𝑗)a[𝑥,𝑦]的最大值 − (1≤𝑥≤𝑖, 1≤𝑦≤𝑗)a[𝑥,𝑦]的最小值。
现在可以对矩阵中的元素任意调整位置，求最大的矩阵和。
输入： 第一行，整数𝑡 表示t个样例 𝑡 (1≤𝑡≤200) 每个样例2行，第一行整数𝑛 和 𝑚 (2≤𝑛,𝑚≤100) 第二行 n x m个整数，𝑏1,𝑏2,…,𝑏𝑛⋅𝑚 (−1e5≤𝑏𝑖≤1e5)
输出： 对于每个样例，输出最大的矩阵和。
Examples input 5 2 2 1 3 1 4 2 2 -1 -1 -1 -1 2 3 7 8 9 -3 10 8 3 2 4 8 -3 0 -7 1 4 3 -32030 59554 16854 -85927 68060 -64460 -79547 90932 85063 82703 -12001 38762
output 9 0 64 71 1933711
题目解析： 题目的意思看着比较复杂，实则要素并不多，对于一个矩阵，真正有意义的就只有4个数字：最小的2个和最大的2个。 按照规则，所有的子矩阵，都由这4个数字组成，因为只关注子矩阵的最大值和最小值。
于是两种，一种是最小值在左上角，相邻位置放最大值和次大值； 一种是最大值在左上角，相邻位置放最小值和次小值；
以样例1来看，就有两种可能： 1 3 4 1 或者 4 1 1 3
针对两种情况都进行计算，取最大值即可。
下面分析一下具体的计算方式，以第一种为例。 当我们在摆放时，首先取出最小值放左上角，那么最大值应该放在相邻最长的一边，这样能最大利用最大值和最小值的差。 为了方便计算，我们令 n <= m；（如果n > m那么交换他们的位置） 这样就可以单独两条边（第一行、第一列）的子矩阵和，最后用（最大值-最小值）x（n-1）x（m-1）即可。
class Solution {
static const int N = 201010;
lld a[N];
public:
void solve() {
int t;
cin >> t;
while (t--) {
int n, m;
cin >> n >> m;
if (n > m) {
int tmp = m;
m = n;
n = tmp;
}
for (int i = 0; i < n * m; ++i) scanf("%lld", &a[i]);
sort(a, a + n * m);
lld ans1 = 0;
ans1 += (a[n * m - 1] - a[0]) * (m - 1);
ans1 += (a[n * m - 2] - a[0]) * (n - 1);
ans1 += (a[n * m - 1] - a[0]) * (n - 1) * (m - 1);
lld ans2 = 0;
ans2 += (a[n * m - 1] - a[0]) * (m - 1);
ans2 += (a[n * m - 1] - a[1]) * (n - 1);
ans2 += (a[n * m - 1] - a[0]) * (n - 1) * (m - 1);
cout << max(ans1, ans2) << endl;
}
}
}
ac;题目4
题目链接 题目大意： MEX是整数数组中未出现的最小非负整数，比如说： [2,2,1]的MEX是0； [0,1,2]的MEX是3； 现在给出整数数组a，可以任意调整数组a的元素顺序，然后再用数组a生成新的数组 [𝑎1+𝑎2,𝑎2+𝑎3,…,𝑎𝑛−1+𝑎𝑛]； 问，新生成数组的MEX最小是多少？
输入： 第一行，整数𝑡 表示t个样例 𝑡 (1≤𝑡≤10000) 每个样例2行； 第一行整数 𝑛 (2≤𝑛≤2⋅1e5). 第二行n个整数𝑎1,𝑎2,…,𝑎𝑛 (0≤𝑎𝑖≤2⋅1e5).
输出： 每个样例一行，输出最小的MEX；
Examples input 3 2 0 0 3 0 0 1 8 1 0 0 0 2 0 3 0
output 1 0 1
题目解析： 假设只有一个元素，那么MEX就取决于整数是否为0； 当有2个元素时，如果都为0，那么结果为1；如果都不为0，那么结果是0；如果存在一个非零整数，那么取决于非零整数是1还是2； 此时我们发现，元素都可以抽象为0、1、非1正整数；
整数0的个数，假设有x个； x = n，答案为1； x > (n+1)/2，0过多，此时一定会有0，那么可以把所有非零整数放在起始位置，只要整数存在任意数字非1，答案为1；否则将整数用0间隔开，答案为2 ；（01010，010100，000011） x <= (n+1)/2，0数量不足，此时必然可以用非零整数去间隔开0，答案为0；
class Solution {
static const int N = 201010;
public:
void solve() {
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
int zeroCnt = 0, notOneCnt = 0;
for (int i = 0; i < n; ++i) {
int tmp;
cin >> tmp;
if (tmp == 0) ++zeroCnt;
else if (tmp > 1) ++notOneCnt;
}
int ans = 0;
if (zeroCnt == n) ans = 1;
else if (zeroCnt <= (n + 1) / 2) ans = 0;
else {
ans = 1 + (notOneCnt == 0);
}
cout << ans << endl;
}
}
}
ac;题目5
题目链接 题目大意： 有m个位置排成一行，标号分别为1、2、3、、、m； 给出n个整数代表n个人，分别由-1、-2和正整数组成： -1表示选择所有已经有人位置的最左边，在该位置的左边坐下，如果左边已经没有位置（比如到位置1了），那么则选择放弃就坐；如果之前没有人就坐，那么会选择位置m； -2表示选择所有已经有人位置的最右边，在该位置的右边坐下，如果右边已经没有位置（比如到位置m了），那么则选择放弃就坐；如果之前没有人就坐，那么会选择位置1； 正整数x表示选择位置x就坐，如果该位置已经有就坐则放弃；
现在问题，假如可以任意安排n个人的就坐时间，请问最多可以安排多少人就坐。
输入： 第一行，整数𝑡 表示t个样例 𝑡 (1≤𝑡≤100) 每个样例2行，第一行整数𝑛 和 𝑚 (1≤𝑛,𝑚≤10000) 第二行 n个整数， 𝑥1,𝑥2,…,𝑥𝑛 (−2≤𝑥𝑖≤𝑚, 𝑥𝑖≠0)
输出： 对于每个样例，输出最大的就坐人数。
Examples input 10 3 10 5 5 5 4 6 1 -2 -2 1 5 7 -1 -1 4 -2 -2 6 7 5 -2 -2 -2 -2 -2 6 6 -1 1 4 5 -1 4 6 8 -1 -1 -1 3 -1 -2 6 7 5 -1 -2 -2 -2 -2 3 1 -2 -2 1 2 5 5 -2 1 2 -1
output 1 3 5 6 5 5 5 1 2 1
题目解析： 简化下题目，所有的数字可以分为三类，-1、-2 和 非负正整数（固定位置），相同位置的数字仅需保留一个； 由题目要求，我们容易知道最初如果选择-1之后，则无法选择-2；（因为m占用了） 同理，选择-2之后也无法选择-1；（因为1占用了） 但是如果已经有固定位置x，那么x左边可以填-1，x右边可以填-2。
三种情况： 1、先考虑-1，那么从n开始，不断往左，最大数量就是-1 和 固定位置的数量； 2、先考虑-2，那么从1开始，不断往右，最大数量就是-2 和 固定位置的数量； 3、先考虑固定位置，假设是最开始是选中位置x，那么从x开始，用-1填充x的左边位置，用-2填充x的右边位置； 并且由题目意思可以知道，-1将无法再进行填充x右边的位置，-2将无法再进行填充x左边的位置，那么最终结果就是x左边合法位置（固定数量和-1数量） + x右边合法位置（固定位置和-2数量）。这个过程可以做到O(1)； 由于无法确定x位置，那么可以用枚举的方式，整体复杂度O(N)；
class Solution {
static const int N = 201010;
int a[N];
public:
void solve() {
int t;
cin >> t;
while (t--) {
int n, m;
cin >> n >> m;
for (int i = 0; i < n; ++i) cin >> a[i];
sort(a, a + n);
int tmp = 0;
for (int i = 1; i < n; ++i) {
if (a[i] == a[i - 1] && a[i] != -1 && a[i] != -2) {
a[i - 1] = m + 1;
++tmp;
}
}
sort(a, a + n);
n -= tmp;
int cnt1 = 0, cnt2 = 0, cnt = 0;
for (int i = 0; i < n; ++i) {
if (a[i] == -1) ++cnt1;
else if (a[i] == -2) ++cnt2;
else ++cnt;
}
int ans = 0;
// case1, -1
ans = max(ans, min(m, cnt1 + cnt));
ans = max(ans, min(m, cnt2 + cnt));
tmp = 0;
for (int i = cnt1 + cnt2; i < n; ++i) {
int sum = 1;
// left
sum += min(a[i] - 1, tmp + cnt1);
// right
sum += min(m - a[i], cnt - tmp - 1 + cnt2);
// 最终结果就是x左边合法位置（固定数量和-1数量） + x右边合法位置（固定位置和-2数量）
ans = max(ans, sum);
++tmp;
}
cout << ans << endl;
}
}
}
ac;腾讯云开发者
