CF2138C1 & CF2138C2 の题解

一份代码同时过，随机化大法才是真神。

考虑题目要求啥。

就是黑白染色，问你从根开始能连续多少层染相同的颜色。

首先先把每一层的节点数记录下来，记为

siz_i

。

考虑一个错误的贪心（根节点深度记为

1

）：

初始时记黑有 $a$ 个，白有 $b$ 个， $i=1$ ；
对于第 $i$ 层有 $siz_i$ 个节点，如果 $\max(a,b)<siz_i$ ，则答案更新为 $i-1$ 并退出，否则转到步骤 $3$ ；
$a,b$ 中较大的一个减去 $siz_i$ ， $i\gets i+1$ 并转到步骤 $2$ 。

很明显是错的，我们稍稍改一下：

初始时记黑有 $a$ 个，白有 $b$ 个， $i=1$ ；
对于第 $i$ 层有 $siz_i$ 个节点，如果 $\max(a,b)<siz_i$ ，则答案更新为 $i-1$ 并退出，否则转到步骤 $3$ ；
如果 $\min(a,b)<siz_i$ ，那么 $a,b$ 中较大的一个减去 $siz_i$ ，否则随机一个减去 $siz_i$ ， $i\gets i+1$ 并转到步骤 $2$ 。

跑

1000

组就行了，实测 C1C2 都是一发通过。

Code

CPP

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define int ll

const int N = 1e6 + 10;
const int INF = 1e18;
const int MOD = 998244353;
using it2 = array<int, 2>;

int n, k, siz[N], deep;
vector<int> g[N];

void dfs(int u, int dep)
{
    ++siz[dep];
    if (g[u].empty())
    {
        deep = min(deep, dep);
        return;
    }
    for (int v : g[u])
    {
        dfs(v, dep + 1);
    }
}

signed main()
{
    cin.tie(0)->sync_with_stdio(false), cout.setf(ios::fixed), cout.precision(10);

    srand(time(0));

    int T;
    cin >> T;
    while (T--)
    {
        cin >> n >> k, deep = INF;
        for (int i = 1; i <= n; ++i)
        {
            g[i].clear(), siz[i] = 0;
        }
        for (int i = 2, fat; i <= n; ++i)
        {
            cin >> fat, g[fat].push_back(i);
        }
        dfs(1, 1), siz[deep + 1] = INF;
        int ans = 1;
        for (int _ = 0, a, b; _ < 1000; ++_)
        {
            a = k, b = n - k;
            for (int i = 1; i <= deep + 1; ++i)
            {
                if (siz[i] > a)
                {
                    if (siz[i] > b)
                    {
                        ans = max(ans, i - 1);
                        break;
                    }
                    else
                    {
                        b -= siz[i];
                    }
                }
                else
                {
                    if (siz[i] > b)
                    {
                        a -= siz[i];
                    }
                    else
                    {
                        if (rand() % 2)
                        {
                            swap(a, b);
                        }
                        a -= siz[i];
                    }
                }
            }
        }
        cout << ans << '\n';
    }

    return 0;
}

CF2138C1 & CF2138C2 の题解

文章操作

CF2138C1 & CF2138C2 の题解

相关推荐

评论

CF2138C1 & CF2138C2 の题解