Znzryb's Blog
0%

CF-1004-D. Object Identification

Posted on Edited on

思路讲解

没有在X中的一点，任何一个点都到达不了，因为在有向图中你不发出边是到达不了任何点的

如果所有点都在X中，那么就选择一个q1（X[i]==1 时的i），一个q2（X[i]==N 时的i），他们的曼哈顿距离≥N-1

但是在这个只有N条边的有向图上，你觉得q1到q2以及q2到q1的有向图路径都大于N-1嘛？显然不可能吧，没那么多边呀，借此就可以判断是有向图还是坐标了。

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
else {  // 这种情况难搞一点
    // 因为这种情况理论上来说甚至有可能每个点之间都相互联通在有向图上
    // 但我们可以利用曼哈顿距离的特性来解决
    ll q1=0, q2=0;
    FOR(i, 1, N) {
      if (X[i] == 1)
        q1 = i;
      else if (X[i] == N)
        q2 = i;
    }
    cout << "? " << q1 << ' ' << q2 << endl;
    ll dis1, dis2;
    cin >> dis1;
    if (dis1 < N - 1) {  // dis1比最小曼哈顿距离都小，肯定也不对
      cout << "! A" << endl;
      return true;
    }
    cout << "? " << q2 << ' ' << q1 << endl;
    cin >> dis2;
    if (dis2 < N - 1) {  // dis2比最小曼哈顿距离都小，肯定也不对
      cout << "! A" << endl;
      return true;
    }
    cout << "! B" << endl;
  }

AC代码

AC

https://codeforces.com/contest/2067/submission/305909277

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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
// Problem: D. Object Identification
// Contest: Codeforces - Codeforces Round 1004 (Div. 2)
// URL: https://codeforces.com/contest/2067/problem/D
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// by znzryb
//
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)
#define all(x) x.begin(), x.end()
#define CLR(i, a) memset(i, a, sizeof(i))
#define fi first
#define se second
#define pb push_back
#define SZ(a) ((int)a.size())
#define LOCAL

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> pll;
typedef array<ll, 3> arr;
typedef double DB;
typedef pair<DB, DB> pdd;
constexpr ll MAXN = static_cast<ll>(2e5) + 10, INF = static_cast<ll>(5e18) + 3;

ll N, T, X[MAXN];
bool vis[MAXN];

inline bool solve() {
  cin >> N;
  if (N == -1) {
    return false;
  }
  FOR(i, 1, N) { vis[i] = false; }
  FOR(i, 1, N) {
    cin >> X[i];
    vis[X[i]] = true;
  }
  vector<ll> disN;  // 没有在X中出现的点
  ll app;           // 随便取一个出现过的点
  FOR(i, 1, N) {
    if (!vis[i])
      disN.pb(i);
    else
      app = i;
  }
  if (SZ(disN) >= 1) {
    // 没有在X中的一点，任何一个点都到达不了，因为在有向图中你不发出边是到达不了任何点的
    cout << "? " << disN[0] << ' ' << app << endl;
    ll dis;
    cin >> dis;
    if (dis == 0)
      cout << "! A" << endl;
    else
      cout << "! B" << endl;
  } else {  // 这种情况难搞一点
    // 因为这种情况理论上来说甚至有可能每个点之间都相互联通在有向图上
    // 但我们可以利用曼哈顿距离的特性来解决
    ll q1=0, q2=0;
    FOR(i, 1, N) {
      if (X[i] == 1)
        q1 = i;
      else if (X[i] == N)
        q2 = i;
    }
    cout << "? " << q1 << ' ' << q2 << endl;
    ll dis1, dis2;
    cin >> dis1;
    if (dis1 < N - 1) {  // dis1比最小曼哈顿距离都小，肯定也不对
      cout << "! A" << endl;
      return true;
    }
    cout << "? " << q2 << ' ' << q1 << endl;
    cin >> dis2;
    if (dis2 < N - 1) {  // dis2比最小曼哈顿距离都小，肯定也不对
      cout << "! A" << endl;
      return true;
    }
    cout << "! B" << endl;
  }
  return true;
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  cin >> T;
  while (T--) {
    bool flag = solve();
    if (!flag) return 0;
  }
  return 0;
}
/*
AC
https://codeforces.com/contest/2067/submission/305909277
*/

心路历程（WA，TLE，MLE……）