社区讨论

蓝屏

ooabaijnaw
学术版参与者 2已保存回复 2

讨论操作

快速查看讨论及其快照的属性，并进行相关操作。

当前回复
2 条
当前快照
1 份
快照标识符
@m3tdljf6
此快照首次捕获于
2024/11/23 07:31
去年
此快照最后确认于
2025/11/04 14:09
4 个月前
查看原帖
前情提要：昨天抽象ABC只切到E题。
一看E题，这不是个二分吗？打完，样例过，结果：RE，关键它显示我样例都RE了。
CPP
#include<bits/stdc++.h>
using namespace std;
int n,q,sum[100005][2];
string s;
vector<int>gang;
int main(){
	cin>>n>>q>>s;
	for(int i=1;i<=n;i++){
		sum[i][0]=sum[i-1][0];
		sum[i][1]=sum[i-1][1];
		if(s[i-1]=='1')sum[i][0]++;
		else if(s[i-1]=='2')sum[i][1]++;
		else gang.push_back(i);
	}
	while(q--){
		int l,r;
		cin>>l>>r;
		int lf=lower_bound(gang.begin(),gang.end(),l)-gang.begin(),rf=upper_bound(gang.begin(),gang.end(),r)-gang.begin()-1,ans;
		if(lf>rf){
			cout<<0<<endl;
			continue;
		}
		while(lf<=rf){
			int mid=(lf+rf)>>1,id=gang[mid];
			int ans1=sum[id][0]-sum[l-1][0],ans2=sum[r][1]-sum[id-1][1];
			if(ans1<=ans2)ans=mid,lf=mid+1;
			else rf=mid-1;
		}
		int lns=ans-1,rns=ans,nns=0;
		if(lns>=0){
			nns=max(nns,min(sum[gang[lns]][0]-sum[l-1][0],sum[r][1]-sum[gang[lns]-1][1]));
		}
		if(rns<gang.size()){
			nns=max(nns,min(sum[gang[rns]][0]-sum[l-1][0],sum[r][1]-sum[gang[rns]-1][1]));
		}
		cout<<nns*2+1<<endl;
	}
}
然后我用atcoderbetter运行了一下，只输出1，然后就RE了；
然后我在while(q--)循环里输出中间变量，然后就有输出了！但评测机只能过滤空格和换行。然后我在while(q--)循环里输出了\n，然后不RE了，第一个变成了1。最后我在while(q--)循环上面输出了\n，然后就过了！
AC代码:
CPP
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
using namespace std;
int n,q,sum[100005][2];
string s;
vector<int>gang;
int main(){
	cin>>n>>q>>s;
	for(int i=1;i<=n;i++){
		sum[i][0]=sum[i-1][0];
		sum[i][1]=sum[i-1][1];
		if(s[i-1]=='1')sum[i][0]++;
		else if(s[i-1]=='2')sum[i][1]++;
		else gang.push_back(i);
	}
    cout<<'\n';
	while(q--){
        cout<<'\n';
		int l,r;
		cin>>l>>r;
		int lf=lower_bound(gang.begin(),gang.end(),l)-gang.begin(),rf=upper_bound(gang.begin(),gang.end(),r)-gang.begin()-1,ans;
		if(lf>rf){
			cout<<0<<endl;
			continue;
		}
		while(lf<=rf){
			int mid=(lf+rf)>>1,id=gang[mid];
			int ans1=sum[id][0]-sum[l-1][0],ans2=sum[r][1]-sum[id-1][1];
			if(ans1<=ans2)ans=mid,lf=mid+1;
			else ans=mid,rf=mid-1;
		}
		int lns=ans-1,rns=ans+1,nns=0;
		if(lns>=0){
			nns=max(nns,min(sum[gang[lns]][0]-sum[l-1][0],sum[r][1]-sum[gang[lns]-1][1]));
		}
		if(ans<gang.size()){
			nns=max(nns,min(sum[gang[ans]][0]-sum[l-1][0],sum[r][1]-sum[gang[ans]-1][1]));
		}
		if(rns<gang.size()){
			nns=max(nns,min(sum[gang[rns]][0]-sum[l-1][0],sum[r][1]-sum[gang[rns]-1][1]));
		}
		cout<<nns*2+1<<endl;
	}
}
虽然用这种玄幻方式卡过去了，但蒟蒻想了一晚上都不知道为什么，求大佬解答！！

回复

共 2 条回复，欢迎继续交流。

正在加载回复...