当前位置：网站首页>Guess the string (dichotomy, interaction)

Guess the string (dichotomy, interaction)

2022-07-19 06:06:00 【lovesickman】

Guess The String

Topic translation

This topic is interactive , Use IO Interaction .

After you output a line , Please empty the buffer ：

stay C++ in , Use fflush(stdout) or cout.flush().
stay Pascal in , Use flush(output).
stay Python in , Use stdout.flush().
Please consult the documentation for other languages .

Please follow the topic to complete the interaction , Sending an illegal inquiry may appear TLE,WA Other questions .

Given a length of $n$ A string that contains only lowercase letters $S$ , You need to guess it .

Altogether $4$ Two ways of interaction ：

Format	Number of calls allowed	Limit	Return value	explain
nothing	$1$	nothing	An integer , $n$ Value .	Call... At the beginning .
`? 1 i`	$26$	$i$ by $[1, n]$ Range of integers .	One character , $S_i$ （ $S$ Of the $i$ Characters ）.	nothing
`? 2 l r`	$\times 10^3$	$\le l \le r \le n$ , And $l, r$ Integers .	An integer , $S_{l \ldots r}$ （ $S$ Of the $l$ to $r$ Characters ） Different characters in Species .	nothing
`! s`	$1$	$s$ Is a string , Represents what you think $S$ .	（ Evaluation results ——AC or WA.）	Last call , Then stop the interaction .

about $100\%$ The data of , $\le n \le 10^3$ .

Examples #1

The sample input #1

5
4
u
2
g
e
s
1

Sample output #1

? 2 1 5
? 1 2
? 2 1 2
? 1 1
? 1 3
? 1 4
? 2 4 5
! guess

Analysis can be seen ： The time complexity must be $O (n l o g (26))$ , $l o g (26)$ Means yes 26 Some information of letters is bisected , And the information has two phases .

$i$ from $\sim n$ Cycle through , Yes $i = = 1$ Special judgement ,vector<int>v, Store the last occurrence of each letter , When you encounter elements you have encountered before , For all the letters that have appeared $v$ Do two points .

One thing to watch out for , $v e c t o r$ Subscript from 0 Start , String from 1 Start , Need to add a bit offset .

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6+7;
typedef long long ll;

// 2022-7-10 09:40:10

char query1(int i){
    
    cout<<"? 1 "<<i<<endl;
    char s;cin>>s;
    return s;
}

int query2(int l,int r){
    
    cout<<"? 2 "<<l<<" "<<r<<endl;
    int s;cin>>s;
    return s;
}
int n,cnt;
char ans[1010];
int node[30];
int main(){
    
    cin>>n;
    for(int i=1;i<=n;i++){
    
        if(i==1){
    
            char t = query1(i);
            ans[i] = t;
            cnt++;
            node[ans[i]-'a'] = i;
        }
        else{
    
            int t = query2(1,i);
            if(t == cnt+1){
                    
                char s = query1(i);
                ans[i] = s;
                cnt++;
                node[ans[i]-'a']=i;
            }
            else{
    // i The position character is the same as a previous character 
                vector<int>v;
                for(int i=0;i<26;i++){
    
                    if(node[i]){
    
                        v.push_back(node[i]);
                    }
                }
                sort(v.begin(),v.end());    
                
                int l = 0, r = v.size()-1;
                while(l<r){
    
                    int mid = l+r+1>>1;
                    if(query2(v[mid],i) == cnt-mid){
    
                        // cout<<"?"<<endl;
                        l = mid;
                    }
                        
                    else
                        r = mid-1;
                }
                ans[i] = ans[v[l]];
                node[ans[i]-'a']=i;
            }
        }
    }
    cout<<"! ";
    for(int i=1;i<=n;i++){
    
        cout<<ans[i];
    }
	return 0;
}