#include 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;} #include 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;} 构造一个 \(n \times m\) 的矩阵，矩阵中的元素是 \(1 \sim n \times m\) 的数字，每个数字只能出现一次，要求相邻元素差的绝对值不是个素数。
题解知识点：构造。
方法一按 \(m\) 奇偶性分类：
(资料图片仅供参考)
\(m\) 是偶数，可构造形如：
\[\begin{array}{l}&1 &2 &3 &4\\&5 &6 &7 &8\\&9 &10 &11 &12\\&13 &14 &15 &16\\\end{array}\]可以保证左右的差的绝对值为 \(1\) ，上下的差的绝对值是 \(m\) 。
\(m\) 是奇数，可构造形如：
\[\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)\)
方法二可构造形如：
\[\begin{array}{l}&1 &2 &3 &4\\&9 &10 &11 &12\\&17 &18 &19 &20\\&5 &6 &7 &8\\&13 &14 &15 &16\\\end{array}\]可以保证左右的差的绝对值为 \(1\) ，上下的差的绝对值是 \(2m\) 或 \(\left( 2 \left\lfloor \dfrac{n-1}{2} \right\rfloor - 1 \right) m\) 。
特别地，当 \(n = 4\) 且 \(m\) 是素数时无法满足，因此考虑 \(n=4\) 时特判，构造形如：
\[\begin{array}{l}&1 &5 &9 &13 &17\\&2 &6 &10 &14 &18\\&3 &7 &11 &15 &19\\&4 &8 &12 &16 &20\\\end{array}\]时间复杂度 \(O(nm)\)
空间复杂度 \(O(1)\)
代码方法一#include 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 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;} 给定一个只包含 (和 )两种字符的字符串 \(s\) 。
现在要求从 \(s_1\) 出发，最终到达 \(s_n\) ，每次可以左右移动一个位置，并依次写下到达的位置的字符。
问通过 \(s\) ，最后能否写下一个合法括号序列。
题解知识点：STL，贪心。
首先若 \(n\) 是奇数无解。
这道题本质就是判断：
对于最后一个((，其右方是否存在一个 ))。对于第一个 ))，其左方是否存在一个 ((。特别地，对于 \(s_1\) 为 )或 \(s_n\) 为 (，也要认为是 ))或 ((。
容易证明，若不满足两个条件的任意一个，那么一定无解；满足这两个条件，一定能构造出一个解。
到这里，其实用两个 set分别维护 ((和 ))的位置，可以直接写了：
((和 ))都不存在，那么有解。若情况1或2满足任意一个，那么无解。否则有解。不过，接下来官方题解的做法更加简洁。
考虑用 set记录所有位置 \(i\) ，满足：
)。若 \(i\) 是偶数，满足 \(s_i\) 是 (。可以看到，第一个满足情况1的位置，只可能在 \(s_1\) 或第一个 ))的位置；最后一个满足情况2的位置，只可能在 \(s_n\) 或最后一个 ((的位置。
因此，我们可以通过类似的判断：
若没有位置满足，那么有解。若第一个记录的位置是奇数或最后一个记录的位置是偶数，那么无解。否则有解。时间复杂度 \(O((n+q) \log n)\)
空间复杂度 \(O(n)\)
代码#include 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 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;} 给定 \(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\) ，有转移方程：
\[f_{i,j} = \begin{cases}f_{i-1,j-1} + (k-1)f_{i-1,j} &,j < n\\f_{i-1,j-1} + kf_{i-1,j} &,j = n\\\end{cases}\]显然dp是会超时的，但是我们从中可以发现，整个过程和 \(a\) 一点关系都没。
因此，我们就假设 \(a_i = 1\) ，显然求不满足的比较容易。 \(b\) 共有 \(k^m\) 种，不满足的情况为 \( 其中组合数是 \(m\) 是 \(10^9\) 的，因此不可以用公式法预处理阶乘及其逆元，考虑用乘法公式递推： 时间复杂度 \(O(n \log m)\) 空间复杂度 \(O(n)\)#include
