[CSP-J 2021] 小熊的果篮

题目

1

2

代码

#include <bits/stdc++.h>
using namespace std;
const int N=2e5+5;
struct node{
	int pre,//上一个水果块(对于水果就是上个水果)
		l,//块开始的序号，左边界 
		d,//块类型，0/1
		id,//水果序号 
		r,//块结束的序号，右边界 
		next;//下一块(下个水果)
	node(){d=-1;id=-1;};//空参数构造函数 
	node(int px,int lx,int vx,int rx,int nx){//构造水果块。
		//上一块，左边界，水果类型，右边界，下一块 
		pre=px,l=lx,d=vx,r=rx,next=nx;
	};
	node(int px,int idx,int nx){//构造一个水果
		//上一个水果，水果序号，下一个水果 
		pre=px,id=idx,next=nx;
	}; 
	bool isempty(){//判定块是否空了(已挑空该块水果) 
		if(l>r)return 1;
		else return 0;
	} 
}k[N],f[N];//N块,N水果 
int n,//水果数
	m=0;//块序号 
void view(int x){
	cout<<"果篮"<<x<<endl;
	for(int i=k[0].next;k[i].d!=-1;i=k[i].next){//遍历所有块 
		cout<<i<<"("<<k[i].d<<")";
		for(int j=k[i].l;j!=k[k[i].next].l;j=f[j].next)//遍历该块所有水果 
			cout<<f[j].id<<" ";cout<<"\t";
	}
	cout<<endl;
}
int main(){
	//freopen("data.cpp","r",stdin);
	int l=0,//左边界 
		r,//右边界 
		x=-1,//本块水果类型 
		x2;//后块水果类型 
	scanf("%d",&n);
	for(int i=1;i<=n+1;i++){//遍历所有水果。多循环一次,用以确认最后一块 
		if(i<=n)scanf("%d",&x2);
		else x2=-2;//最后一块,跟第一块-1不一样(全空后不合并)
		f[i]=node{i-1,i,i+1};//建立本水果(链表) 
		if(x!=x2){//本水果跟上一水果不一样，那前面就是一个块 
			r=i-1;//上一块的右边界 
			k[m]=node{m-1,l,x,r,m+1};//建立上一块(链表) 
			l=i,x=x2;//本块的左边界和水果类型 
			m+=1;//本块序号 
		}
	}
	k[m]=node{m-1,n+1,-2,n+1,m+1};//尾块
	//view(0);
	while(k[0].next!=m){//第一个空块的下一个不是最后一个空块就继续 
		for(int i=k[0].next;i!=m+1;i=k[i].next){//遍历所有块，包括最后一个空块 
			if(k[i].d!=-2){//非最后一个空块 
				//cout<<"输出"<<i<<"("<<k[i].v[0]<<")\n";
				cout<<f[k[i].l].id<<" ";//输出该块左边界对应水果序号 
				if(!k[i].isempty()){//非空就去掉第一个元素——左边界右移 
					f[f[k[i].l].pre].next=f[k[i].l].next;//左边界的上一水果的下一水果是左边界的下一水果 
					f[f[k[i].l].next].pre=f[k[i].l].pre;//左边界的下一水果的上一水果是左边界的上水果 
					k[i].l=f[k[i].l].next;//块的首水果变成水果的下一水果 
				}
			}
			int j=k[i].pre;//处理上一块 
			if(k[j].isempty()){//如果上一块空了，
				if(k[k[j].pre].d==k[k[j].next].d){//前后一样，合并。
					//合并后块到前块 
					k[k[j].pre].r=k[k[j].next].r;//上一块的右边界改成下一块的右边界水果 
					k[k[j].pre].next=k[k[j].next].next;//前块的后块是后块的后块 
					k[k[k[j].next].next].pre=k[j].pre;//后块的后块的前块是前块 
				}else{//前后不一样，续接上 
					k[k[j].pre].next=k[j].next;//前一个的下一个是自己下一个 
					k[k[j].next].pre=k[j].pre;//下一个的前一个是自己上一个 
				}
			}
			//view(i);
		}
		cout<<endl;
		//view();
	} 
	return 0;
}

思路

• 模拟按块取水果，并动态合并空块
• 双层双向链表。水果块和各水果
• 遍历所有块，并输出每块首水果。某块被取空，如果前后块一样就合并，否则续接
• 每个水果会被处理1次(O(n))，每个果篮会被处理1次(O(n)),能处理n=2e5的规模。

小结

链表还是很有趣，多操作，熟能生巧。
都在处理序号，不管块双向链表和水果双向链表。块的首个水果和尾水果跟水果的序号统一。