题解：CF201E Thoroughly Bureaucratic Organization

· · 题解

一道能让边哥都说有难度的 adhoc 好题。核桃哪位大神把这个 *2600 放 S 组模拟赛 T2 的啊。

考虑如何区分两个人，显然如果存在一次询问，使得其中一个人在返回的集合中，而另一个人不在返回的集合中，那么这两个人是不同的。

继续考虑如何由此确定编号。我们考虑数学归纳法，先找出编号是 1 的，然后由此找到编号为 2,3,\dots 的。先对包含元素 1 的集合对应的位置取个交，然后我们可能会得到多个位置。那么如何排除其余的位置呢？根据所有人的询问互异的结论，易知这多个位置如果在包含 1 的集合里无法区分，那么就一定可以在其他元素不含 1、但是对应的位置包含这几个位置之一的询问区别开来，因此就只剩下了唯一的位置，对应编号 1。剩下的编号依次操作即可。

至此原问题被转化为：找出一个最小的 k，使得给 n 个人分配互不相同的、值域在 [0,2^k-1] 内的数后，对于每一个二进制位，是 1 的数的个数 \le m。

最小的 k 显然具有单调性，可以二分。考虑如何快速 check。

首先发现先把 \operatorname{popcount} 小的编号贪心地赋给某个人一定更优。证明考虑调整法，如果一个 \operatorname{popcount} 更大的编号先赋给了一个人，那么我从用一个 \operatorname{popcount} 更小的、且是原编号二进制下的子集的编号代替一定更优。

那么我们对于 \operatorname{popcount}=0,1,2,3,\dots,k 的询问的方案数分别计算，\operatorname{popcount}=i 的询问共有 C_{k}^{i} 次，如果剩下能放的 1 的个数 lst\le C_{k}^{i}，那我们就直接放置，并且让 lst 减掉它；否则就最多可以进行 \left \lfloor \frac{lst}{i} \right \rfloor 次询问，然后 break 掉，因为后面一定放不了了。最后统计出最多能进行的询问次数，对应着最多能供给的人数，如果 \ge n 则是合法的。

为什么不会出现 lst \le i 但是能放的位置不足 i 个的情况呢？考虑反证，假设有一个位置 x 上 1 被取的个数大于 m，那么一定有另一个位置 y 的 1 被取的个数小于 m，我们为了让方案合法，会把 x 的 1 移到 y 上。并且这一定不会让询问重复，因为 x=0,y=1 的询问的个数一定小于 x=1,y=0 的询问的个数。所以调整后一定可以使得方案合法。

最后证明 check 的复杂度，注意到求答案的式子是 \sum_{i=0}^kC_{k}^{i}=(1+1)^k=2^k，所以枚举 k 的次数是 O(\log V) 的。综上，时间复杂度为 O(t\log^2 n)。

#include <bits/stdc++.h>
#define fi first
#define se second
#define eb(x) emplace_back(x)
#define pb(x) push_back(x)
#define lc(x) (tr[x].ls)
#define rc(x) (tr[x].rs)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ldb;
using pi=pair<int,int>;
ll n,m;
ll check(ll k)
{
    ll lst=m*k,res=1,ad=1;
    for(ll i=1;i<=k;i++)
    {
        ad=ad*(k-i+1)/i;
        if(lst-ad*i>0)
        {
            lst-=ad*i;
            res+=ad;
        }
        else
        {
            res+=lst/i;
            break;
        }
        if(res>=1000000000)return 1000000000;
    }
    return res;
}
void solve()
{
    cin>>n>>m;
    ll l=0,r=n,mid;
    while(l<r)
    {
        mid=(l+r)>>1;
        if(check(mid)>=n)r=mid;
        else l=mid+1;
    }
    cout<<l<<'\n';
}
int main()
{
    //freopen("sample.in","r",stdin);
    //freopen("sample.out","w",stdout);
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t;
    cin>>t;
    while(t--)solve();
    return 0;
}