省队集训-0419试机赛

allenchoi · 2025-06-02 01:13:19 · 个人记录

A.石堆分裂

题意：

初始时有一个共 n 个石子的石堆。给定 m，一次操作时，假设有 k 个石堆，大小为 a_{1...k}，可以指定 b_{1...k}，满足 0\le b_i\le a_i,\sum b_i\le m，然后把第 i 堆分裂成 b_i,a_i-b_i 两堆，大小为 0 的当作不存在。求分裂出 n 个大小为 1 的石堆所需的最小操作次数。
多组测试，T\le10^3,n\le m\le10^9。

Sol：

假设要分裂 x 次，则相当于要给 n 个石子都赋一个 [0,2^x) 的编号，每一位表示在这一次操作中这颗石子是分到 b_i 一堆还是 a_i-b_i 一堆，要求这些编号两两不同，且每一位 1 的数量都不超过 m。
考虑二分答案。按照 popcount 贪心，从小到大填入。popcount 相同的数，如果填不够 n 个，给每一位的贡献都是相同的，即 \binom{x-1}{i-1}；否则可以把 1 均摊到每一位，这样一定最优。
复杂度 O(T\log^2n)。

Code：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int T,n,m;
bool check(int x)
{
    ll sum = 0,cnt = 0,c1 = 1,c2 = 1;
    for(int i = 0;i <= x;i++)
    {
        if(i) c1 = c1 * (x - i + 1) / i;
        if(i > 1) c2 = c2 * (x - i + 1) / (i - 1);
        if(sum + c1 >= n) return cnt + (i ? ((n - sum) * i + x - 1) / x : 0) <= m;
        sum += c1,cnt += (i ? c2 : 0);
        if(cnt > m) return false;
    }
    return false;
}
int main()
{
    freopen("split.in","r",stdin);
    freopen("split.out","w",stdout);
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d",&n,&m);
        int l = -1,r = n,mid;
        while(r - l > 1)
        {
            mid = (l + r) / 2;
            if(check(mid)) r = mid;
            else l = mid;
        }
        printf("%d\n",r);
    }
    return 0;
}

白：

题意：

有一个排列，可以执行一次操作：选择若干个不交的区间，然后把区间里的数从小到大排序。也可以选择什么都不做。问可以得到多少本质不同的排列。