Codeforces Round 1048 (Div. 2)

A - Maple and Multiplication

签到，如果相等就不用操作；如果 $a$ 是 $b$ 的倍数，则只需要对 $b$ 进行一次操作；否则，需要进行两次操作把 $a,b$ 都变到 LCM。

AC Code

#include <bits/stdc++.h>
 
void Run() {
    int a, b;
    std::cin >> a >> b;
    if (a > b) std::swap(a, b);
 
    if (a == b) std::cout << 0;
    else if (b % a == 0) std::cout << 1;
    else std::cout << 2;
 
    std::cout << "\n";
}
 
int main() {
    int t;
    std::cin >> t;
    while (t--) Run();
}

B - Cake Collection

注意到对于烤箱 $i$ 来说，我们最后从这个烤箱取出的蛋糕总数量只取决于我们最后时刻是什么时候从这个烤箱取的。例如在 $t=\set{3,7,9}$ 取三次蛋糕，分别取出 $3a_i+(7-3)a_i+(9-7)a_i=9a_i$ 个蛋糕。

所以排序完之后从大往小从 $\min(m,n)$ 个烤箱里取即可

AC Code

#include <bits/stdc++.h>
using ll = long long;
constexpr int N = 2e5 + 10;

ll n, m;
ll a[N];

void Run() {
    std::cin >> n >> m;
    ll sum = 0;
    for (int i = 1; i <= n; i++) std::cin >> a[i], sum += a[i];
    std::sort(a + 1, a + 1 + n);

    ll ans = 0;
    ll r = m % n;

    for (int i = n; i >= 1 && m > 0; i--) {
        ans += a[i] * m;
        m--;
    }
    std::cout << ans << "\n";
}

int main() {
    int t;
    std::cin >> t;
    while (t--) Run();
}

C - Cake Assignment

两个操作的本质是（令 $T=2^{k+1}$ ，即总数）：

$C\gets \frac{C}{2}$
$C\gets \frac{C+T}{2}$

所以，假设经过 $p$ 次操作，最后 Chocola 手里的蛋糕数量一定可以表示为

x=\frac{C+bT}{2^p}, b\in\N

考虑二进制下的表示： $x$ 末尾有 $a$ 个 $0$ ，分子上 $C$ 末尾有 $k$ 个 $0$ ， $bT$ 末尾至少有 $k+1$ 个 $0$ 。于是分子的末尾至少有 $k$ 个 $0$ 。于是

d\cdot 2^a=\frac{e\cdot 2^k}{2^p}

所以 $\min p=k-a$ ，然后 $b$ 也就可以求出来了，于是我们可以从 $b$ 的二进制表示推理出操作次序。时间复杂度 $O(\log n)$ .

AC Code

#include <bits/stdc++.h>
using ll = long long;
using ull = unsigned long long;

void Run() {
    ll k, n;
    std::cin >> k >> n;
    if (n == (1ll << k)) return void(std::cout << 0 << "\n");

    int f = __builtin_ctzll((ull)n);
    int need = k - f;
    ull od = n >> f;
    ull S = (od - 1) >> 1;

    std::cout << need << "\n";
    for (int i = 0; i < need; i++) { std::cout << ((S >> i) & 1 ? 2 : 1) << " "; }
    std::cout << "\n";
}

int main() {
    int t;
    std::cin >> t;
    while (t--) Run();
}

D -

神秘题，赛时说是题意没讲清楚导致 unrated

首先考虑长度为 $3$ 的时候，发现 $[3,2,1]$ 这种情况就不是 perfect 的了，所以思考这个性质能不能推广。

发现是可以的。考虑例子 5 2 4 1 3，如果我先用 op1 交换 5 2，那么就变成 2 5 4 1 3，我可以对中间的 5 4 1 使用 op2。所以我们可以使用 op2 减少操作次数的方式为：先用 op1 交换出长度为 $3$ 的递减子序列，然后用 op2 进行交换。

所以结论是：区间里不能存在长度为 $3$ 的子序列，否则就不是 perfect 的。

后面想到了但是不知道怎么写（

E1/E2 -

首先是一个贪心的想法：我们让深度相同的点染上相同的颜色，这样所有叶子的公共前缀就肯定能尽可能长了。

令深度为 $i$ 的点有 $c_i$ 个，我们考虑第 $i$ 层能否染成 $0$ 。这个就相当于能否选出若干层全部染色成 $0$ ，满足染色为 $0,1$ 的点的数量分别不超过 $k,n-k$ .

E1

我们令 dp[k] 表示可以选出若干层染成 $0$ 且点数为 $k$ 。解决存在性 dp 的一个方法是 bitset dp，即可行性的转移为 dp |= dp << c[i].

那么我们怎么确定能否满足点的数量分别不超过 $k,n-k$ 呢？设前 $i$ 层共有 $s$ 个点，假设可以找到一种选层的方式选出 $f$ 个点染成 $0$ ，那么也就是说，剩下的 $s-f$ 个点都染成了 $1$ ，所以我们可以列出不等式

f\le k\\ f\le s\\ s-f\le n-k\\ f\ge 0

故我们要检查的 dp[f] 的范围是 $\max(0,s-n+k)\le f\le \min(s,k)$ ，所以可以直接从小到大枚举前 $i$ 层，转移 dp 并暴力检查 dp 取最大的 $i$ .

时间复杂度的话，瓶颈在 dp 上：最多 $O(n)$ 层，每次 dp 转移是 $O(\frac{n}{w})$ 的，检查 dp[f] 也是 $O(n)$ 的，所以时间复杂度是 $O(n^2)$ .

