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;
}