A

代码

#include <bits/stdc++.h>using namespace std;using ll = long long; bool solve() {    int n;    cin >> n;    int mx = -2e9, mi = 2e9;    for (int i = 1;i <= n;i++) {        int x;        cin >> x;        mi = min(x, mi);        mx = max(x, mx);    }    if (mi < 0) cout << mi << '\n';    else cout << mx << '\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 n;    cin >> n;    int pos[3];    for (int i = 1;i <= n;i++) {        int x;        cin >> x;        if (x == 1) pos[0] = i;        else if (x == 2) pos[1] = i;        else if (x == n) pos[2] = i;    }    if (pos[2] < pos[1] && pos[2] < pos[0]) cout << pos[2] << ' ' << min(pos[0], pos[1]) << '\n';    else if (pos[2] > pos[1] && pos[2] > pos[0]) cout << pos[2] << ' ' << max(pos[0], pos[1]) << '\n';    else cout << 1 << ' ' << 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;}

C

题目

构造一个 $n \times m$ 的矩阵，矩阵中的元素是 $1 \sim n \times m$ 的数字，每个数字只能出现一次，要求相邻元素差的绝对值不是个素数。

题解

知识点：构造。

方法一

按 $m$ 奇偶性分类：

1. $m$ 是偶数，可构造形如：

   15913261014371115481216$$\begin{array}{lllll}& 1& 2& 3& 4\\ & 5& 6& 7& 8\\ & 9& 10& 11& 12\\ & 13& 14& 15& 16\end{array}$$

   $$\begin{array}{l} &1 &2 &3 &4\\ &5 &6 &7 &8\\ &9 &10 &11 &12\\ &13 &14 &15 &16\\ \end{array}$$

   可以保证左右的差的绝对值为 $1$ ，上下的差的绝对值是 $m$ 。

2. $m$ 是奇数，可构造形如：

   1713192814203915164101117561218$$\begin{array}{llllll}& 1& 2& 3& 4& 5\\ & 7& 8& 9& 10& 6\\ & 13& 14& 15& 11& 12\\ & 19& 20& 16& 17& 18\end{array}$$

   $$\begin{array}{l} &1 &2 &3 &4 &5\\ &7 &8 &9 &10 &6\\ &13 &14 &15 &11 &12\\ &19 &20 &16 &17 &18\\ \end{array}$$

   可以保证左右的差的绝对值为 $1$ ，上下的差的绝对值是 $m+1$ 。

时间复杂度 $O(nm)$

空间复杂度 $O(1)$

方法二

可构造形如：

可以保证左右的差的绝对值为 $1$ ，上下的差的绝对值是 $2m$ 或 $\left( 2 \left\lfloor \dfrac{n-1}{2} \right\rfloor - 1 \right) m$ 。

特别地，当 $n = 4$ 且 $m$ 是素数时无法满足，因此考虑 $n=4$ 时特判，构造形如：

时间复杂度 $O(nm)$

空间复杂度 $O(1)$

代码

方法一

#include <bits/stdc++.h>using namespace std;using ll = long long; bool solve() {    int n, m;    cin >> n >> m;    if (m & 1) {        for (int i = 1;i <= n;i++)            for (int j = 1;j <= m;j++)                cout << (i - 1) * m + (j + i - 2) % m + 1 << " \n"[j == m];    }    else {        for (int i = 1;i <= n;i++)            for (int j = 1;j <= m;j++)                cout << (i - 1) * m + j << " \n"[j == m];    }    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;}

方法二

#include <bits/stdc++.h>using namespace std;using ll = long long; bool solve() {    int n, m;    cin >> n >> m;    if (n == 4) {        for (int i = 1;i <= n;i++)            for (int j = 1;j <= m;j++)                cout << i + (j - 1) * n << " \n"[j == m];    }    else {        for (int i = 1;i <= n;i++) {            int ii = i <= (n + 1) / 2 ? 2 * i - 1 : 2 * (i - (n + 1) / 2);            for (int j = 1;j <= m;j++) {                cout << (ii - 1) * m + j << " \n"[j == m];            }        }    }    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

题目

给定一个只包含 ( 和 ) 两种字符的字符串 $s$ 。

现在要求从 $s_1$ 出发，最终到达 $s_n$ ，每次可以左右移动一个位置，并依次写下到达的位置的字符。

问通过 $s$ ，最后能否写下一个合法括号序列。

题解

知识点：STL，贪心。

首先若 $n$ 是奇数无解。

这道题本质就是判断：

