A
题目
知识点：模拟。
确定开头字母，然后循环比较即可。
时间复杂度 (O(n))
空间复杂度 (O(n))
题解
#include <bits/stdc++.h> #define ll long long using namespace std; bool solve() { string s; cin >> s; string t = "Yes"; int pos = -1; if (s[0] == t[0]) pos = 0; else if (s[0] == t[1]) pos = 1; else if (s[0] == t[2]) pos = 2; else return false; for (auto ch : s) { if (ch != t[pos]) return false; pos = (pos + 1) % 3; } cout << "YES" << '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 << "NO" << 'n'; } return 0; } B
题目
知识点：枚举。
找到总和等于 (sum + s) 的排列，其中 (sum) 是原来序列的和。这个排列的最大数字不能小于原来序列里的最大数字，否则不合法。
时间复杂度 (O(n))
空间复杂度 (O(1))
题解
#include <bits/stdc++.h> #define ll long long using namespace std; bool solve() { int m, s; cin >> m >> s; int mx = 0, sum = 0; for (int i = 1;i <= m;i++) { int x; cin >> x; sum += x; mx = max(x, mx); } int ans = -1; for (int i = 1;i <= 70;i++) { if (i * (i + 1) / 2 == sum + s) { ans = i; break; } } if (ans >= mx) cout << "YES" << 'n'; else cout << "NO" << '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
题目
知识点：贪心。
分类讨论：
- (a=b) ，不用操作。
- (|a-b|geq x) ，一次操作。
- 先将 (a) 变 (l) （或 (r) ），再将 (l) （或 (r) ）变成 (x) ，两次操作（如果可以的话）。
- 先将 (a) 变 (l) （或 (r) ），再将 (l) （或 (r) ）变成 (r) （或 (l) ），再将 (r) （或 (l) ）变成 (x) ，三次操作（如果可以的话）。
- 无解，因为 (a) 变换到 (l) 或 (r) 将会拥有与 (b) 的最大距离，再不行就无解。
时间复杂度 (O(1))
空间复杂度 (O(1))
题解
#include <bits/stdc++.h> #define ll long long using namespace std; bool solve() { int l, r, x; int a, b; cin >> l >> r >> x; cin >> a >> b; if (a == b) cout << 0 << 'n'; else if (abs(a - b) >= x) cout << 1 << 'n'; else if (a - l >= x && b - l >= x || r - a >= x && r - b >= x) cout << 2 << 'n'; else if (a - l >= x && r - l >= x && r - b >= x || r - a >= x && r - l >= x && b - l >= x) cout << 3 << 'n'; else cout << -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; } D
题目
知识点：数论，贪心。
显然尽可能配对 (2) 和 (5) 因子，随后尽可能乘 (10) 。
先找到 (n) 中已有的 (2) ，(5)因子数量，然后先用 (mul) 配平因子数（这样操作的得到的 (mul) 最小）。
之后，给 (mul) 乘 (10) 直到再次操作会超过 (m) 。
最后把 (mul) 加倍到最大值 (m) 内最大值。
时间复杂度 (O(log n + log m))
空间复杂度 (O(1))
题解
#include <bits/stdc++.h> #define ll long long using namespace std; bool solve() { int n, m; cin >> n >> m; int t = n; int c2 = 0, c5 = 0; while (t % 2 == 0) t /= 2, c2++; while (t % 5 == 0) t /= 5, c5++; int mul = 1; while (c2 < c5 && mul * 2LL <= m) mul *= 2, c2++; while (c2 > c5 && mul * 5LL <= m) mul *= 5, c5++; while (mul * 10LL <= m) mul *= 10; cout << 1LL * n * (m / mul) * mul << '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; } E
题目
显然贪心策略是从小到大吸收，考虑道具使用顺序。
方法一
知识点：枚举，dfs。
只有三个道具，直接搜索所有使用顺序即可，每次先把能吸收的吸收了。
时间复杂度 (O(n))
空间复杂度 (O(n))
方法二
知识点：线性dp。
设 (dp[i][j][k]) 表示吸收了前 (i) 个人， (2) 倍道具剩 (j) 个， (3) 倍道具剩 (k) 个的最大能量。
转移时，先从吸收了 (i-1) 个人的状态转移到吸收了 (i) 个人的状态，再考虑吸收了 (i) 个人的状态后使用道具的情况。
使用道具时的转移不需要考虑转移顺序。某个状态被其他的状态更新后，再使用道具的状态一定会被更新他的状态包括，因此不需要考虑更新顺序。
时间复杂度 (O(n))
空间复杂度 (O(n))
题解
方法一
#include <bits/stdc++.h> #define ll long long using namespace std; int n; int a[200007]; int dfs(int pos, int cntg, int cntb, ll h) { while (pos <= n && h > a[pos]) h += a[pos++] / 2; int mx = pos - 1; if (cntg >= 1) mx = max(mx, dfs(pos, cntg - 1, cntb, h * 2)); if (cntb >= 1) mx = max(mx, dfs(pos, cntg, cntb - 1, h * 3)); return mx; } bool solve() { int h; cin >> n >> h; for (int i = 1;i <= n;i++) cin >> a[i]; sort(a + 1, a + n + 1); cout << dfs(1, 2, 1, h) << '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 <bits/stdc++.h> #define ll long long using namespace std; int a[200007]; ll f[200007][3][2]; bool solve() { int n, h; cin >> n >> h; for (int i = 1;i <= n;i++) cin >> a[i]; sort(a + 1, a + n + 1); for (int i = 1;i <= n;i++) for (int j = 0;j <= 2;j++) for (int k = 0;k <= 1;k++) f[i][j][k] = 0; f[0][2][1] = h; f[0][1][1] = h * 2; f[0][2][0] = h * 3; f[0][0][1] = h * 4; f[0][1][0] = h * 6; f[0][0][0] = h * 12; for (int i = 1;i <= n;i++) { for (int j = 0;j <= 2;j++) for (int k = 0;k <= 1;k++) if (f[i - 1][j][k] > a[i]) f[i][j][k] = max(f[i][j][k], f[i - 1][j][k] + a[i] / 2); for (int j = 0;j <= 2;j++) { for (int k = 0;k <= 1;k++) { if (j >= 1) f[i][j - 1][k] = max(f[i][j - 1][k], f[i][j][k] * 2); if (k >= 1) f[i][j][k - 1] = max(f[i][j][k - 1], f[i][j][k] * 3); if (j >= 2) f[i][j - 2][k] = max(f[i][j - 2][k], f[i][j][k] * 4); if (j >= 1 && k >= 1) f[i][j - 1][k - 1] = max(f[i][j - 1][k - 1], f[i][j][k] * 6); if (j >= 2 && k >= 1) f[i][j - 2][k - 1] = max(f[i][j - 2][k - 1], f[i][j][k] * 12); } } } for (int i = n;i >= 0;i--) for (int j = 0;j <= 2;j++) for (int k = 0;k <= 1;k++) if (f[i][j][k]) { cout << i << 'n'; return true; } 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; } F
题目
知识点：贪心，枚举。
显然答案不会大于等于 (p) ，即只需要考虑 (a_n) 关于缺失数字的大小即可，用 set 存出现过的数。
如果没有小于 (a_n) 的缺失数字，就不需要进位，设最大的缺失数字为 (mx) （不存在则设为 (a_n) ），答案为 (mx - a_n) 。
如果有小于 (a_n) 的缺失数字，则必须进位。进位后，一定会出现 (0) 以及模拟进位后变化的最高位的数字，需要纳入 set 。随后找到小于 (a_n) 的最大缺失数字 (mx) （不存在则设为 (0) ），答案为 (mx + p-a_n) 。
因为给出的数字最多只有 (100) 个，所以每次找数字的次数不会超过 (100) 次。
时间复杂度 (O(n log n))
空间复杂度 (O(n))
题解
#include <bits/stdc++.h> #define ll long long using namespace std; int a[107]; bool solve() { int n, p; cin >> n >> p; for (int i = 1;i <= n;i++) cin >> a[i]; set<int> st; for (int i = 1;i <= n;i++) st.insert(a[i]); bool cf = 0; for (int i = a[n];i >= 0 && !cf;i--) cf |= !st.count(i); if (cf) { st.insert(0); for (int i = n - 1;i >= 0;i--) { if (a[i] + 1 < p) { st.insert(a[i] + 1); break; } } int mx = a[n] - 1; while (mx > 0 && st.count(mx)) mx--; cout << mx + p - a[n] << 'n'; } else { int mx = p - 1; while (mx > a[n] && st.count(mx)) mx--; cout << mx - a[n] << '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; } G
题目
知识点：构造，二分，贪心。
显然，(a_{2i} = b_i) 最优，接下来考虑 (a_{2i-1}) 。
首先，我们希望出现在前面的数字尽可能小，但因为留下的数字是较大的，不一定能让后面数字有解。于是，若要确定这个数字，那么就必须每次都需要检查一遍后面的数字是否还有解，这样很难以较小复杂度实现。
但是，我们知道出现在后面的数字要尽可能大，我们可以从后往前确定数字，这样就尽可能保留了小的数字，使得前面的数有解。并且，保留的数字不会比这种方案更小，因此如果前面的数字还是无解，那就真的无解。
因此，我们先把 (1) 到 (n) 存在 set 中，把出现过的数字删除。如果删除的数字已经删过，那么不可能是个排列，所以无解。然后，从后往前，确定未出现的数中小于 (b_i) 的最大数当作 (a_{2i-1}) ，如果没有则无解。
时间复杂度 (O(n log n))
空间复杂度 (O(n))
#include <bits/stdc++.h> #define ll long long using namespace std; int a[200007], b[100007]; bool solve() { int n; cin >> n; for (int i = 1;i <= n / 2;i++) cin >> b[i], a[i * 2] = b[i]; set<int> st; for (int i = 1;i <= n;i++) st.insert(i); for (int i = 1;i <= n / 2;i++) { if (!st.count(b[i])) return false; st.erase(b[i]); } for (int i = n / 2;i >= 1;i--) { auto pos = st.lower_bound(b[i]); if (pos == st.begin()) return false; a[i * 2 - 1] = *prev(pos); st.erase(prev(pos)); } for (int i = 1;i <= n;i++) cout << a[i] << ' '; cout << '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; } 
