[UOJ#405/LOJ#2863][IOI2018]組合動作（互動）

Address

UOJ#405

LOJ#2863

Solution

第一次做互動題。

題意大概是給定一個未知的，由 A 、 B 、 X 、 Y 構成的長度為 N N N 的字元串 S S S ，每次可以給出一個長度不超過 4 N 4N 4N 的字元串 T T T ，查詢既是 T T T 的子串又是 S S S 的字首的最長字元串的長度。使用不超過 N + 2 N+2 N+2 次查詢，還原出字元串 S S S 。 S S S 的第一個字元不會出現多次。

（1）求 S S S 的第一個字元。

先查詢串 AB ，如果查詢結果不為 0 0 0 ，則 S [ 1 ] S[1] S[1] 為 A 或 B ，然後再查詢串 A ，如果查詢結果不為 0 0 0 則 S [ 1 ] S[1] S[1] 為 A 否則為 B 。如果查詢串 AB 的結果為 0 0 0 則 S [ 1 ] S[1] S[1] 為 X 或 Y 。同樣繼續查詢 X 進行判斷。

操作數為 2 2 2 。

（2）已知 S [ 1... i ] S[1...i] S[1...i] ，求 S [ 1... i + 1 ] S[1...i+1] S[1...i+1] （ i &lt; N − 1 i&lt;N-1 i<N−1 ）。

即确定 S [ i + 1 ] S[i+1] S[i+1] 。我們會發現，如果暴力判斷需要 2 2 2 次操作，下面需要使用一種隻使用 1 1 1 次操作的方法。

顯然，隻使用 1 1 1 次操作的關鍵是要通過查詢的結果把三種字元區分開。

構造字元串（以 S [ 1 ] = ′ Y ′ S[1]=&#x27;Y&#x27; S[1]=′Y′ 為例）：

S [ 1... i ] + ′ A ′ + ′ A ′ + S [ 1... i ] + ′ A ′ + ′ B ′ + S [ 1... i ] + ′ A ′ + ′ C ′ + S [ 1.. i ] + ′ B ′ S[1...i]+&#x27;A&#x27;+&#x27;A&#x27;+S[1...i]+&#x27;A&#x27;+&#x27;B&#x27;+S[1...i]+&#x27;A&#x27;+&#x27;C&#x27;+S[1..i]+&#x27;B&#x27; S[1...i]+′A′+′A′+S[1...i]+′A′+′B′+S[1...i]+′A′+′C′+S[1..i]+′B′

長度最多為 4 N − 1 4N-1 4N−1 。

易得，如果 S [ i + 1 ] = ′ A ′ S[i+1]=&#x27;A&#x27; S[i+1]=′A′ 則查詢結果為 i + 2 i+2 i+2 ，如果 S [ i + 1 ] = ′ B ′ S[i+1]=&#x27;B&#x27; S[i+1]=′B′ 則查詢結果為 i + 1 i+1 i+1 ，否則為 i i i 。

S [ 1 ] S[1] S[1] 為其他字元時同理。

總操作次數 N − 2 N-2 N−2 。

（3）求 S [ N ] S[N] S[N] 。

暴力枚舉。隻需要枚舉除 S [ 1 ] S[1] S[1] 之外的兩個字元。

當然和求 S[1] 一樣也可以

操作次數 2 2 2 。

這樣，總操作次數就是 N + 2 N+2 N+2 。

Code

#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include "combo.h"
#define For(i, a, b) for (i = a; i <= b; i++)

const char ch[] = {'A', 'B', 'X', 'Y'};

std::string add(std::string s, int l, int r)
{
	int i;
	For (i, l, r) s.push_back(ch[i]);
	return s;
}

std::string dda(std::string s, int l, int r)
{
	int i; std::string res = "";
	For (i, l, r) res += s, res.push_back(ch[i]);
	return res;
}

char inters(int x, int y)
{
	int i, pos = -1;
	For (i, 1, y)
	{
		pos++;
		if (pos == x) pos++;
	}
	return ch[pos];
}

std::string guess_sequence(int N)
{
	int i, firs, l = 0, r = 3;
	std::string st;
	For (i, 0, 1)
	{
		int mid = l + r >> 1;
		if (press(add(st, l, mid))) r = mid;
		else l = mid + 1;
	}
	firs = l; st.push_back(ch[l]);
	if (N == 1) return st;
	For (i, 1, N - 2)
	{
		int tmp = press(st + inters(firs, 1) + inters(firs, 1)
			+ st + inters(firs, 1) + inters(firs, 2)
			+ st + inters(firs, 1) + inters(firs, 3)
			+ st + inters(firs, 2));
		if (tmp == i + 2) st.push_back(inters(firs, 1));
		else if (tmp == i + 1) st.push_back(inters(firs, 2));
		else st.push_back(inters(firs, 3));
	}
	l = 0; r = 3;
	For (i, 0, 1)
	{
		int mid = l + r >> 1;
		if (press(dda(st, l, mid)) == N) r = mid;
		else l = mid + 1;
	}
	st.push_back(ch[l]);
	return st;
}