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

题目链接：[https://www.luogu.com.cn/problem/P15499](P15499 [ICPC 2025 APC] Secret Lilies and Roses)

很厉害的一道题。

显然如果我们知道玫瑰的数量 $ m $，则回答 $ m $ 一定可行。考虑如何求出玫瑰的数量，一个可行的方案是找到一个连续的玫瑰-百合，设玫瑰的位置为 $ p $，则询问 multi(p) 和 multi(p+1)，记回答分别为 $ x, y $ 有玫瑰的数量等于 $ (y-x)+p-(x/(y-x)) $，但是显然这在 $ y=0 $，即位置 $ p $ 是最后一朵玫瑰的时候是错误的，那么我们询问 multi(p-1)，记回答为 $ z $，即为前 $ p-1 $ 个位置中百合的数量，因此有玫瑰的数量等于 $ p-1-z+1=p-z $。这里最多消耗三次询问。

考虑如何找到一个玫瑰-百合，我们假设位置 0 有一个玫瑰，位置 n+1 有一个百合，那么可以二分（这步很难想到！），当前 $ l, r $ 的值代表位置 $ l-1 $ 是一个玫瑰，位置 $ r+1 $ 是一个百合，每次询问 $ mid $ 的具体类别并替换可以替换的 $ l $ 或 $ r $。这里用了最多 $ \lceil \log_2n \rceil = 7 $ 次询问。

很明显这还是有问题的，如果找到的区间包含假设的玫瑰和百合那么久不成立了，但是注意到这意味着如果取到了最左边的区间那么有第一个位置是百合。取到最右边的区间那么有最后一个位置是玫瑰，都可以通过一次询问解决，具体见代码。

代码：

#include<bits/stdc++.h>
#define time(null) chrono::steady_clock::now().time_since_epoch().count()
#define int long long
#define uint unsigned long long
#define debug() cout<<"come here\n"
#define INF 0x3f3f3f3f3f3f3f3f
#define pii pair<int,int>
#define pb push_back
#define Code return
#define by 0
#define MCYYDS ;
using namespace std;
int qpow(int a,int b,int p=INF){int ret=1;while(b){if(b&1)ret=(ret*a)%p;a=(a*a)%p;b>>=1;}return ret;}
inline int read(){int ret=0,f=1;char ch=getchar();while(ch<'0'||ch>'9')f=(ch=='-'?-1:f),ch=getchar();while(ch>='0'&&ch<='9')ret=(ret<<3)+(ret<<1)+(ch^48),ch=getchar();return ret*f;}
inline void write(int x){if(x<0){putchar('-');write(-x);return ;}if(x>9)write(x/10);putchar((char)(x%10+48));}
inline void writech(int x,char ch){write(x);putchar(ch);}
bool typ(int x)
{cout<<"type "<<x<<endl;string s;cin>>s;return (s[0]=='l');
}
int mul(int x)
{cout<<"multi "<<x<<endl;int y;cin>>y;return y;
}
void ans(int x)
{cout<<"answer "<<x<<endl;return ;
}
signed main()
{
//	ios::sync_with_stdio(0);
//	cin.tie(0);
//	cout.tie(0);int T;cin>>T;while(T--){int n;cin>>n;int l=1,r=n;while(l<=r){int mid=l+r>>1;if(typ(mid))r=mid-1;else l=mid+1;}swap(l,r);if(l!=0&&r!=n+1){int x=mul(l),y=mul(r);int ri=y-x;if(ri==0){ans(l-mul(l-1));}else{int li=x/ri;ans(ri+l-li);}}else if(l==0){ans(mul(1));}else if(r==n+1){ans(n-mul(n-1));}}Code by MCYYDS
}