Codeforces Round #831 (Div. 1 + Div. 2) A-E

比赛链接

A

题解

知识点：数学。

(2) 特判加 (7)，其他加 (3) 直接偶数。

时间复杂度 (O(1))

空间复杂度 (O(1))

代码

#include <bits/stdc++.h> #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 <bits/stdc++.h> #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 <bits/stdc++.h> #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 <bits/stdc++.h> #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) 时的答案。

分两种情况讨论：

1. (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])) 。

2. (dp[u][1]) 时，由于根节点 (u) 最后只可能等于一个子节点 (v_i) ，那么 (u) 只可能衔接在一个 (dp[v_i][1]) 后面。

   (dp[v_i][0]) 不能考虑进去。因为，当 (v_i) 为根的子树不是条链，一定存在子孙 (w) 使得 (a[v_i]<a[w]) ，那么 (a[u]<a[w]) 不可能衔接到 (w) 后面；当 (v_i) 为根的子树是链时，则 (dp[v_i][1] = dp[v_i][0]+1>dp[v_i][0]) ，没必要选。

时间复杂度 (O(n))

空间复杂度 (O(n))

代码

#include <bits/stdc++.h>  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; }