洛谷-P10786 [NOI2024] 百万富翁 题解

Subtask 1

直接每对 \((i,j)\) 均询问一次，然后找出比其他数都大的一个即可。

Subtask 2

不难想到每次请求把候选点集合二等分并对应连边，每条边必然排除一个数。于是每次请求排除一半候选点。可以做到 \(t=20,s=10^6\)，期望得分 \(11\)。

题目要求 \(t\le 8,s\le 1099944\)。我们需要用查询次数换请求次数。\(1099944\) 这样的奇怪限制启发我们 dp。设 \(f_{k,i}\) 为用 \(k\) 次请求，把 \(i\) 个候选点缩减到 \(1\) 个的最少查询次数，答案即为 \(f_{8,N}\)。转移为：

其中 \(w(j,i)\) 为一次请求把 \(i\) 个候选点缩减到 \(j\) 个的最小查询次数。现在问题变成如何计算 \(w\)。

对于每次请求，我们不妨把查询视为无向图 \(G\) 的边。那么交互库把图定向成 DAG（大指向小），入度不为 \(0\) 的点一定会被排除，我们只保留入度为 \(0\) 的点。

因此在一次请求中留下来的点集中任意两点间无连边，即点集为 \(G\) 的独立集。反过来，任意独立集都能取到：将该独立集排在拓扑序最前面，然后按拓扑序大小关系定向即可给出构造。

因此，如果我们希望一次请求后最多剩下 \(j\) 个候选点，必须保证

其中 \(\alpha(G)\) 是 \(G\) 的最大独立集大小。因此 \(w(j,i)\) 就转化为有 \(i\) 个点且满足 \(\alpha(G)\le j\) 的图 \(G\) 的最小边数。

手模小样例，发现一个比较优秀的构造：把 \(i\) 个点平均分成 \(j\) 组，每组连成完全图，总边数为

事实上，可以证明这是最优构造：

注意到，\(G\) 的独立集和补图 \(\overline{G}\) 中的团一一对应。因此

\[\alpha(G)\le j\Longleftrightarrow K_{j+1}\notin\overline{G} \]

而 \(G\) 的边数最少等价于 \(\overline{G}\) 的边数最多。

这正是图兰定理：

在所有 \(i\) 个点且不包含 \(K_{j+1}\) 的图中，边数最多的图是具有 \(i\) 个点的完全 \(j\) 分图（即上面构造的图）。

现在还有一个问题：朴素 dp 是 \(O(tn^2)\) 的，会 T。暴力枚举发现 \(w\) 满足四边形不等式。这一点可以证明：

往证 \(\forall j<i\) 有

\[w(j,i)+w(j+1,i+1)\le w(j+1,i)+w(j,i+1) \]

移项，得

\[w(j+1,i+1)-w(j+1,i)\le w(j,i+1)-w(j,i) \]

而

\[w(j,i+1)-w(j,i)\le \binom{\left\lfloor i/j\right\rfloor+1}{2}->\binom{\left\lfloor i/j\right\rfloor}{2} \]

代入原式，得

\[\binom{\left\lfloor i/(j+1)\right\rfloor+1}{2}-\binom{\left\lfloor >i/(j+1)\right\rfloor}{2} \le \binom{\left\lfloor i/j\right\rfloor+1}{2}-\binom{\left\lfloor >i/j\right\rfloor}{2} \]

即

\[\left\lfloor i/(j+1)\right\rfloor\le \left\lfloor i/j\right\rfloor \]

证毕。

于是决策单调性成立，可以用分治算法优化到 \(O(tn\log n)\)，发现 \(f_{8,N}\) 的值恰好满足限制，从而通过本题。

Code

#include "richest.h"
#include <vector>
#include <bitset>
#define rep(i,a,b) for(int i(a);i<b;++i)
#define rept(i,a,b) for(int i(a);i<=b;++i)
#define eb emplace_back
#define ll long long
#define il inline
using namespace std;
namespace{
    constexpr ll INF=1e16;
    int N,T,S;
    bool INITED;
}
namespace Case1{
    constexpr int MAXN=1000;
    bitset<MAXN> mk;
    vector<int> A,B,C;
    int solve(){
        if(!INITED){
            A.reserve(499500);
            B.reserve(499500);
            C.reserve(499500);
            INITED=true;
        }
        mk.reset();
        A.clear(),B.clear();
        rep(i,0,N-1) rep(j,i+1,N) A.eb(i),B.eb(j);
        C=ask(A,B);
        rep(i,0,499500) mk.set(C[i]==A[i]?B[i]:A[i]);
        rep(i,0,N) if(!mk[i]) return i;
        return 0;
    }
}
namespace Case2{
    constexpr int MAXN=1e6+1;
    ll f[9][MAXN];
    int g[9][MAXN];
    bitset<MAXN> mk;
    vector<int> A,B,C,D;
    il ll comb(ll x){
        return x*(x-1)/2;
    }
    il ll w(int m,int n){
        int a=n/m,b=n%m;
        return (m-b)*comb(a)+b*comb(a+1);
    }
    void calc(int k,int l,int r,int opt_l,int opt_r){
        int i=l+r>>1;
        g[k][i]=opt_l;
        rept(j,opt_l,min(opt_r,i-1)){
            if(f[k-1][j]+w(j,i)<f[k][i]){
                f[k][i]=f[k-1][j]+w(j,i);
                g[k][i]=j;
            }
        }
        if(l<i) calc(k,l,i-1,opt_l,g[k][i]);
        if(r>i) calc(k,i+1,r,g[k][i],opt_r);
    }
    int solve(){
        mk.reset();
        if(!INITED){  // 仅在初始时运行一次dp
            fill(f[0]+2,f[0]+N+1,INF);
            rept(k,1,8){
                fill(f[k]+1,f[k]+N+1,INF);
                calc(k,1,N,1,N);
            }
            A.reserve(f[8][N]),B.reserve(f[8][N]);
            C.reserve(f[8][N]),D.reserve(f[8][N]);
            INITED=true;
        }
        int k=8,n=N;
        while(n>1){
            int m=g[k][n];
            int len=w(m,n),a=n/m,b=n%m,p=0;
            A.clear(),B.clear(),D.clear();
            rep(_,0,m-b){
                while(D.size()<a){
                    if(!mk[p]) D.eb(p);
                    ++p;
                }
                rep(i,0,D.size()-1){
                    rep(j,i+1,D.size()){
                        A.eb(D[i]),B.eb(D[j]);
                    }
                }
                D.clear();
            }
            rep(_,0,b){
                while(D.size()<a+1){
                    if(!mk[p]) D.eb(p);
                    ++p;
                }
                rep(i,0,D.size()-1){
                    rep(j,i+1,D.size()){
                        A.eb(D[i]),B.eb(D[j]);
                    }
                }
                D.clear();
            }
            C=ask(A,B);
            rep(i,0,len){
                int u=C[i]==A[i]?B[i]:A[i];
                if(!mk[u]) mk.set(u),--n;
            }
            --k;
        }
        rep(i,0,N) if(!mk[i]) return i;
        return 0;
    }
}
int richest(int _N,int _T,int _S){
    N=_N,T=_T,S=_S;
    return N==1000?Case1::solve():Case2::solve();
}