Two Houses | Codeforces 1498E

题目链接

有一张 \(n\) 个点的竞赛图。

不会给这张竞赛图,但会给每个点的入度 \(k_i\)

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

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

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

\(n \le 500\)

做法一

考虑一对点 \((u,v)\),由于是竞赛图,\(u,v\) 间有连边,不妨设 \(u \rightarrow 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\)

得到一个结论:如果一对点不双向可达,那么入度大的一定无法到达入度小的。

把所有点对按价值从大到小依次询问,每次询问入度大的能否到达入度小的,如果可以,就直接输出这一对。

如果到最后都没有回答“是”,那么输出无解。

复杂度 \(O(n^2)\)

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#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++)

using namespace std;
const int N = 1000;
char ch[N];
struct Qry {
int x, y, v;
bool operator <(const Qry& b)const { return v > b.v; }
} q[N * N];
vector <int> v[N];
int n, idx, k[N];
int main() {
scanf("%d", &n);
rep(i, 1, n) scanf("%d", &k[i]);
rep(i, 1, n) rep(j, i + 1, n)
q[++idx] = k[i] < k[j] ? (Qry){ j, i, k[j] - k[i] } : (Qry){ i, j, k[i] - k[j] };
sort(q + 1, q + idx + 1);
rep(i, 1, idx) {
printf("? %d %d\n", q[i].x, q[i].y);
fflush(stdout);
scanf("%s", ch);
if(ch[0] == 'Y') printf("! %d %d\n", q[i].x, q[i].y), fflush(stdout), exit(0);
}
puts("! 0 0"), fflush(stdout);
return 0;
}

做法二

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

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

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

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#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;
}