交互题就是让你的 ACM/OI 程序和 OJ 进行交互。与一般的 OJ 给一组输入,你的程序再根据输入给出输出不同的是,OJ 给的输入是根据你的程序即时生成的,作为你的询问的回答/操作以后的反馈。

一个题目链接

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
#include<bits/stdc++.h>
#define ld long double
#define ll long long

using namespace std;

inline bool ask(int a, int b, int c)
{
char ret[10];
cout << "? "<<a << " " << b << " " << c << "\n";
cout.flush();
cin >> ret;
return (strcmp(ret, "Yes") == 0);
}

int main()
{
srand(5436);
int n, k, d;
cin >> n >> k;
d = log(n*(k - 1) + 1) / log(k) + 0.01;
int la, lb;
multiset<int> ab;
while (ab.size() != 2 * d - 3)
{
ab.clear();
la = rand() % n + 1;
lb = rand() % n + 1;
for (int i = 1; i <= n; i++)
{
if (i == la || i == lb)
continue;
if (ask(la, i, lb))
{
ab.insert(i);
}
}
}
ab.insert(la);
ab.insert(lb);
int value[1505] = { 0 };
for (int a : ab)
for (int b : ab)
for (int c : ab)
value[b] += ask(a, b, c);
int ans, ansval = 0;
for (int a : ab)
if (ansval < value[a])
{
ansval = value[a];
ans = a;
}
cout << "! " << ans;
return 0;
}

需要注意的是,交互题中,你的程序进行输出的时候,需要 flush 你的输出,否则会导致 TLE。具体原理和程序的缓冲区有关,可以自行百度。

After printing each query do not forget to print end of line and flush the output. Otherwise you may get Idleness limit exceeded. To do this, use:

  • fflush(stdout) or cout.flush() in C++;
  • System.out.flush() in Java;
  • flush(output) in Pascal;
  • stdout.flush() in Python;
    See documentation for other languages.