Subtask 2不难想到每次请求把候选点集合二等分并对应连边每条边必然排除一个数。于是每次请求排除一半候选点。可以做到 t20,s106t20,s106期望得分 1111。题目要求 t≤8,s≤1099944t≤8,s≤1099944。我们需要用查询次数换请求次数。10999441099944 这样的奇怪限制启发我们 dp。设 fk,ifk,i​ 为用 kk 次请求把 ii 个候选点缩减到 11 个的最少查询次数答案即为 f8,Nf8,N​。转移为fk,imin⁡1≤ji(fk−1,jw(j,i))fk,i​1≤jimin​(fk−1,j​w(j,i))其中 w(j,i)w(j,i) 为一次请求把 ii 个候选点缩减到 jj 个的最小查询次数。现在问题变成如何计算 ww。对于每次请求我们不妨把查询视作无向图 GG 的边。那么交互库会把图定向成 DAG大指向小有入度的点一定会被排除只保留入度为 00 的点。因此在一次请求中留下来的点集中两两无边是 GG 的独立集。反过来任意独立集或其超集都能取到将独立集安排在拓扑序最前面然后按照拓扑序给边定向就能给出构造。因此如果我们希望一次请求后最多剩下 jj 个候选点必须保证α(G)≤jα(G)≤j其中 α(G)α(G) 是 GG 的最大独立集大小。因此 w(j,i)w(j,i) 就转化为有 ii 个点且满足 α(G)≤jα(G)≤j 的图 GG 的最小边数。手模小样例发现一个比较优秀的构造把 ii 个点平均分成 jj 组每组连成完全图总边数为w(j,i)(imodj)⋅(⌊i/j⌋12)(j−(imodj))⋅(⌊i/j⌋2)w(j,i)(imodj)⋅(2⌊i/j⌋1​)(j−(imodj))⋅(2⌊i/j⌋​)事实上可以证明这是最优构造注意到GG 的独立集和补图 G‾G 中的团一一对应。因此α(G)≤j⟺Kj1∉G‾α(G)≤j⟺Kj1​∈/G而 GG 的边数最少等价于 G‾G 的边数最多。这正是图兰定理在所有 ii 个点且不包含 Kj1Kj1​ 的图中边数最多的图是具有 ii 个点的完全 jj 分图即上面构造的图的补图。现在还有一个问题朴素 dp 是 O(tn2)O(tn2) 的会 T。暴力枚举发现 ww 满足四边形不等式。这一点可以证明往证 ∀ji∀ji 有w(j,i)w(j1,i1)≤w(j1,i)w(j,i1)w(j,i)w(j1,i1)≤w(j1,i)w(j,i1)移项得w(j1,i1)−w(j1,i)≤w(j,i1)−w(j,i)w(j1,i1)−w(j1,i)≤w(j,i1)−w(j,i)而w(j,i1)−w(j,i)(⌊i/j⌋12)−(⌊i/j⌋2)w(j,i1)−w(j,i)(2⌊i/j⌋1​)−(2⌊i/j⌋​)代入原式得(⌊i/(j1)⌋12)−(⌊i/(j1)⌋2)≤(⌊i/j⌋12)−(⌊i/j⌋2)(2⌊i/(j1)⌋1​)−(2⌊i/(j1)⌋​)≤(2⌊i/j⌋1​)−(2⌊i/j⌋​)即⌊i/(j1)⌋≤⌊i/j⌋⌊i/(j1)⌋≤⌊i/j⌋该式恒成立因此原式成立。证毕。于是决策单调性成立可以用分治算法优化到 O(tnlog⁡n)O(tnlogn)。发现 f8,N1099944f8,N​1099944恰好满足限制从而通过本题。Code#include richest.h#include vector#include bitset#define rep(i,a,b) for(int i(a);ib;i)#define rept(i,a,b) for(int i(a);ib;i)#define eb emplace_back#define ll long long#define il inlineusing namespace std;namespace{constexpr ll INF1e16;int N,T,S;bool INITED;}namespace Case1{constexpr int MAXN1000;bitsetMAXN mk;vectorint A,B,C;int solve(){if(!INITED){A.reserve(499500);B.reserve(499500);C.reserve(499500);INITEDtrue;}mk.reset();A.clear(),B.clear();rep(i,0,N-1) rep(j,i1,N) A.eb(i),B.eb(j);Cask(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 MAXN1e61;ll f[9][MAXN];int g[9][MAXN];bitsetMAXN mk;vectorint A,B,C,D;il ll comb(ll x){return x*(x-1)/2;}il ll w(int m,int n){int an/m,bn%m;return (m-b)*comb(a)b*comb(a1);}void calc(int k,int l,int r,int opt_l,int opt_r){int ilr1;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(li) calc(k,l,i-1,opt_l,g[k][i]);if(ri) calc(k,i1,r,g[k][i],opt_r);}int solve(){mk.reset();if(!INITED){ // 仅在初始时运行一次dpfill(f[0]2,f[0]N1,INF);rept(k,1,8){fill(f[k]1,f[k]N1,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]);INITEDtrue;}int k8,nN;while(n1){int mg[k][n];int lenw(m,n),an/m,bn%m,p0;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,i1,D.size()){A.eb(D[i]),B.eb(D[j]);}}D.clear();}rep(_,0,b){while(D.size()a1){if(!mk[p]) D.eb(p);p;}rep(i,0,D.size()-1){rep(j,i1,D.size()){A.eb(D[i]),B.eb(D[j]);}}D.clear();}Cask(A,B);rep(i,0,len){int uC[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 N1000?Case1::solve():Case2::solve();}分类: 题解免责声明本内容来自平台创作者博客园系信息发布平台仅提供信息存储空间服务。好文要顶 关注我 收藏该文 微信分享xiaoniu142857粉丝 - 1 关注 - 0加关注00升级成为会员« 上一篇 洛谷-P7998 [WFOI - 01] 猜数 题解» 下一篇 洛谷-P11942 [KTSC 2025] 重塑矩阵 题解posted 2026-05-16 22:41 xiaoniu142857 阅读(80) 评论(1) 收藏 举报