社区讨论

求助C题

灌水区参与者 3已保存回复 3

讨论操作

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

当前回复
3 条
当前快照
1 份
快照标识符
@lo22iulk
此快照首次捕获于
2023/10/23 06:56
2 年前
此快照最后确认于
2023/11/03 07:17
2 年前
查看原帖
写了个离谱代码
CPP
#include<bits/stdc++.h>
#define int long long
using namespace std;
map<pair<int,int>,bool>mp;
string st;
int t,l[200001],n,ans,r[200001],cnt,len,x,y;
bool b[200001];
int ss(int p){
	int as,lpos=1,rpos=cnt;
	while(lpos<=rpos){
		int mid=(lpos+rpos)>>1;
		if(p>=l[mid])as=mid,lpos=mid+1;
		else rpos=mid-1;
	}
	return as;
}
signed main(){
	cin>>t;
	while(t--){
		mp.clear();
		cin>>len>>n;
		cin>>st;
		memset(l,0,sizeof l);
		memset(r,0,sizeof r);
		memset(b,0,sizeof b);
		cnt=ans=0;
		int now=0;
		while(now<len){
			x=now;
			while(st[now+1]==st[now]&&now+1<len)now++;
			l[++cnt]=x;
			r[cnt]=now;
			now++;
		}
		bool bb=0;
			mp.clear();
		while(n--){
			cin>>x>>y;
			x--,y--;
			int xx=ss(x),yy=ss(y);
			if(xx==yy){
				if(!bb)ans++,bb=1;
				continue;
			}
			if(st[l[xx]]=='0'){
				if(st[l[yy]]=='0'){
					if(!mp[make_pair(xx+1,yy)])mp[make_pair(xx+1,yy)]=1,ans++;
				}
				else{
					if(xx+1<yy){
						if(!mp[make_pair(xx+1,yy)])mp[make_pair(xx+1,yy)]=1,ans++;
					}
					else{
						if(!bb)ans++,bb=1;
						continue;
					}
				}
			}
			else{
				if(st[l[yy]]=='0'){
					if(!b[y]&&!(y==r[yy]&&mp[make_pair(xx,yy)])){
						b[y]=1,ans++;
						if(y==r[yy])mp[make_pair(xx,yy)]=1;
					}
				}
				else{
					if(!mp[make_pair(xx,yy-1)])mp[make_pair(xx,yy-1)]=1,ans++;
				}
			}
		}
		cout<<ans<<endl;
	}
	return 0;
}

回复

3 条回复,欢迎继续交流。

正在加载回复...