比賽連結

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;
}