甘织玲奈子

神秘细节题，感觉自己思维路径和题解都不太相同。。。

容易发现这个删除长得很像括号序列，所以我们从括号序列开始想，我们的限制条件在相邻不能相同，所以我们考虑这个问题相当于是我把括号的端点放下去然后能够把一些相同的位置直接岔开，但是这还不够，我们每次放一个括号还强制地把括号两端的点碰到了一起，我们肯定是很讨厌这种情况的，所以括号序列所岔的两个颜色不准相同。

然后这个东西有一个匹配的结论是什么呢，无论括号序列，每次挑出两个颜色不同点把他们直接合并，合并的最大次数就是最后括号序列能够拼出来的最大括号对数。

这个东西可以用调整法证明，具体地先暴力跑一遍括号匹配，然后剩下的肯定是若干个颜色相同的点，那么我们可以把已匹配的区间按照左端点排序，枚举之后一个一个拆开，然后把最后剩下的点全部拉出来再跑一遍括号匹配，这样就可以碰到这个上界。

为什么这样拼回去的括号序列仍然合法呢，你考虑，假设有一个区间非法了，就只有两种可能，要么是你选的这个区间，他卡在这个区间左边，那么他就应该先被选取因为他拥有更小的左端点，卡在这个区间右边的话，考虑因为匹配长成这个样子，那么被我匹配的一定是某个区间的右端点，而左端点一定在我的左边，这个时候在最一开始我就会直接匹配上左端点而不会造出这么一个鬼畜的区间。

我们成功地证明了这个上界必然能够摸到，而构造就直接是证明，然后我们就愉快地做出了这个题。

代码一堆神秘细节。。

CPP

#include<bits/stdc++.h>
using namespace std;
int T,n;
int num[26];
int need[26][26];
priority_queue<int> Q[26];
bool cmp(pair<int,int> A,pair<int,int> B){
	return A.second-A.first+1<B.second-B.first+1;
}
int father[200005];
int find(int x){
	return father[x]==x?x:father[x]=find(father[x]);
}
class BIT{
	public:
	int c[200005];
	int lowbit(int x){
		return x&-x;
	}
	void add(int x,int y){
		while(x<=n){
			c[x]+=y;
			x+=lowbit(x);
		}
		return;
	}
	int ask(int x){
		int sum=0;
		while(x){
			sum+=c[x];
			x-=lowbit(x);
		}
		return sum;
	}
	void init(){
		for(int i=1;i<=n;i++){
			c[i]=lowbit(i);
		}
		return;
	}
}P;
void solve(){
	string S;
	cin>>S;
	n=S.size();
	S='?'+S;
	int ans=0;
	memset(num,0,sizeof(num));
	memset(need,0,sizeof(need));
	for(int i=2;i<=n;i++){
		if(S[i]==S[i-1]){
			num[S[i]-'a']++;
		}
	}
	priority_queue<pair<int,int>> q;
	int all=0;
	for(int i=0;i<26;i++){
		all+=num[i];
		q.push(make_pair(num[i],i));
	}
	while(q.top().first){ 
		pair<int,int> tmp1=q.top();
		q.pop();
		pair<int,int> tmp2=q.top();
		q.pop();
		tmp1.first--,tmp2.first--;
		if(tmp2.first>-1)need[tmp1.second][tmp2.second]++;
		q.push(tmp1),q.push(tmp2);
		ans++;
	}
	vector<pair<int,int>> A;
	for(int i=2;i<=n;i++){
		if(S[i]==S[i-1]){
			int pos=0;
			bool flg=false;
			for(int j=0;j<26;j++){
				if(j==S[i]-'a')continue;
				if(!Q[j].size())continue;
					pos=max(pos,Q[j].top());
//				}
			}
			if(pos){ 
				int j=S[pos]-'a';
				A.push_back(make_pair(Q[j].top(),i-1)); 
				Q[j].pop();
			}
			else{
				Q[S[i]-'a'].push(i);
			}
		}
	}
	int ruozhi=0;
	for(int i=0;i<26;i++){// 
		if(!Q[i].empty()){
			ruozhi=i+1;
			break;
		}
	}
	sort(A.begin(),A.end());
	if(ruozhi){//
		ruozhi--;
		vector<int> id;
		while(!Q[ruozhi].empty()){
			id.push_back(Q[ruozhi].top());
			Q[ruozhi].pop();
		}
		int need=id.size();
		vector<pair<int,int> > B=A;
		A.clear();
		for(int i=0;i<B.size();i++){
			int lt=A[i].first;
			int rt=A[i].second;
			int val=(S[lt]==ruozhi+'a')+(S[rt+1]==ruozhi+'a');
			if(need>0){
				need-=(2-2*val);
				id.push_back(lt);
				id.push_back(rt+1);
			}
			else{
				A.push_back(make_pair(lt,rt));
			}
		}
		sort(id.begin(),id.end());
		stack<int> stk;
		bool flg=false;
		for(int i=0;i<id.size();i++){
			int now=id[i];
			if(S[now]==ruozhi+'a'){
				if(stk.empty()){
					stk.push(now);
					flg=true;
				}
				else{
					if(flg){
						stk.push(now);
					}
					else{
						A.push_back(make_pair(stk.top(),now-1));
						stk.pop();
					}
				}
			}
			else{
				if(stk.empty()){
					stk.push(now);
					flg=false;
				}
				else{
					if(!flg){
						stk.push(now);
					}
					else{
						A.push_back(make_pair(stk.top(),now-1));
						stk.pop();
					}
				}
			}
		}
		while(!stk.empty()){
			A.push_back(make_pair(stk.top(),stk.top()));
			stk.pop();
		}
	}
	A.push_back(make_pair(1,n));
	sort(A.begin(),A.end(),cmp);
	for(int i=1;i<=n+1;i++)father[i]=i;
	P.init();
	vector<pair<int,int> > seta;
	for(int i=0;i<A.size();i++){ 
		int lt=A[i].first,rt=A[i].second;
		int now=find(lt);
		int L=P.ask(lt-1)+1;
		int R=P.ask(rt);
		if(L>R)continue;
		seta.push_back(make_pair(L,R));/
		string T="";
		while(now<=rt){
			T+=S[now];
			P.add(now,-1);
			father[now]=now+1;
			now=find(now);
		}
	}
	printf("%lu\n",seta.size());
	for(int i=0;i<seta.size();i++){
		printf("%d %d\n",seta[i].first,seta[i].second);
	}
	return;
}
int main(){
//	freopen("kristoff.in","r",stdin);
//	freopen("kristoff.out","w",stdout);
	scanf("%d",&T);
	while(T--)solve();
	return 0;
}

文章操作

相关推荐

评论

甘织玲奈子