The 2022 ICPC Asia Xian Regional Contest

B题网络流看了好久都没看明白，这场撑死也只能6题T_T，但是6题还可能铁。🐔了。

---

C - Clone Ranran (CF104077 C)

题目大意

<++>

解题思路

肯定是先复制然后一遍出题最优，枚举复制就行。

神奇的代码

#include <bits/stdc++.h>

using i64 = long long;

void solve() {
    i64 a, b, c;
    std::cin >> a >> b >> c;

    i64 ans = (1LL << 60);
    i64 add = 0;
    for (i64 i = 1;i <= c + c;i <<= 1) {
        ans = std::min(ans, 1LL * ((c + i - 1) / i) * b + add);
        add += a;
    }
    
    std::cout << ans << '\n';
}

int main() {
    std::cin.tie(nullptr)->sync_with_stdio(false);

    int tt = 1;
    std::cin >> tt;
    while (tt --) solve();

    return 0;
}

---

F - Hotel (CF104077 F)

题目大意

<++>

解题思路

贪心

神奇的代码

#include <bits/stdc++.h>

using i64 = long long;

void solve() {
    int n, c1, c2;
    std::cin >> n >> c1 >> c2;

    i64 ans = 0;
    for (int i = 0;i < n;i ++) {
        std::string s;
        std::cin >> s;
        if (c1 * 2 <= c2) {
            ans += 3 * c1;
        } else {
                if (s[0] == s[1] || s[0] == s[2] || s[1] == s[2]) ans += c2 + std::min(c1, c2);
                else ans += std::min(3 * c1, 3 * c2);
        }
    }

    std::cout << ans << std::endl;
}

int main() {
    std::cin.tie(nullptr)->sync_with_stdio(false);

    int tt = 1;
    // std::cin >> tt;
    while (tt --) solve();

    return 0;
}

---

G - Perfect Word (CF104077 G)

题目大意

<++>

解题思路

可以发现，当一个字符串是完美字符串时，他的任意一个子串也必须是完美字符串。判断掐头去尾的两个字符串是否是完美的就可以。

将所有字符串按长度从小到大排序，依次判断哪些是完美字符串维护最大值即可。

神奇的代码

#include <bits/stdc++.h>
#include <string>
#include <unordered_map>

using i64 = long long;

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

    std::vector<std::string> s(n);
    for (int i = 0;i < n;i ++) {
        std::cin >> s[i];
    }

    std::sort(s.begin(), s.end(), [&](std::string &a, std::string &b) {
        return a.size() < b.size();
    });

    int ans = 0;
    std::map<std::string, bool> mp;

    for (int i = 0;i < n;i ++) {
        if (s[i].size() == 1) {
            mp[s[i]] = true;
        } else if (mp.count(s[i].substr(0, s[i].size() - 1)) && mp.count(s[i].substr(1))) {
            mp[s[i]] = true;
        } else continue;
        ans = std::max(ans, int(s[i].size()));
    }

    std::cout << ans << std::endl;
}

int main() {
    std::cin.tie(nullptr)->sync_with_stdio(false);

    int tt = 1;
    // std::cin >> tt;
    while (tt --) solve();

    return 0;
}

---

J - Strange Sum (CF104077 J)

题目大意

<++>

解题思路

去\(i\)为\(n\)显然可以取到整个区间。设\(a\)为最大值，\(b\)为次大值，答案一定为：

\(ans = max(0, a, a + b)\)

神奇的代码

#include <bits/stdc++.h>

using i64 = long long;

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

    std::vector<i64> a(n);
    for (int i = 0;i < n;i ++) {
        std::cin >> a[i];
    }

    std::sort(a.begin(), a.end(), std::greater<int>());
    i64 ans = 0;
    ans = std::max(ans, a[0] + a[1]);
    ans = std::max(ans, a[0]);

    std::cout << ans << std::endl;
}

int main() {
    std::cin.tie(nullptr)->sync_with_stdio(false);

    int tt = 1;
    // std::cin >> tt;
    while (tt --) solve();

    return 0;
}

---

L - Tree (CF104077 L)

题目大意

<++>

解题思路

每个好集合要么是一条链，要么是所有叶子节点。

可以一层一层的叶子节点删上去，不断维护当前有多少条链+删的层数最小即可。

求链用长链剖分也行，直接dfs判断当前层有多少叶子节点也行。

时间复杂度\(o(n)\).

神奇的代码

#include <bits/stdc++.h>
#include <functional>

using i64 = long long;

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

    std::vector<std::vector<int>> g(n + 1, std::vector<int>());
    for (int i = 2;i <= n;i ++) {
        int x;
        std::cin >> x;
        g[i].emplace_back(x);
        g[x].emplace_back(i);
    }

    std::vector<int> cnt(n + 1), dep(n + 1);
    std::function<void(int, int)> dfs = [&](int u, int fa) {
        dep[u] = 1;
        for (int v : g[u]) {
            if (v == fa) continue;
            dfs(v, u);
            dep[u] = std::max(dep[u], dep[v] + 1);
        }
        cnt[dep[u]] ++;
    };

    dfs(1, -1);

    int ans = (1 << 30);
    for (int i = 1;i <= n;i ++) {
        ans = std::min(ans, i + cnt[i] - 1);
    }

    std::cout << ans << '\n';
}

int main() {
    std::cin.tie(nullptr)->sync_with_stdio(false);

    int tt = 1;
    std::cin >> tt;
    while (tt --) solve();

    return 0;
}

---