G. Guess One Character 解析(思維)

今天我們來看看CF2038G 題目連結

題目描述

本題是一道交互題。系統預先固定了一個$01$字串$s$，其長度$n$滿足 $2 \le n \le 50$。
你必須在不超過3次查詢下，正確猜出$s$中至少一個位置的字符。

互動方式

• 查詢
  你可以發送查詢，格式為$1\ t$，其中$t$為一個長度介於1和$n$（含）之間、僅由字符0和1組成的字符串。查詢的回應是$t$作為連續子串在$s$中出現的次數（例如，若$s=111011$且$t=11$，則回應為 3）。

• 提交答案
  當你決定猜測某一字符時，應以格式$0\ i\ c$提交答案，其中$1 \le i \le n$且$c \in {0,1}$表示你認為$s_i = c$。如果答案正確，系統將回應1，否則回應-1並終止程序。

前言

我自己想的時候我真心認為必須要先$t=01$再$t=10$，因為如果這兩個的數量不一樣我們就一定知道的一個和最後一個字是什麼。
然而在這兩個的數量一樣的時候，死活找不到方法。

想法

我是看解答的，解答很簡單，三個步驟：

1. $t=1$
2. $t=11$
3. $t=10$

這個解法的原理是想要去看最後一位到底是$0$還是$1$。
由於最後一位如果是$1$的話，$t=10$就沒辦法統計到最後一位的$1$，而在此之前的“結尾$1$”都可以被$t=10$捕捉到。
而其他不是“結尾$1$”的$1$的數量都可以被$t=11$捕捉到。
所以如果$t=1$的數量等於$t=11$的數量加上$t=10$的數量，就代表結尾沒有$1$，因此結尾是$0$。
相反的狀況就是結尾是$1$。

程式碼:

const int _n = 1e5 + 10;
int t, n, m;
main(void) {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  cin >> t;
  while (t--) {
    cin >> n;
    int q1, q11, q10;
    cout << "1 1" << endl;
    cin >> q1;
    cout << "1 11" << endl;
    cin >> q11;
    cout << "1 10" << endl;
    cin >> q10;
    if (q1 == q11 + q10) {
      cout << "0 " << n << " 0" << endl;
    } else {
      cout << "0 " << n << " 1" << endl;
    }
    int res;
    cin >> res;
    if (res == -1) {
      return 0;
    }
  }
 
  return 0;
}

標頭、模板請點Submission看 Submission