标签 交互 下的文章

「Codeforces 1174F」Ehab and the Big Finale

题目链接：Codeforces 1174F

这是一道交互题。

给定一棵有 $n$ 个点的树，节点 $1$ 为根节点。

我们选择一个隐藏节点 $x$，你需要进行以下三种操作来找到这个节点 $x$ 的编号。

• d u：你会得到节点 $u$ 和 $x$ 之间的距离。两个节点之间的距离定义为最短路径上的边数。
• s u：你会得到节点 $u$ 到 $x$ 的最短路径上的第二个节点。但是如果 $u$ 不是 $x$ 的祖先，你会直接得到 Wrong answer 的结果！
• ! u：回答隐藏节点 $x$ 的编号为 $u$。

你需要在 $36$ 次询问（不包括回答）内找到 $x$ 的编号。这个隐藏节点 $x$ 不会根据你的询问而改变。

数据范围：$2 \le n \le 2 \times 10 ^ 5$。

「Codeforces 1153E」Serval and Snake

题目链接：Codeforces 1153E

这是一道交互题。

Serval 在上学的途中，必须穿过一个池塘，池塘里面有一条危险的蛇。池塘可以用一张 $n \times n$ 的网格表示。蛇的头部和尾部在不同的格子里，它的身体是一串连接头部和尾部的格子，并且身体不会相交。Serval 碰到蛇就会有生命危险。

幸运的是，他有一个特殊的装置可以回答如下问题：你可以选择一个矩形，它会告诉你蛇身穿过矩形边界的次数。

你作为 Serval 的好朋友，请你在使用不超过 $2019$ 询问后帮 Serval 找到蛇头和蛇尾。注意：蛇不会随着询问而移动。

数据范围：$2 \le n \le 1000$。