Two Houses | Codeforces 1498E

· · 题解

此题无需询问，可以线性求出所有强连通分量。

题目链接 可能更好的体验

有一张 n 个点的竞赛图。

不会给这张竞赛图，但会给每个点的入度 k_i。

还可以通过交互询问从 u 能否到达 v，但一旦回答了”是“，就不能再询问了。

定义一个点对 (u,v) 的价值是 |k_u-k_v|。

求所有双向可达的点对中价值最大的一对，或者输出无解。如果有多对，输出任意一对。

n \le 500

考虑拓扑序最小的几个强连通分量的并集 S，S 内的点全部向 S 外的点连边，所以 S 内所有点的入度和等于 \binom {|S|}2，反之亦然。

引理：在竞赛图中，如果 u 能到达 v 而 v 不能到达 u，即 u 的拓扑序严格小于 v，那么 k_u < k_v

证明：如果 v 不能到达 u，\exists S,u \in S \land \forall x \in S, y \not \in S,x \rightarrow y，即集合 S 内的点全部向 S 外的点连边。

\therefore k_v \ge |S|,k_u < |S| \Rightarrow k_u < k_v

把所有点按入度从小到大排序，如果前 m 个节点的入度和等于 \binom m2，那么前 m 个点一定是拓扑序最小的几个强连通分量的并集，并且不会漏掉，这样就可以分离出所有的强连通分量，直接统计答案即可。

复杂度 O(n)，因为排序可以桶排，无需询问。

代码：

#include <bits/stdc++.h>
#define rep(i, l, r) for(int i = (l); i <= (r); i++)
#define per(i, r, l) for(int i = (r); i >= (l); i--)
#define mem(a, b) memset(a, b, sizeof a)
#define For(i, l, r) for(int i = (l), i##e = (r); i < i##e; i++)
#define fi first
#define se second
#define mp make_pair

using namespace std;
const int N = 505;
typedef pair <int, int> P;
int n; P a[N];
int main() {
    cin >> n;
    rep(i, 1, n) scanf("%d", &a[i].fi), a[i].se = i;
    sort(a + 1, a + n + 1);
    int su = 0; P mi(n, 0), ma(-1, 0);
    pair <int, P> as;
    rep(i, 1, n) {
        su += a[i].fi;
        mi = min(mi, a[i]), ma = max(ma, a[i]);
        if(su == i * (i - 1) / 2) {
            if(mi.se ^ ma.se) as = max(as, mp(ma.fi - mi.fi, mp(mi.se, ma.se)));
            mi.fi = n, ma.fi = -1;
        }
    }
    if(as.se.fi) printf("! %d %d\n", as.se.fi, as.se.se);
    else puts("! 0 0");
    fflush(stdout);
    return 0;
}