A
题解
知识点：数学。
\(2\) 特判加 \(7\)，其他加 \(3\) 直接偶数。
时间复杂度 \(O(1)\)
空间复杂度 \(O(1)\)
代码
#include #define ll long long using namespace std; bool solve() { int n; cin >> n; if (n == 2) cout << 7 << '\n'; else cout << 3 << '\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
题解
知识点：贪心。
注意到，最优能做到周长等于底边之和乘 \(2\) 加上高度最大值乘 \(2\) 。
我们把短的边当作底边，长的边当作高，这样长的边的贡献会最少。
时间复杂度 \(O(n)\)
空间复杂度 \(O(1)\)
代码
#include #define ll long long using namespace std; bool solve() { int n; cin >> n; ll sum = 0; int mx = 0; for (int i = 1;i <= n;i++) { int x, y; cin >> x >> y; sum += min(x, y); mx = max({ mx,x,y }); } cout << 2 * (sum + 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; }
C
题解
知识点：贪心，枚举。
从小到大排序后，我们发现单独放一个 \(a[1]\) 或 \(a[n]\) 在 bag3 （或 bag1 ）最优，这样就能一次覆盖一段最长的，其他情况因为取在中间，不会超过 \(a[n]-a[1]\) 。
不妨假设单独放了个 \(a[n]\) 在 bag3，再把剩下的分成两段 \([a[1],a[i-1]],[a[i],a[n-1]]\) 分别放在 bag2,1 （较远的放中间），如此得到解 \(a[n] - a[i-1] + a[i] - a[i-1]\) 。同理 \(a[1]\) 单独放，有解 \(a[i] - a[1] + a[i] - a[i-1]\) 。
枚举这两种的所有情况，取最大值。
时间复杂度 \(O(n \log n)\)
空间复杂度 \(O(n)\)
代码
#include #define ll long long using namespace std; int a[200007]; bool solve() { int n; cin >> n; for (int i = 1;i <= n;i++) cin >> a[i]; sort(a + 1, a + n + 1); ll ans = 0; for (int i = 2;i <= n;i++) { ans = max({ ans,2LL * a[i] - a[i - 1] - a[1],-2LL * a[i - 1] + a[n] + a[i] }); } 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; }
D
题解
知识点：贪心，数学。
神奇的华容道。
遍历一遍，能出的直接出，当前不能出的放在除了起点终点之外的地方以后再出，但要保证放之后至少还有两个空位，即只能放 \(nm-4\) 个卡片，否则下一个进来以后就满了动不了，其他情况都能随意移动卡片（华容道qwq）。
时间复杂度 \(O(n \log n)\)
空间复杂度 \(O(n)\)
代码
#include #define ll long long using namespace std; int a[100007]; bool solve() { int n, m, k; cin >> n >> m >> k; priority_queue<int> pq; int p = k; for (int i = 1;i <= k;i++) cin >> a[i]; for (int i = 1;i <= k;i++) { while (!pq.empty() && pq.top() == p) pq.pop(), p--; if (a[i] == p) p--; else { pq.push(a[i]); if (pq.size() >= n * m - 3) return false; } } cout << "YA" << '\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 << "TIDAK" << '\n'; } return 0; }
E
题解
知识点：树形dp。
设 \(dp[u][0/1]\) 表示对于以 \(u\) 为根的子树，子序列包括/不包括 \(u\) 时的答案。
分两种情况讨论：
-
\(dp[u][0]\) 时，那么子节点 \(v_i\) 的最长不下降子序列是可以任意合并的，即子节点的答案 \(\max (dp[v_i][0],dp[v_i][1])\) 能加在一起。因为 \(a[v_i]\) 互相大小没有限制，所以可以自定义后拼在一起。那么答案便是 \(\sum \max (dp[v_i][0],dp[v_i][1])\) 。
-
\(dp[u][1]\) 时，由于根节点 \(u\) 最后只可能等于一个子节点 \(v_i\) ，那么 \(u\) 只可能衔接在一个 \(dp[v_i][1]\) 后面。
\(dp[v_i][0]\) 不能考虑进去。因为，当 \(v_i\) 为根的子树不是条链，一定存在子孙 \(w\) 使得 \(a[v_i]
时间复杂度 \(O(n)\)
空间复杂度 \(O(n)\)
代码
#include using namespace std; vector<int> g[100007]; int f[100007][2]; void dfs(int u) { f[u][0] = 0; f[u][1] = 1; for (auto v : g[u]) { dfs(v); f[u][0] += max(f[v][0], f[v][1]); f[u][1] = max(f[u][1], f[v][1] + 1); } } int main() { std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); int n; cin >> n; for (int i = 2;i <= n;i++) { int p; cin >> p; g[p].push_back(i); } dfs(1); cout << max(f[1][0], f[1][1]) << '\n'; return 0; }