题解：CF1498E Two Houses

ctdpl · 2026-05-11 21:05:21 · 题解

证明：对于两个点 x,y，若 x 的入度 \le y 的入度，则 x 可以走到 y。

反证法，假设 x 不能走到 y。

令 S 为 x 能走到的点的集合， T 为 x 不能走到的点的集合。有 x\in S，y\in T。

显然对于两个点 a,b，若 a\in S，b\in T 则有边 b\to a。所以集合 T 中每个点向 S 中每个点均有连边，集合 S 没有连向集合 T 的边。因此对于每个在集合 S 中的点，入度 \ge 集合 T 的大小。也就是说 x 的入度 \ge 集合 T 的大小，所以 y 的入度 \ge 集合 T 的大小。因为 y\in T，所以 y 的度数 < 集合 T 的大小。（只有 T 集合内部可以连向 y）

矛盾，故 x 可以走到 y。

然后就很好做了，从入度差从大往小遍历点对，查询入度大的是否能走到入度小的即可。

#include <bits/stdc++.h>
using namespace std;
int n,a[505];
pair<int,pair<int,int>> p[250005];char s[15];
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);int m=0;
    for(int i=1;i<=n;i++) for(int j=i+1;j<=n;j++) p[++m]={abs(a[i]-a[j]),a[i]>=a[j]?make_pair(i,j):make_pair(j,i)};
    sort(p+1,p+m+1,greater<pair<int,pair<int,int>>>());
    for(int i=1;i<=m;i++){
        printf("? %d %d\n",p[i].second.first,p[i].second.second);
        fflush(stdout);
         scanf("%s",s+1);
        if(s[1]=='Y'){
            printf("! %d %d\n",p[i].second.first,p[i].second.second);
            return 0;
        }
    }
    printf("! 0 0");
    return 0;
}