题解：CF1498E Two Houses

snowfallen · 2026-04-24 19:23:12 · 题解

题意：交互题，给定一张竞赛图的入度序列，你可以进行多次 u 是否能到达 v 的询问，如果回答为 Yes，你就不能再继续询问，你需要输出一对点对 x 和 y，使得 x 和 y 在一个强连通分量里且 x 的入度与 y 的入度之差最大。

竞赛图是对于对两个不同的点 u 和 v，要么有 u 到 v 的边，要么有 v 到 u 的边的图。

竞赛图一定有 \dfrac{n(n-1)}{2} 条边。

这道题是兰道定理模板。

竞赛图的基本性质：SCC 缩点后，所有 SCC 构成一条链。

兰道定理：

对于一张图的入度序列满足 d_1\le d_2\le \dots d_n。

那么这张图是竞赛图的充要条件是：对于每个 i，1\le i\le n，都满足 \sum_{j=1}^i d_j\ge \dfrac{i(i-1)}{2} 且 \sum_{i=1}^n d_i = \dfrac{n(n-1)}{2}。

且如果一个点 k 满足 \sum_{j=1}^k d_j= \dfrac{k(k-1)}{2}，t 是满足 \sum_{j=1}^t d_j= \dfrac{t(t-1)}{2} 大于 k 最小的，那么 [k+1,t] 的点必定形成一个强连通分量。

于是这道题其实都不用向交互库查询，对入读序列排个序直接做就行了。

#include<bits/stdc++.h>
using namespace std;
struct node{
    int v,id;
}k[510];
inline bool operator < (node x,node y){
    return x.v<y.v;
}
int n;
signed main() {
    cin>>n;
    for(int i=1;i<=n;i++) cin>>k[i].v,k[i].id=i;
    sort(k+1,k+n+1);
    int sum=0,minn=2e9,id=0,ans=-2e9,a=0,b=0;
    for(int i=1;i<=n;i++){
        sum+=k[i].v;
        if(sum==i*(i-1)/2){
            if(k[i].v-minn>ans) ans=k[i].v-minn,a=k[i].id,b=k[id].id;
            minn=2e9,id=0;
        }
        else if(minn>k[i].v) minn=k[i].v,id=i;
    }
    if(a==0 || b==0) a=b=0;
    cout<<"! "<<a<<" "<<b;
    return 0;
}