1. 对于最后一个 (( ，其右方是否存在一个 )) 。
2. 对于第一个 )) ，其左方是否存在一个 (( 。

特别地，对于 $s_1$ 为 ) 或 $s_n$ 为 ( ，也要认为是 )) 或 (( 。

容易证明，若不满足两个条件的任意一个，那么一定无解；满足这两个条件，一定能构造出一个解。

到这里，其实用两个 set 分别维护 (( 和 )) 的位置，可以直接写了：

1. 若 (( 和 )) 都不存在，那么有解。
2. 若情况1或2满足任意一个，那么无解。
3. 否则有解。

不过，接下来官方题解的做法更加简洁。

考虑用 set 记录所有位置 $i$ ，满足：

1. 若 $i$ 是奇数，满足 $s_i$ 是 ) 。
2. 若 $i$ 是偶数，满足 $s_i$ 是 ( 。

可以看到，第一个满足情况1的位置，只可能在 $s_1$ 或第一个 )) 的位置；最后一个满足情况2的位置，只可能在 $s_n$ 或最后一个 (( 的位置。

因此，我们可以通过类似的判断：

1. 若没有位置满足，那么有解。
2. 若第一个记录的位置是奇数或最后一个记录的位置是偶数，那么无解。
3. 否则有解。

时间复杂度 $O((n+q) \log n)$

空间复杂度 $O(n)$

代码

#include <bits/stdc++.h>using namespace std;using ll = long long; int main() {    std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);    int n, q;    cin >> n >> q;    set<int> st;    for (int i = 1;i <= n;i++) {        char ch;        cin >> ch;        if (ch == '(' && !(i & 1) || ch == ')' && (i & 1)) st.insert(i);    }     while (q--) {        int x;        cin >> x;        if (auto it = st.find(x);it != st.end()) st.erase(it);        else st.insert(x);        if (n & 1) {            cout << "NO" << '\n';            continue;        }        if (!st.size()) cout << "YES" << '\n';        else if ((*st.begin() & 1) || !(*prev(st.end()) & 1)) cout << "NO" << '\n';        else cout << "YES" << '\n';    }    return 0;}

E

题目

给定 $n,m,k$ ，再给一个长度为 $n$ 的整数数组 $a$ 满足 $a_i \in [1,k]$ 。

求有多少不同的长度为 $m$ 的整数数组 $b$ ，满足 $b_i \in [1,k]$ 且 $a$ 是 $b$ 的子序列。

不同的定义：两个数组任意一个位置数字不同，可看做不同。

题解

知识点：线性dp，排列组合。

先考虑朴素的dp。

设 $f_{i,j}$ 表示考虑了 $b$ 前 $i$ 个数字，且作为 $b$ 的子序列的 $a$ 的前缀的最长长度为 $j$ ，有转移方程：

显然dp是会超时的，但是我们从中可以发现，整个过程和 $a$ 一点关系都没。

因此，我们就假设 $a_i = 1$ ，显然求不满足的比较容易。 $b$ 共有 $k^m$ 种，不满足的情况为 $<n$ 个 $1$ 且其他都不为 $1$ ，因此不满足的情况有 $\displaystyle$ 种，所以最终答案为：

其中组合数是 $m$ 是 $10^9$ 的，因此不可以用公式法预处理阶乘及其逆元，考虑用乘法公式递推：

时间复杂度 $O(n \log m)$

空间复杂度 $O(n)$

代码

#include <bits/stdc++.h>using namespace std;using ll = long long; const int P = 1e9 + 7;namespace Number_Theory {    int qpow(int a, ll k) {        int ans = 1;        while (k) {            if (k & 1) ans = 1LL * ans * a % P;            k >>= 1;            a = 1LL * a * a % P;        }        return ans;    }}namespace CNM {    using namespace Number_Theory;    const int N = 2e5 + 7;    int n, m, cn[N];    void init(int _n, int _m) {        n = _n;        m = _m;        cn[0] = 1;        for (int i = 1;i <= m;i++) cn[i] = 1LL * (n - i + 1) * qpow(i, P - 2) % P * cn[i - 1] % P;    }    int Cn(int m) {        if (n == m && m == -1) return 1;        if (n < m || m < 0) return 0;        return cn[m];    }}using Number_Theory::qpow;using CNM::Cn; bool solve() {    int n, m, k;    cin >> n >> m >> k;    for (int i = 1, x;i <= n;i++) cin >> x;    CNM::init(m, n);    int ans = qpow(k, m);    for (int i = 0;i <= n - 1;i++) (ans -= 1LL * Cn(i) * qpow(k - 1, m - i) % P - P) %= P;    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;}