CodeTonRound4-div1+div2题解

题解 A - E

---

Dream is so far ~

A. Beautiful Sequence

检查每一位对应的数字是否小于等于位置，如果可以说明这个数字可以移动到对应位置上， 遍历即可

#include<bits/stdc++.h>
using namespace std;

using i64 = long long;

void solve() {
    int n;
    cin >> n;

    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    for (int i = 1; i <= n; i++) {
        if (a[i] <= i) {
            cout << "Yes\n";
            return;
        }
    }
    cout << "No\n";
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;

    while(t--) {
        solve();
    }

    return 0;
}

B. Candies

考虑到从一开始往后面变，且每次只能变为 $2 n - 1$ 或 $2 n + 1$ ， 显然这些数都是奇数， 考虑从末位往前处理， 每次除以二如果是奇数说明这一次选了2来到这一步，否则将除以二结果加一，同时意味着这一步选了1。

#include<bits/stdc++.h>
using namespace std;

using i64 = long long;

void solve() {
    i64 n;
    cin >> n;

    if (n % 2 == 0) {
        cout << -1 << '\n';
        return;
    }

    vector<int> ans;
    while (n != 1) {
        int now = n / 2;
        if (!(now & 1)) {
            now ++;
            ans.push_back(1);
        }
        else {
            ans.push_back(2);
        }
        n = now;
    }
    cout << ans.size() << '\n';
    for (int i = ans.size() - 1; i >= 0; i--) {
        cout << ans[i] << ' ';
    }
    cout << '\n';
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;

    while(t--) {
        solve();
    }

    return 0;
}

C. Make It Permutation

首先考虑有一个以上数字，显然需要使用第二步操作去掉（否则将不会形成一排列），
之后对于去重后数组， 将其排序， 从后面往前面dp过去， 考虑把后面全部删掉或者是在这两位之间补齐剩下的数字， 有
$dp[i] = min(dp[i + 1] + (b[i + 1] - b[i] - 1) d, c (nn - 1 - i));$
即当前位置最小需要等于上一位到这一位之间需要补齐数字和把后面全部删掉的数字。
注意一开始的1要补上（if no one in this array)

#include<bits/stdc++.h>
using namespace std;

using i64 = long long;

void solve() {
    i64 n, c, d;
    cin >> n >> c >> d;

    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }   

    sort(a.begin() + 1, a.end());
    vector<int> b;

    i64 sum = 0;
    if (a[1] != 1) {
        b.push_back(1);
        sum += d;
    }

    b.push_back(a[1]);
    for (int i = 2; i <= n; i++) {
        if (a[i] == a[i - 1]) {
            sum += c;
            continue;
        }
        b.push_back(a[i]);
    }

    int nn = b.size();
    vector<i64> dp(nn);
    for (int i = nn - 2; i >= 0; i--) {
        dp[i] = min<i64>(dp[i + 1] + (b[i + 1] - b[i] - 1) * d, c * (nn - 1 - i));
    }

    cout << dp[0] + sum << '\n';
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;

    while(t--) {
        solve();
    }

    return 0;
}

D. Climbing The Tree

蜗牛爬树，很好玩的数学题， 直接给代码 ： 思路见代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
int fun (int h, int x, int y) {
    if (h <= x) return 1;
    return ceil ( (h - x) * 1.0 / (x - y) ) + 1;
}
void solve() {
    int q;
    cin >> q;
    bool f = false;
    int l, r;
    while (q --) {
        int op, a, b, n;
        cin >> op >> a >> b;
        if (op == 1) {
            cin >> n;
            if (!f) {
                if (n == 1) {
                    l = 1;
                    r = a;
                }
                else {
                    l = a * n - b * n - a + 2 * b + 1;
                    r = a * n - b * n + b;
                }
                f = true;
                cout << 1 << " ";
            }
            else {
                int x, y;
                if (n == 1) {
                    x = 1;
                    y = a;
                }
                else {
                    x = a * n - b * n - a + 2 * b + 1;
                    y = a * n - b * n + b;
                }
                if (max (x, l) > min (y, r) ) cout << 0 << " ";
                else {
                    l = max (x, l);
                    r = min (y, r);
                    cout << 1 << " ";
                }
            }
        }
        else {
            if (!f) cout << -1 << " ";
            else {
                if (fun (l, a, b) == fun (r, a, b) ) cout << fun (l, a, b) << " ";
                else cout << -1 << " ";
            }
        }
    }
    cout << "\n";
}
signed main () {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;
    
    while (t --) {
        solve();
    }
    
    return 0;
}

E. Monster

给出一张图， 点 u 的遍历需要先经过这一个点所需权值 a[ u ] 个点后才可遍历， 一开始想这道题会想着先选出所有点权为 0 的点， 以这个点作为起点开始bfs 维护一个Krusal树，想着想着不知道怎么写了，换个了思路， 用一个小根堆记录当前能到达的点的相邻所有点， 一开始把所有0的点压入堆中， 用个变量记录当前已经走过的点的数量，之后每次从堆中取出一个点， 检查这个点的权是否小于已经走过的点的数量， 如果大于说明不能到达，直接停止（因为开的是小根堆）， 否则对这个点周围的点进行遍历，如果可以到达就让走过的点++ ， 否则压入堆中等待处理。

#include<bits/stdc++.h>
using namespace std;

using i64 = long long;
constexpr int inf = 1e9 + 7;
struct node {
    int u, w;
    bool operator>(const node& a) const { return this->w > a.w; } 
};
void solve() {
    int n, m;
    cin >> n >> m;

    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    vector<vector<int>> e(n + 1);
    for (int i = 1; i <= m; i++) {
        int u, v;
        cin >> u >> v;
        e[u].push_back(v);
        e[v].push_back(u);
    }
    vector<int> vis(n + 1);

    auto fun = [&](int s) -> bool {
        priority_queue<node, vector<node>, greater<node>> q;
        //queue<int> Q;
        int cnt = 0;
        q.push({s, a[s]});

        while (!q.empty()) {
            auto [u, w] = q.top();
            q.pop();
            if (vis[u] == s) continue;
            vis[u] = s;

            if (cnt >= w) {
                cnt++;
                for (auto v : e[u]) if (vis[v] != s) {
                    q.push({v, a[v]});
                }
            }
            else {
                break;
            }
        }
        //cerr << "cnt : " << cnt << '\n';
        return (cnt == n);
    };

    for (int i = 1; i <= n; i++) {
        if (a[i] == 0 && !vis[i]) {
            if (fun(i)) {
                cout << "Yes\n";
                return;
            }
        }
    }
    cout << "No\n";
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;

    while(t--) {
        solve();
    }

    return 0;
}