求助今年提高T2正确性!
  • 板块学术版
  • 楼主Solwek
  • 当前回复0
  • 已保存回复0
  • 发布时间2023/11/5 15:05
  • 上次更新2023/11/5 16:29:56
查看原帖
求助今年提高T2正确性!
684960
Solwek楼主2023/11/5 15:05

我是按照优先队列扩展的,WA了,想知道为什么不能这么做

#include<bits/stdc++.h>
#define int long long
using namespace std;

char s[2000010];
int mod=1e6+7;
int n;
vector<pair<int,int> >v[1000010];
struct node{
	int l,r;
	bool operator <(const node &cmp)const{
		if(r-l!=cmp.r-cmp.l)
			return r-l>cmp.r-cmp.l;
		return l>cmp.l;
	}
};
priority_queue<node>q;
int ql[2000010],qr[2000010];

int qwer(pair<int,int>x){
	return (x.first*137%mod+x.second*1137%mod)%mod;
}
void push(pair<int,int>x){
	v[qwer(x)].push_back(x);
}
int find(pair<int,int>x){
	int h=qwer(x);
	int len=v[h].size();
	for(int i=0;i<len;i++){
		if(v[h][i]==x){
			return 1;
		}
	}
	return 0;
}
void solve(){
	int ans=0;
	for(int i=1;i<n;i++){
		if(s[i]==s[i+1]){
			q.push({i,i+1});
			qr[i]=i+1;
			ql[i+1]=i;
		}
	}
	while(!q.empty()){
		node f=q.top();q.pop();
		if(!find({f.l,f.r}))ans++;
		else continue;
		cout<<f.l<<' '<<f.r<<'\n';
		push({f.l,f.r});	
		if(s[f.l-1]==s[f.r+1]&&f.l!=1&&f.r!=n){
			q.push({f.l-1,f.r+1});
			qr[f.l-1]=f.r+1;
			ql[f.r+1]=f.l-1;
		}
		if(qr[f.r+1]&&f.r!=n){
			q.push({f.l,qr[f.r+1]});
			qr[f.l]=qr[f.r+1];
			ql[qr[f.r+1]]=f.l;
		}
		if(ql[f.l-1]&&f.l!=1){
			q.push({ql[f.l-1],f.r});
			ql[f.r]=ql[f.l-1]; 
			qr[ql[f.l-1]]=f.r;
		} 
	}
	cout<<ans;
}
signed main(){
	freopen("game.in","r",stdin);
	freopen("game.out","w",stdout);
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>n>>s+1;
	solve();
	return 0;
} 
2023/11/5 15:05
加载中...