题目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;