交互題

有一個(gè)長為$N$的由$A,B,X,Y$組成的字符串$S$，其中首字母不會(huì)重復(fù)出現(xiàn)。給定$N$，求$S$，可以詢問一個(gè)字符串的最長的為$S$前綴的子串長度，詢問次數(shù)不超過$N+2$即為滿分，詢問串長度不超過$4N$。

$$1\le N\le2000$$

考慮先$2$次問出首字母，則之后可以用首字母作“分隔符”，然后考慮每個(gè)字符依次詢問。

對(duì)于第$2$到第$N-1$個(gè)字符，設(shè)當(dāng)前答案串為$T$，三個(gè)不是首字母的字符分別為$p,q,r$，則如果詢問$TpTqpTqqTqr$，則可以根據(jù)返回值的不同確定當(dāng)前字符，最后用$2$次詢問問出第$N$個(gè)字符即可。

1 const std::string C[4] = {"A", "B", "X", "Y"}; 2 3 std::string guess_sequence(int N) { 4 int first = press("AB") ? press("B") : press("Y") + 2; 5 std::string answer = C[first]; 6 int x, y, z, cur = 0; 7 FOR(j, 0, 4) { 8 if (j == first) { 9 continue; 10 } 11 ++ cur; 12 switch (cur) { 13 case 1: 14 x = j; 15 break; 16 case 2: 17 y = j; 18 break; 19 case 3: 20 z = j; 21 break; 22 } 23 } 24 FOR(i, 2, N) { 25 int result = press(answer + C[x] + answer + C[y] + C[x] + answer + C[y] + C[y] + answer + C[y] + C[z]); 26 if (result == i - 1) { 27 answer += C[z]; 28 } else if (result == i) { 29 answer += C[x]; 30 } else { 31 answer += C[y]; 32 } 33 } 34 if (N != 1) { 35 if (press(answer + C[x]) == N) { 36 answer += C[x]; 37 } else if (press(answer + C[y]) == N) { 38 answer += C[y]; 39 } else { 40 answer += C[z]; 41 } 42 } 43 return answer; 44 }

?

轉(zhuǎn)載于:https://www.cnblogs.com/sjkmost/p/10357739.html

總結(jié)

以上是生活随笔為你收集整理的UOJ 405(IOI2018 D1T1)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。