AC Code for E1

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

void Run() {
    int n, k;
    std::cin >> n >> k;
    std::vector<std::vector<int>> g(n + 1);
    for (int i = 2; i <= n; ++i) {
        int p;
        std::cin >> p;
        g[p].push_back(i);
    }
    std::vector<int> depth(n + 1, 0);
    std::queue<int> q;
    q.push(1);
    depth[1] = 1;
    std::vector<int> cnt(n + 2, 0);
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        cnt[depth[u]]++;
        for (int v : g[u]) {
            depth[v] = depth[u] + 1;
            q.push(v);
        }
    }
    int Dmin = INT_MAX;
    for (int u = 1; u <= n; ++u) {
        if (g[u].empty()) Dmin = std::min(Dmin, depth[u]);
    }
    std::vector<int> levels;
    for (int d = 1; d <= Dmin; ++d) levels.push_back(cnt[d]);
    sort(levels.begin(), levels.end());

    int ans = 0;
    std::bitset<1005> dp;
    dp.reset();
    dp[0] = 1;
    int su = 0;

    for (int L = 1; L <= (int)levels.size(); ++L) {
        int x = levels[L - 1];
        su += x;
        dp |= (dp << x);
        int f = n - su;
        int low = std::max(0, k - f);
        int high = std::min(k, su);
        bool ok = false;
        if (low <= high) {
            for (int s = low; s <= high; ++s) {
                if (dp[s]) {
                    ok = true;
                    break;
                }
            }
        }
        if (ok) ans = L;
    }
    std::cout << ans << '\n';
}

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

    return 0;
}

E2

考虑进一步优化：BFS 以及收集 levels 肯定是无法优化了的，所以得从 dp 下手。

一个发现：levels 里可能有很多重复的 $a_i$ ，这样的 $a_i$ 至多有 $O(\sqrt n)$ 个，我们考虑能不能把相同的 $a_i$ 放到一起计算。

设 $a_i$ 出现 $m_i$ 次。E1 的做法是做 $m_i$ 次 dp 转移，我们可以使用倍增，将 $m_i$ 次拆分为 $1,2,4,\dots$ ，这样既可以拼出任意的 $x\in [0,m_i]$ ，时间复杂度也能降低至 $O(\log m_i)$ .

此外，我们也可以二分 $i$ ，表示前 $i$ 层可以选出这样的 $f$ 。单调性是显然的（点数量都不够当然随便选）。

总时间复杂度： $O(\log n)\cdot O(\sqrt n)\cdot O(\frac{n}{w})=O(\frac{n\sqrt n\log n}{w})$

AC Code

#include <bits/stdc++.h>
#define sz(x) int(x.size())
constexpr int N = 2e5 + 10;
using ll = long long;
using vi = std::vector<int>;

int n, k, depth[N], cnt[N], m;
vi g[N], lv, vals, tot, pf;

void Run() {
    std::cin >> n >> k;
    for (int i = 2, fa; i <= n; i++) std::cin >> fa, g[fa].push_back(i);

    [&] {
        depth[1] = 1;
        std::queue<int> q;
        q.push(1);

        while (!q.empty()) {
            int u = q.front();
            q.pop();
            cnt[depth[u]]++;
            for (auto v : g[u]) {
                depth[v] = depth[u] + 1;
                q.push(v);
            }
        }
    }();

    int dmin = INT_MAX;
    for (int i = 1; i <= n; i++)
        if (g[i].empty()) dmin = std::min(dmin, depth[i]);
    for (int d = 1; d <= dmin; d++) lv.push_back(cnt[d]);
    std::sort(lv.begin(), lv.end());

    for (int i = 0; i < sz(lv);) {
        int j = i;
        while (j < sz(lv) && lv[i] == lv[j]) j++;
        vals.push_back(lv[i]);
        tot.push_back(j - i);
        i = j;
    }
    m = sz(vals);

    pf.push_back(0);
    for (int i = 0; i < m; i++) pf.push_back(pf[i] + tot[i]);

    auto check = [&](int M) {
        if (M == 0) return true;
        vi used(m, 0);
        int need = M;
        ll sum = 0;
        for (int i = 0; i < m; i++) {
            if (need <= 0) break;
            int t = std::min(need, tot[i]);
            used[i] = t;
            need -= t;
            sum += 1ll * vals[i] * t;
        }

        ll rest = n - sum;

        int l = std::max(0ll, 1ll * k - rest);
        int r = std::min(1ll * k, sum);
        if (l > r) return false;

        std::bitset<N> dp;
        dp.reset();
        dp.set(0);

        for (int i = 0; i < m; i++) {
            int x = vals[i], u = used[i], p = 1;
            while (u > 0) {
                int t = std::min(p, u);
                int w = x * t;
                dp |= dp << w;
                u -= t;
                p <<= 1;
            }
        }

        for (int i = l; i <= r; i++)
            if (dp.test(i)) return true;
        return false;
    };

    int l = -1, r = dmin + 1;
    while (l + 1 < r) {
        int mid = l + ((r - l) >> 1);
        if (check(mid)) l = mid;
        else r = mid;
    }
    std::cout << l << "\n";
}

void Clean() {
    for (int i = 1; i <= n; i++) {
        cnt[i] = 0;
        g[i].clear();
        depth[i] = 0;
    }
    lv.clear(), tot.clear(), vals.clear(), pf.clear();
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int T;
    std::cin >> T;
    while (T--) Run(), Clean();
}