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) 奇偶性分类：
-
(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 leftlfloor dfrac{n-1}{2} rightrfloor - 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 <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) 是奇数无解。
题目其实要求我们，对于使得 (s) 不是合法括号序列的位置，需要找到其他位置修正它们。那么，我们可以得到朴素的合法性结论：
- 最后一个让 (s) 不是合法括号序列的
( ，其右方一定要存在 )) 。
- 第一个让 (s) 不是合法括号序列的
) ，其左方一定要存在 (( 。
到这里，其实已经可以通过将 (, ) 转换为 (1,-1) ，然后用线段树二分找到第一个前缀和小于 (0) 的位置（最左侧的不合法 ) ）和最后一个后缀和大于 (0) 的位置（最右侧的不合法 ( ），配合 set 保存 ((, )) 的位置判断是否存在即可。
但这样有点麻烦，我们可以进一步讨论使得 (s) 不是合法括号序列的位置特征和双括号的关系。
容易证明，对于最后一个不合法的 ) ，要么在一组 )) 内，要么在 (s_1) ；最后一个不合法的 ( ，要么在一组 (( 内，要么在 (s_n) 。 因此，这道题本质就是判断：
- 对于最后一个
(( ，其右方是否存在一个 )) 。
- 对于第一个
)) ，其左方是否存在一个 (( 。
特别地，对于 (s_1) 为 ) 或 (s_n) 为 ( ，也要认为是 )) 或 (( 。
到这里，其实用两个 set 分别维护 (( 和 )) 的位置，可以直接写了：
- 若
(( 和 )) 都不存在，那么有解。
- 若情况1或2不满足任意一个，那么无解。
- 否则有解。
不过，接下来官方题解的做法更加简洁。
考虑用 set 记录所有位置 (i) ，满足：
- 若 (i) 是奇数，满足 (s_i) 是
) 。
- 若 (i) 是偶数，满足 (s_i) 是
( 。
可以看到，第一个满足情况1的位置，只可能在 (s_1) 或第一个 )) 的位置；最后一个满足情况2的位置，只可能在 (s_n) 或最后一个 (( 的位置。
因此，我们可以通过类似的判断：
- 若没有位置满足，那么有解。
- 若第一个记录的位置是奇数或最后一个记录的位置是偶数，那么无解。
- 否则有解。
时间复杂度 (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) ，有转移方程：
[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) 种，不满足的情况为 (<n) 个 (1) 且其他都不为 (1) ，因此不满足的情况有 (displaystyle sum_{i=0}^{n-1} binom{m}{i}(k-1)^{m-i}) 种，所以最终答案为：
[k^m -sum_{i=0}^{n-1} binom{m}{i}(k-1)^{m-i} ]
其中组合数是 (m) 是 (10^9) 的，因此不可以用公式法预处理阶乘及其逆元，考虑用乘法公式递推：
[binom{m}{i} = frac{m-i+1}{i} binom{m}{i-1} ]
时间复杂度 (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; }
