如果字符串里既有 o 又有 - ，那么答案就是最长 o 的长度，否则无解。
#include <bits/stdc++.h>
#define int long long
using namespace std;
int n;
string s;
signed main(){
cin>>n;
cin>>s;
bool O=false,_=false;
for(int i=0;i<n;++i){
if(s[i]=='o') O=true;
if(s[i]=='-') _=true;
}
if(!(O&&_)){
cout<<"-1\n";
return 0;
}
int a=0,ans=0;
for(int i=0;i<n;++i){
if(s[i]=='o') a++;
else a=0;
ans=max(ans,a);
}
cout<<ans<<"\n";
return 0;
}
看看这数据范围和询问次数，很快能猜到用二分。
初始范围是
- 如果 ，就把区间改为
- ，就把区间改为
交互题不要忘记刷新缓冲区！！！
（endl自动刷新缓冲区）
#include <bits/stdc++.h>
#define int long long
using namespace std;
int n;
int query(int q){
cout<<"?"<<q<<endl;
cin>>q;
return q;
}
signed main(){
cin>>n;
int l=1,r=n;
while(r-l > 1){
int mid=(l+r)/2;
int s=query(mid);
if(s) r=mid;
else l=mid;
}
cout<<"!"<<l<<endl;
return 0;
}
每个 都表示了距离 在 的点中不能有黑点。
数据范围比较小，直接暴力算距离，标记不允许染黑的点，最后判断是否有解就好了。
#include<bits/stdc++.h>
//#define int long long
using namespace std;
const int N=2005;
int n,m,k;
vector<int> e[N];
int dis[N][N],vis[N];
int p[N],d[N];
bool black[N];
queue<int> q;
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);
cin>>n>>m;
for(int i=1;i<=m;i++){
int u,v;
cin>>u>>v;
e[u].push_back(v);
e[v].push_back(u);
}
cin>>k;
for(int i=1;i<=k;++i){
cin>>p[i]>>d[i];
}
for(int i=1;i<=n;++i){
q.push(i);
vis[i]=i;
dis[i][i]=0;
while(!q.empty()){
int u=q.front();
q.pop();
for(auto v:e[u]){
if(vis[v]<i){
vis[v]=i;
dis[i][v]=dis[i][u]+1;
q.push(v);
}
}
}
}
for(int i=1;i<=n;i++)
black[i]=true;
for(int i=1;i<=k;i++){
for(int j=1;j<=n;++j){
if(dis[p[i]][j]<d[i]){
black[j]=false;
}
}
}
for(int i=1;i<=k;++i){
bool t=false;
for(int j=1;j<=n;++j){
if(black[j]==true&&dis[p[i]][j]==d[i]){
t=true;
break;
}
}
if(!t){
printf("No\n");
return 0;
}
}
cout<<"Yes\n";
for(int i=1;i<=n;++i){
cout<<black[i];
}
cout<<"\n";
return 0;
}