社区讨论
求助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 条回复,欢迎继续交流。
正在加载回复...