UOJ405 【IOI2018】组合动作题解

题目链接：#405. 【IOI2018】组合动作

题意：

你在玩一个动作游戏。游戏控制器有 $4$ 个按键，A、B、X 和 Y。在游戏中，你用组合动作来赚金币。你可以依次按这些按键来完成一个组合动作。

这个游戏有一个隐藏的按键序列，可以表示为由这 $4$ 个字符组成的串 $S$。你并不知道这个串 $S$，但是你知道它的长度为 $N(1\le N \le 2000)$。

你还知道，$S$ 的首字符不会在串中重复出现。例如，$S$ 可以是”ABXYY“或者”XYYAA“，但不能是”AAAAA“或”BXYBX“。

你可以依次按最多 $4N$ 个按键来完成一个组合动作。串 $p$ 为你所按的按键序列。你用这个组合动作赚到的金币数量，等于同时为 $p$ 之子串和 $S$ 之前缀的最长字符串的长度。串 $t$ 的子串定义为 $t$ 中的连续字符序列 (可以为空)。$t$ 的前缀定义为 $t$ 的子串，其或者为空，或者包含 $t$ 的首字符。

例如，如果 $S$ 是 “ABXYY“，而 $p$ 是 “XXYYABYABXAY“，你会得到 $3$ 个金币，因为 “ABX“ 是可作为 $p$ 的子串的 $S$ 的前缀中最长的。

你的任务是，用少量的组合动作，找出隐藏字符串 $S$ 。

实现细节：

你需要实现下面的函数：
std::string guess_sequence(int N)
N：串 $S$ 的长度。

对每个测试用例，该函数被调用恰好一次。

该函数应返回串 $S$。

你的程序可以调用下面的函数：
int press(std::string p)
p：你的按键序列。

p 必须是长度为从 $0$ 到 $4N$ 的串 (包括 $0$ 和 $4N$)。p 的每个字符必须是 A、B、X 或者 Y。

对每个测试用例，你调用该函数的次数不能超过 $8000$ 次。

该函数的返回结果是，当按出按键序列 p 后你赚到的金币数量。

如果不满足上面的条件，你的程序将被判为 Wrong Answer。否则，你的程序将被判为 Accepted，而你的得分将根据 press 的调用次数来计算。

有趣的构造+交互题。

从首字母入手，先花 $2$ 次询问找到第一个字符 $c$ 。

为什么要找到它呢？因为它在隐藏串中只出现在第一个。

这意味着，不存在一个 $S$ 的子串第一个字符是 $c$

于是我们可以以 $c$ 为分隔符，构造出形如 PvPwuPwvPww 的询问串（ $c=$ P ，$u,v,w \ne c$ ）

这个串特殊在它可以直接得到下一个字符为 $u,v,w$ 中的哪一个

因为他们对应的返回值（金币数）为 $l,~l+1,~l+2$ 。

且询问串长 $4l+7 \le 4n$ 只需 $l \le n-2$ 。然后最后一个字符直接 $2$ 次问就好了。

于是询问数 $n+2$ 。

时间复杂度 $O(n^2)$

代码：（题目只要实现函数）

#include "combo.h"
#include <bits/stdc++.h>
using namespace std;

string guess_sequence(int n)
{
	char c = press("AB") ? (press("A") ? 'A' : 'B') : press("X") ? 'X' : 'Y';
    char rem[3] = {'A','B','X'};
	string res(1,c);
	if (n == 1) return res;
	for (int i=0; i<3; i++) rem[i] == c ? rem[i] = 'Y' : 0;
	for (int i=1; i<n-1; i++)
    {
		int j=press(res + rem[1] + res + rem[2] + rem[0] + res + rem[2] + rem[1] + res + rem[2] + rem[2]);
		res.push_back(rem[j - i]);
	}
	res.push_back(press(res + rem[0]) == n ? rem[0] : press(res + rem[1]) == n ? rem[1] : rem[2]);
	return res;
}