【题解】【模拟】—— [CSP-J 2021] 小熊的果篮
前置知识:双向链表,并查集
[CSP-J 2021] 小熊的果篮
戳我查看题目(洛谷)
题目描述
小熊的水果店里摆放着一排 n n n 个水果。每个水果只可能是苹果或桔子,从左到右依次用正整数 1 , 2 , … , n 1, 2, \ldots, n 1,2,…,n 编号。连续排在一起的同一种水果称为一个“块”。小熊要把这一排水果挑到若干个果篮里,具体方法是:每次都把每一个“块”中最左边的水果同时挑出,组成一个果篮。重复这一操作,直至水果用完。注意,每次挑完一个果篮后,“块”可能会发生变化。比如两个苹果“块”之间的唯一桔子被挑走后,两个苹果“块”就变成了一个“块”。请帮小熊计算每个果篮里包含的水果。
输入格式
第一行,包含一个正整数 n n n,表示水果的数量。
第二行,包含 n n n 个空格分隔的整数,其中第 i i i 个数表示编号为 i i i 的水果的种类, 1 1 1 代表苹果, 0 0 0 代表桔子。
输出格式
输出若干行。
第 i i i 行表示第 i i i 次挑出的水果组成的果篮。从小到大排序输出该果篮中所有水果的编号,每两个编号之间用一个空格分隔。
输入输出样例
输入 #1
12
1 1 0 0 1 1 1 0 1 1 0 0
输出 #1
1 3 5 8 9 11
2 4 6 12
7
10
输入 #2
20
1 1 1 1 0 0 0 1 1 1 0 0 1 0 1 1 0 0 0 0
输出 #2
1 5 8 11 13 14 15 17
2 6 9 12 16 18
3 7 10 19
4 20
输入 #3
见附件中的 fruit/fruit3.in。
输出 #3
见附件中的 fruit/fruit3.ans。
提示
【样例解释 #1】
这是第一组数据的样例说明。
所有水果一开始的情况是 [ 1 , 1 , 0 , 0 , 1 , 1 , 1 , 0 , 1 , 1 , 0 , 0 ] [1, 1, 0, 0, 1, 1, 1, 0, 1, 1, 0, 0] [1,1,0,0,1,1,1,0,1,1,0,0],一共有 6 6 6 个块。
在第一次挑水果组成果篮的过程中,编号为 1 , 3 , 5 , 8 , 9 , 11 1, 3, 5, 8, 9, 11 1,3,5,8,9,11 的水果被挑了出来。
之后剩下的水果是 [ 1 , 0 , 1 , 1 , 1 , 0 ] [1, 0, 1, 1, 1, 0] [1,0,1,1,1,0],一共 4 4 4 个块。
在第二次挑水果组成果篮的过程中,编号为 2 , 4 , 6 , 12 2, 4, 6, 12 2,4,6,12 的水果被挑了出来。
之后剩下的水果是 [ 1 , 1 ] [1, 1] [1,1],只有 1 1 1 个块。
在第三次挑水果组成果篮的过程中,编号为 7 7 7 的水果被挑了出来。
最后剩下的水果是 [ 1 ] [1] [1],只有 1 1 1 个块。
在第四次挑水果组成果篮的过程中,编号为 10 10 10 的水果被挑了出来。
【数据范围】
对于 10 % 10 \% 10% 的数据, n ≤ 5 n \le 5 n≤5。
对于 30 % 30 \% 30% 的数据, n ≤ 1000 n \le 1000 n≤1000。
对于 70 % 70 \% 70% 的数据, n ≤ 50000 n \le 50000 n≤50000。
对于 100 % 100 \% 100% 的数据, 1 ≤ n ≤ 2 × 10 5 1 \le n \le 2 \times {10}^5 1≤n≤2×105。
【提示】
由于数据规模较大,建议 C/C++ 选手使用 scanf
和 printf
语句输入、输出。
思路1.数组模拟(70分)
1.1.题意解析
这道题看上去非常简单,直接使用数组模拟就行了。可是它难就难在单纯使用数组来维护会达到 O ( N 2 ) O(N^2) O(N2)的时间复杂度,铁定超时。如下:
虽然不是正解,但我还是贴出来,给大家提供一种思路。
1.2.参考代码
#include<bits/stdc++.h>
using namespace std;
int main()
{//用数组a存储水果的种类,flag[i]存储i号水果是否被取出int n,a[200010]={},flag[200010]={},cnt=0,prev,is_take=0;scanf("%d",&n);for(int i=1;i<=n;i++)scanf("%d",&a[i]);while(cnt<n)//用cnt统计被取出的水果的个数 {is_take=0;//用is_take存储第一个块头是否被取出 for(int i=1;i<=n;i++){if(flag[i])continue;//如果这个水果已经被取出了,跳出 if(!is_take)//如果是第一个没有被取出的水果 {is_take=1;//初始化状态 prev=!a[i];}if(a[i]!=prev)//如果是新的一块,取出块头 {flag[i]=1;prev=a[i];cnt++;printf("%d ",i);}}printf("\n");//输出换行 }return 0;
}
思路2.双向链表模拟(60分)
2.1.题意解析
既然使用数组模拟会超时,那我们可不可以换一种数据结构呢?对了!我们可以使用双向链表来模拟。
一个基础的双向链表如下:
首先定义一个结构体node
,用来储存每个节点的信息,如下:
struct node//储存每一个节点的信息
{int kind,prev,next;node(int _kind=0,int _prev=0,int _next=0):kind(_kind),prev(_prev),next(_next){}
}l[MAXN];
同时定义一个数组l
,用来模拟双向链表。这里有一个小技巧:令l[0]
永远为表头。
然后定义一个变量cnt
,用来记录双向链表l
的长度和最后一个位置。
接下来,我们需要分装两个基础的函数:插入和删除,具体操作如下:
void insert_back(int x,int kind)//插入节点的函数
{int now=x;l[++cnt]=node(kind,now,l[x].next);//增加编号为cnt新节点 if(l[x].next)l[l[x].next].prev=cnt;//x后面有节点,前驱元素改为此节点l[x].next=cnt;//x的后驱节点改为此节点
}
void del(int x)//删除节点的函数
{int prv=l[x].prev,nxt=l[x].next;//取出x的前驱元素和后驱元素if(nxt)l[nxt].prev=prv;//x后面有节点,和x的前驱元素连接l[prv].next=nxt;//x的前驱元素和后驱元素连接cnt--;//长度减一
}
然后就是遍历整个双向链表。使用一个变量now
记录当前枚举到的节点。如果当前节点是一个块的开头(即和上一个节点的品种不一样),那么就取出。否则就now=l[now].next
。注意:要先取出第一个节点。
但这其实根遍历数组没有太大的本质区别,甚至比用数组模拟的分还要低 ,时间复杂度还是 O ( n 2 ) O(n^2) O(n2)。如下:
2.2.参考代码
#include<bits/stdc++.h>
using namespace std;
#define MAXN 200010
struct node//储存每一个节点的信息
{int kind,prev,next;node(int _kind=0,int _prev=0,int _next=0):kind(_kind),prev(_prev),next(_next){}
}l[MAXN];
int cnt,n;
void insert_back(int x,int kind)//插入节点的函数
{int now=x;l[++cnt]=node(kind,now,l[x].next);//增加编号为cnt新节点 if(l[x].next)l[l[x].next].prev=cnt;//x后面有节点,前驱元素改为此节点l[x].next=cnt;//x的后驱节点改为此节点
}
void del(int x)//删除节点的函数
{int prv=l[x].prev,nxt=l[x].next;//取出x的前驱元素和后驱元素if(nxt)l[nxt].prev=prv;//x后面有节点,和x的前驱元素连接l[prv].next=nxt;//x的前驱元素和后驱元素连接cnt--;//长度减一
}
int main()
{scanf("%d",&n);for(int i=1,prev=0;i<=n;i++)//初始化 {int kind;scanf("%d",&kind);insert_back(prev,kind);prev=i;}while(cnt){printf("%d ",l[0].next);if(cnt==1)break;int now=l[l[0].next].next,prev=l[l[0].next].kind;del(l[0].next);//第一个元素总要取出while(now)//遍历链表{if(l[now].kind!=prev)//块头,取出 {prev=!prev;int nxt=l[now].next;printf("%d ",now); del(now);now=nxt;}else now=l[now].next;}puts("");}return 0;
}
解法1.双向链表模拟优化
3.1.题意解析
既然以上的双向链表还是遍历每个节点,呢我可不可以优化一下,使得双向链表只遍历每个块呢?
当然可以,定义一个可变数组head
,用来存储每个块的块头。并在输入时预处理。在遍历时直接把块头节点输出并删除。
但是现在就有了一个难点:怎么样判定下一个节点会不会成为一个块的新块头呢?
如果一个块头被取出,它后面的点成了块头,那么它一定具有以下两个特征。
1.
l[t].kind==l[l[t].next].kind
。此节点和此节点的下一个种类一样,即是当前块的新块头;
2.l[t].kind!=l[l[t].prev].kind
,此节点和上一个节点种类不一样,即不会被上一个块合并。
注意:
1.新块头要先用临时数组tmp
存储,以免对当前遍历造成影响。
2.如果head
数组空了,跳出循环。
3.2.AC代码
#include<bits/stdc++.h>
using namespace std;
#define MAXN 200010
struct node//储存每一个节点的信息
{int kind,prev,next;node(int _kind=-1,int _prev=0,int _next=0):kind(_kind),prev(_prev),next(_next){}//结构体初始化函数
}l[MAXN];//双向链表
int cnt,n;
void insert_back(int x,int kind)//在节点x后面插入值为kind的节点的函数
{l[++cnt]=node(kind,x,l[x].next);//增加编号为cnt新节点if(l[x].next)l[l[x].next].prev=cnt;//x后面有节点,前驱元素改为此节点 l[x].next=cnt;//x的后驱节点改为此节点
}
void del(int x)//删除节点x的函数
{int prv=l[x].prev,nxt=l[x].next;//取出x的前驱元素和后驱元素if(nxt)l[nxt].prev=prv;//x后面有节点,和x的前驱元素连接l[prv].next=nxt;//x的前驱元素和后驱元素连接
}
int main()
{scanf("%d",&n);int prev;//记录上一个节点的种类vector<int>head(1,1);//初始化,第一个节点绝对是块头 for(int i=1;i<=n;i++){int kind;scanf("%d",&kind);insert_back(i-1,kind);//插入链表if(i==1)prev=kind;//初始化else if(kind!=prev)//如果是新的块{head.push_back(i);//新增一个块头prev=!prev;//状态取反}}while(!head.empty())//只要还有待取出的块头就继续循环{vector<int>tmp;//暂时储存下一轮的块头for(int i=0;i<head.size();i++)//循环取出{int t=head[i];//先取出当前块头printf("%d ",t);//输出del(t);//删除节点t/*如果此节点和此节点的下一个种类一样(即是当前块的新块头),且此节点和上一个节点种类不一样(即不会被上一个块合并),那么就是新块头*/if(l[t].kind==l[l[t].next].kind&&l[t].kind!=l[l[t].prev].kind)tmp.push_back(l[t].next);}head=tmp;//赋值puts("");}return 0;
}
解法2.并查集
4.1.题意解析
这道题还可以使用并查集来做,如果不会的同学可以自行上网搜索。或者看看这一篇。目前只需要了解其原理就行了,代码实现在底下有。
在删除一个数之后,我们将 这个数 这个数 这个数与 这个数 − 1 这个数-1 这个数−1相连。就形成了一些树。在删除块头的时候,这个块头所在的树的祖先节点,也就是根节点,就是下一个没有被删除的块头。如果不理解的话可以自己画一下图带入一下数据。
定义一个数组head
,储存每个块的块头。定义一个数组size
,储存每个块的大小。定义一个数组fa
,fa[i]
代表i
所属的数的代表(根节点)。最后定义一个变量sum_void
,储存当前连续被取空的块的个数(原因请看下面)。
现在还有一个问题,什么情况下需要新建一个块呢?
1.这一个块不会在这一轮被取光(不然就没有意义了);
2.这是第一个块,或者说当前新块的个数为0;
3.前一个块不会在这一轮被取空(不会导致和上一个块合并);
4.前面被取空的块的个数为偶数(和上一个同理)。
最后附上并查集的模版
int find(int x)//寻找x家族的代表,顺便进行路径压缩
{if(fa[x]==x)return x;//代表就是本人,返回 return fa[x]=find(fa[x]);//路径压缩
}
void join(int c1,int c2)//合并两个集合
{int f1=find(c1),f2=find(c2);//找到两个元素的代表 if(f1<f2)swap(f1,f2);//如果f1更小就交换 fa[f2]=f1;//修改代表
}
注:此思路是我借鉴的洛谷上一位大佬的思路发现的,请见谅。
4.2.AC代码
#include<bits/stdc++.h>
using namespace std;
#define MAXN 200010
int n,a[MAXN],size[MAXN],head[MAXN],fa[MAXN],sum,cnt=1,sum_void;
/*用size储存每个块的大小,head储存要取出来的的一个水果,fa储存每个块的代表cnt储存块的个数,sum_void储存上一个连续的取完的块的个数*/
int size2[MAXN],head2[MAXN],cnt2;//临时存储
int find(int x)//寻找x家族的代表,顺便进行路径压缩
{if(fa[x]==x)return x;//代表就是本人,返回 return fa[x]=find(fa[x]);//路径压缩
}
void join(int c1,int c2)//合并两个集合
{int f1=find(c1),f2=find(c2);//找到两个元素的代表 if(f1<f2)swap(f1,f2);//如果f1更小就交换 fa[f2]=f1;//修改代表
}
int main()
{scanf("%d",&n);for(int i=1;i<=n;i++)//读入并预处理scanf("%d",&a[i]),fa[i]=i;size[1]=1,head[1]=1;//将1号水果放进果篮里for(int i=2;i<=n;i++)//将2到n号水果放进果篮里 {if(a[i]!=a[i-1])head[++cnt]=i;//此元素与上一个元素不一样,新增一个块 size[cnt]++;//此块的大小加一 }while(sum<n)//循环直到取出n个元素 {for(int i=1;i<=cnt;i++)//将每一个块头和它前一个元素连接,方便查找 printf("%d ",head[i]),join(head[i]-1,head[i]);printf("\n");sum+=cnt;//取出cnt块 cnt2=sum_void=0;//赋初值 for(int i=1;i<=cnt;i++)//处理每个块 {if(size[i]>1)//如果这个块不会在这一轮被取光 {//第一个块或者前一个块有元素或者前面连续的被取空的块有偶数个 if(cnt2==0||size[i-1]>1||sum_void%2==0)head2[++cnt2]=find(head[i])+1,size2[cnt2]=0;//新建一个块 size2[cnt2]+=size[i]-1;//这个块的大小是上一个块减一 sum_void=0;//连续的空的块的个数清零 }else sum_void++;//否则就是空的块 }cnt=cnt2;//更新块的个数 for(int i=1;i<=cnt;i++)//更新每一个块的大小和块头 size[i]=size2[i],head[i]=head2[i];}return 0;
}
5.结尾语
其实这道题还可以用许多数据结构维护,比如vector
,queue
,set
,线段树等。是一道很好的练习数据结构的题。但由于篇幅关系就只给大家讲这么多了。感兴趣的话可以自行上网查询。
喜欢就订阅此专辑吧!
【蓝胖子编程教育简介】
蓝胖子编程教育,是一家面向青少年的编程教育平台。平台为全国青少年提供最专业的编程教育服务,包括提供最新最详细的编程相关资讯、最专业的竞赛指导、最合理的课程规划等。本平台利用趣味性和互动性强的教学方式,旨在激发孩子们对编程的兴趣,培养他们的逻辑思维能力和创造力,让孩子们在轻松愉快的氛围中掌握编程知识,为未来科技人才的培养奠定坚实基础。
欢迎扫码关注蓝胖子编程教育