比賽連結

A

題解

知識點：貪心，構造。

注意到有 \(1\) 就一定能構造。

時間複雜度 \(O(n)\)

空間複雜度 \(O(1)\)

程式碼

#include <bits/stdc++.h>
#define ll long long

using namespace std;

bool solve() {
    int n, k;
    cin >> n >> k;
    bool ok = 0;
    for (int i = 1;i <= n;i++) {
        int x;
        cin >> x;
        ok |= x;
    }
    if (ok) 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;
}

B

題解

知識點：列舉，雙指標。

用對撞指標，列舉左側 \(1\) 和 右側 \(0\) ，一次操作能消除一對。

時間複雜度 \(O(n)\)

空間複雜度 \(O(n)\)

程式碼

#include <bits/stdc++.h>
#define ll long long

using namespace std;

int a[100007];
bool solve() {
    int n;
    cin >> n;
    for (int i = 1;i <= n;i++) cin >> a[i];
    int l = 1, r = n;
    int cnt = 0;
    while (l <= r) {
        while (l <= r && a[l] == 0)l++;
        while (l <= r && a[r] == 1)r--;
        if (l <= r) {
            l++;
            r--;
            cnt++;
        }
    }
    cout << cnt << '\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_i<a_{i-1}\) 的 \(a_i\) ，使 \(a_i \geq a_{i-1}\) 。這樣的相鄰數對之差大於 \(i\) 的不會超過 \(n-i\) 組，即第 \(i\) 次操作修改的一定小於等於 \(i\) ，因此我們一定可以通過 \(n\) 次操作修改所有這樣的數對。

把所有相鄰兩數的差帶著下標從小到大排序輸出下標就行。

時間複雜度 \(O(n \log n)\)

空間複雜度 \(O(n)\)

程式碼

#include <bits/stdc++.h>
#define ll long long

using namespace std;

int a[100007];
bool solve() {
    int n;
    cin >> n;
    for (int i = 1;i <= n;i++) cin >> a[i];
    vector<pair<int, int>> v;
    v.push_back({ 0,1 });
    for (int i = 2;i <= n;i++) {
        v.push_back({ a[i - 1] - a[i], i });
    }
    sort(v.begin(), v.end());
    for (auto [i, j] : v) cout << j << ' ';
    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;
}

D

題解

知識點：樹形dp，貪心。

此題重點在於如何分配路徑到子節點。

顯然，為了保證子節點路徑數至多相差 \(1\) ，若父節點有 \(p\) 或 \(p+1\) 條路徑，那麼 \(s\) 個子節點可能的路徑數只有 \(\lfloor \frac{p}{s} \rfloor\) 或 \(\lfloor \frac{p}{s} \rfloor + 1\) 。

1. \(s>2\) 和 \(s=1\) 時，顯然成立。
2. \(s = 2\) 時， \(p\) 能被整除時顯然成立。
3. \(s = 2\) 時， \(p\) 不能被整除時 \(p+1\) 一定能被整除，但只有 \(\lfloor \frac{p}{s} \rfloor + 1\) 一種合法情況，\(p\) 有 \(\lfloor \frac{p}{s} \rfloor\) 或 \(\lfloor \frac{p}{s} \rfloor + 1\) 兩種，同樣成立。

我們知道了子節點可能分配到路徑後，對分配方法進行dp就行。

設 \(f[u][0/1]\) ，表示對於節點 \(u\) 的子樹， \(u\) 具有路徑數為 \(p\) 或 \(p+1\) 時，子樹的總貢獻。對於 \(f[u][0/1]\) ，先加上 \(u\) 本身的貢獻，以及子節點 \(v\) 路徑數為 \(\lfloor \frac{p}{s} \rfloor\) 的一種貢獻，即 \(f[v][0]\) ，這是子節點都能分配到的。

然後，對於 \(f[u][0]\) ，可以給 \(p \mod s\) 個子節點多分配一條路徑；對於 \(f[u][1]\) 可以給 \((p+1) \mod s\) 個子節點多分配一條路徑。這些子節點的貢獻可以加一個增量 \(f[v][1]-f[v][0]\) ，我們按照這個增量排序，就能找到增量最大的幾個子節點，我們給它們分配即可。

最後輸出 \(f[1][0]\) ，根節點沒有多一條路徑的選擇。

時間複雜度 \(O(n \log n)\)

空間複雜度 \(O(n)\)

程式碼

#include <bits/stdc++.h>
#define ll long long

using namespace std;

vector<int> g[200007];
int s[200007];
ll f[200007][2];
void dfs(int u, int p) {
    f[u][0] = 1LL * p * s[u];
    f[u][1] = f[u][0] + s[u];
    if (!g[u].size()) return;
    vector<ll> tb;
    for (auto v : g[u]) {
        dfs(v, p / g[u].size());
        f[u][0] += f[v][0];
        f[u][1] += f[v][0];
        tb.push_back(f[v][1] - f[v][0]);
    }
    sort(tb.begin(), tb.end(), [&](ll a, ll b) {return a > b;});
    int r = p % g[u].size();
    for (int i = 0;i < r;i++) f[u][0] += tb[i];
    for (int i = 0;i <= r;i++) f[u][1] += tb[i];
}

bool solve() {
    int n, k;
    cin >> n >> k;
    for (int i = 1;i <= n;i++) g[i].clear();
    for (int i = 2;i <= n;i++) {
        int p;
        cin >> p;
        g[p].push_back(i);
    }
    for (int i = 1;i <= n;i++) cin >> s[i];
    dfs(1, k);
    cout << f[1][0] << '\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;
}