题解：P15499 [ICPC 2025 APC] Secret Lilies and Roses

Solwek · 2026-05-10 19:48:21 · 题解

下文钦定百合是 1，玫瑰是 0。

我们发现要回答的东西很奇怪，考虑找到一些性质把答案转化一下。

通过观察与手模，我们发现答案其实就是序列中 0 的个数！证明考虑设 0 的个数为 i，那么 r_i=n-i-(n-i-l_i)=l_i。那么我们只需要知道序列中有多少个 0 即可。

一个显然的思路是，我们随便找到一个位置 i，问一下 s_i 是 0 还是 1，如果是 0，那么我们问一下 l_ir_i,l_{i-1}r_{i-1}，因为 s_i=0，那么 l_{i-1}=l_i,r_{i-1}=r_i+1，此时容易计算出 l_i,r_i，也就容易算出 0 的个数，对于 s_i=1 也同理，但是这样会存在一个问题，就是 l_i 有可能等于 0，此时我们算不出 r_i 的值，我们需要找到一种结构使得不会出现这种情况。

我们发现 s_i=0,s_{i+1}=1 这样的结构就不会出现这种情况，我们只需要问一下 l_{i-1}r_{i-1},l_{i+1}r_{i+1} 就可以了。

所以我们只需要找到一个 s_i=0,s_{i+1}=1 的 i，考虑二分，我们钦定 s_{0}=0,s_{n+1}=1，那么每次算 [l,r] 时我们都保证 s_{l-1}=0,s_{r+1}=1，我们问一下 s_{mid} 是多少然后再往左或者右递归即可，当 l>r 时我们就找到了一个 i。

询问次数为 \lceil\log_2 n\rceil+2。

#include<bits/stdc++.h>
#define int long long
using namespace std;

int query(int x){
    cout<<"type "<<x<<'\n';
    fflush(stdout);
    string s;
    cin>>s;
    if(s[0]=='l')return 1;
    else return 0;
}
int mul(int x){
    cout<<"multi "<<x<<'\n';
    fflush(stdout);
    int y;
    cin>>y;
    return y;
}
void ans(int x){
    cout<<"answer "<<x<<'\n';
    fflush(stdout);
}
signed main(){
    int T;
    cin>>T;
    while(T--){
        int n;
        cin>>n;
        int l=1,r=n;
        while(l<=r){
            int mid=(l+r)/2;
            if(query(mid))r=mid-1;
            else l=mid+1;
        }
        swap(l,r);
        if(l==0)ans(mul(1));
        else if(r==n+1)ans(n-mul(n-1));
        else ans(l+mul(l+1)-mul(l-1));
    }
    return 0;
}