交互与提答题选讲

gaochunzhen · 2023-01-17 11:44:37 · 个人记录

作业在这里

1. 交互题

交互题分为两种：IO 交互和函数式交互。

(1) IO 交互

选手需要通过输入输出与交互器进行交互。具体来说，选手将询问等操作通过标准输出进行输出，并从标准输入中读取反馈信息。

每次输出后需要刷新缓冲区。fflush(stdout) 或 std::cout << std::flush 可以实现该操作（使用 std::cout 也可以自动刷新缓冲区）。

下面举一个例子。

P1733 猜数（IO交互版）

评测机会在区间 [1,10^9] 中选择一个整数，你应该写一个代码来猜测它。你最多可以问评测机 50 个问题。

对于每一次询问，你可以向评测机询问区间 [1,10^9] 中的一个整数，评测机会返回:

• 0，如果它为答案（即评测机所选的数字），且程序应该在此之后停止询问。
• -1，如果它小于答案。
• 1，如果它大于答案。

每次询问，你需要向标准输出输出一个 [1,10^9] 中的整数，然后清空缓冲区。

然后你需要从标准输入中输入一个整数，代表评测机返回的结果。

相信大家已经一眼秒了，所以就直接放代码了。

#include <bits/stdc++.h>
using namespace std;
int l = 1, r = 1e9, mid, x;
int main() {
    while (1) {
        mid = (l + r) >> 1;
        printf("%d\n", mid);
        fflush(stdout);
        scanf("%d", &x);
        if (!x) return 0;
        else if (x == 1) r = mid - 1;
        else l = mid + 1;
    }
    return 0;
}

CF843B Interactive LowerBound

先来一道简单题练练手。

有一个由 n 个元素构成的数组，其构成了一个单项链表。每个数组元素 i 包含两个整数，\mathrm{val}_i 是元素的整数值，\mathrm{nxt}_i 是它所指向的元素，如果当前元素为最后一个元素则 \mathrm{nxt}_i=-1。保证 \mathrm{val}_i 递增。

给定链表的起点 \mathrm{st} 和一个数 x，你需要求出 \geq x 的最小的 \mathrm{val}_i。

你可以询问不超过 1999 次。每次询问如下：

• ? i —— 询问 \mathrm{val}_i 和 \mathrm{nxt}_i。