P7912 [CSP-J 2021] 小熊的果篮 个人题解

P7912 [CSP-J 2021] 小熊的果篮此篇仅为记录我的思考防止我以后忘记如果能对你产生帮助荣幸之至题目描述小熊的水果店里摆放着一排n{ n }n个水果。每个水果只可能是苹果或桔子从左到右依次用正整数1,2,…,n{1,2,…,n}1,2,…,n编号。连续排在一起的同一种水果称为一个“块”。小熊要把这一排水果挑到若干个果篮里具体方法是每次都把每一个“块”中最左边的水果同时挑出组成一个果篮。重复这一操作直至水果用完。注意每次挑完一个果篮后“块”可能会发生变化。比如两个苹果“块”之间的唯一桔子被挑走后两个苹果“块”就变成了一个“块”。请帮小熊计算每个果篮里包含的水果。输入格式第一行包含一个正整数n{ n }n表示水果的数量。第二行包含n{ n }n个空格分隔的整数其中第i{ i }i个数表示编号为i{ i }i的水果的种类1 代表苹果0 代表桔子。输出格式输出若干行。第i{ i }i行表示第i{ i }i次挑出的水果组成的果篮。从小到大排序输出该果篮中所有水果的编号每两个编号之间用一个空格分隔。输入输出样例输入 112110011101100输出 1135891124612710输入 22011110001110010110000输出 21581113141517269121618371019420数据范围对于100%{ 100 \% }100%的数据1≤n≤2×105{1 \le n \le 2×10^5}1≤n≤2×105个人解析前备知识点静态链表的实现静态链表速度更快、内存可控、无指针风险、自定义灵活无容器开销在大数据量链表题里稳定不超时是信奥最优选择。1.定义纯数组实现代码如下constintN1e5100;//数组上限intdata[N];//存数据此处数据类型使用intintnxt[N];//存下一个元素下标inthead,cnt,tail;//head存第一个元素下标cnt存非空数据的最后一个下标tail存最后一个元素下标可以用head{\text{head}}head或nxt[0]{\text{nxt[0]}}nxt[0]存链表中的第一个元素下标。cnt{\text{cnt}}cnt通过存非空数据的最后一个下标来记录数组中空的位置有哪些也就是说数组中下标大于cnt{\text{cnt}}cnt的位置都属于空的位置tail{\text{tail}}tail存链表中的最后一个元素下标。如果第000个元素默认不用那么就可以将000作为链表结束的表示即nxt[tail]0{\text{nxt[tail]0}}nxt[tail]0。2.插入在逻辑上的第一个元素前再插入一个元素x{\text{x}}xdata[cnt]x;// 开辟空间保存数据x 当前地址即 cntnxt[cnt]head;// 新节点的后继是头headcnt;// 当前链表的头是 cnt在逻辑最后位置插入元素x{\text{x}}xdata[cnt]x;// 开辟空间保存数据x 当前地址即 cntnxt[tail]cnt;// 当前链表的尾巴的后继是新节点tailcnt;// 当前链表的尾巴是 cnt在下标为now{\text{now}}now的元素后面插入一个新的元素x{\text{x}}x代码如下data[cnt]x;// 开辟空间保存数据x 当前地址即 cntnxt[cnt]nxt[now];// 新节点的后继是 now 节点的后继nxt[now]cnt;// now 节点的后继是 cnt3.删除删除 now 的后继节点nxt[now]nxt[nxt[now]];注意这种操作只是在逻辑上将该元素删除了物理上仍然是占有该空间的但是编程复杂度与时间复杂度都非常优秀。4.遍历遍历即将所有元素全部访问一遍此处仿照数组遍历的方法代码如下for(intihead;i;inxt[i]){操作data[i];}本题分析数据范围n≤2×105n \le 2\times 10^5n≤2×105暴力模拟每轮遍历全部水果会超时所以我想使用双层链表维护外层链表管理所有果篮作用快速删除果篮后连接前后果篮内层链表管理单个果篮内部所有水果快速弹出最左侧元素快速合并相邻同果篮。涉及连接、合并操作均O(1)O(1)O(1)时间开销数据结构果篮双向静态链表结构体数组lis[]存储每一个果篮用l/r记录前后果篮下标实现双向链表附加信息t块水果类型、st块内第一个水果编号、ed块内最后一个水果编号设置哨兵节点lis[0]规避链表首尾边界特判方便合并。块内水果单向静态链表数组nxt[]nxt[x]代表编号xxx的水果在同一块内的下一个水果快速弹出块首元素、拼接两个块的水果链。参考程序#includeiostreamusingnamespacestd;constintN2e55;inta[N],nxt[N],n,r1;// a存水果类型nxt果篮内水果单向链表r代表当前果篮也是果篮总数intcnt;// 已取出水果计数控制外层循环终止// 果篮结构体双向静态链表节点structK{intl,r;// l前驱果篮下标r后继果篮下标intt;// 果篮水果类型 0/1intst,ed;// st果篮首水果编号ed果篮尾水果编号K():l(0),r(0),st(0),ed(0){}}lis[N];intmain(){// IO加速cin.tie(nullptr)-sync_with_stdio(false);cinna[1];// 哨兵节点 lis[0]后继果篮是 1 号果篮类型是 -1lis[0].r1,lis[0].t-1;// 第一个果篮的开始水果与末尾水果都是 1 类型是 a[1]lis[1].stlis[1].ed1,lis[1].ta[1];// 划分果篮构建双层链表for(inti2;in;i){cina[i];if(a[i]a[i-1]){// 当前水果和前果篮类型一致nxt[i-1]i;// 同一果篮当前水果是上一水果的后继果篮内水果链表向后延伸lis[r].edi;// 更新当前果篮末尾水果编号}else{r;// 种类不同新建果篮lis[r-1].rr;// 前果篮后继指向果篮块lis[r].lr-1;// 新果篮前驱指向前果篮lis[r].stlis[r].edi;// 当前果篮内开始水果与末尾水果都是 ilis[r].ta[i];// 当前新果篮的类型是 a[i]}}// 模拟每一轮操作取完所有水果结束while(cnt!n){// 遍历所有果篮取出每个果篮最左侧水果并输出for(intheadlis[0].r;head;headlis[head].r){inthlis[head].st;// 当前果篮首水果couth ;hnxt[h],cnt;// 模拟拿出水果计数 1if(h){lis[head].sth;// 果篮内水果仍有剩余更新当前果篮第一个水果}else{// 果篮已取空从果篮双向链表摘除// 连接当前果篮的前驱与后继lis[lis[head].l].rlis[head].r;lis[lis[head].r].llis[head].l;}}cout\n;// 遍历果篮链表合并相邻同类型果篮起点从第二个果篮开始for(intheadlis[lis[0].r].r;head;headlis[head].r){intflis[head].l;// f是当前果篮的前一果篮if(lis[f].tlis[head].t){nxt[lis[f].ed]lis[head].st;// 拼接两果篮内部水果链表lis[f].edlis[head].ed;// 更新前果篮末尾水果lis[f].rlis[head].r;// 前果篮的后继是当前果篮的后继lis[lis[head].r].lf;// 后果篮前驱指回前果篮}}}return0;}第一遍写的时候考虑了好久可不可以while{\text{while}}while里面一个for{\text{for}}for就搞定了如果当前果篮为空当前果篮的后继果篮只有一个水果那么将前一果篮连接上后一果篮假设两果篮类型相同又要合并但是现在还不能合并因为后一果篮还没有拿水果如果提前拿导致后一果篮没有水果又得合并太复杂了所以还是干脆再重新跑一遍得了。时间复杂度所有轮次里循环A\text{A}A遍历块的总次数n\text{n}n证明设一轮现存块数量为k\text{k}k本轮循环A\text{A}A遍历k\text{k}k次每一次遍历必然消耗 1 个水果取出块首元素cnt\text{cnt}cnt。所有轮次循环A\text{A}A遍历总次数 一共取出水果总数n\text{n}n。循环B\text{B}B合并遍历总遍历次数同样上限O(n){ O(n) }O(n)循环B\text{B}B是遍历块链表检查相邻两块是否合并一个块一旦被合并到前块会永久从链表移除再也不会被循环B\text{B}B访问初始总块数最多n\text{n}n交替 01每一次循环B\text{B}B的遍历只会访问当前存活的块所有轮次循环B\text{B}B访问块的总次数不会超过初始总块数的常数倍也就是O(n){ O(n) }O(n)。A c c e pted\colorbox{#52C41A}{\color{white}{\Huge{\ A \hspace{-.4cm}{\raisebox{.3cm}{c}} \hspace{-.3cm}{c} \normalsize\hspace{-.3cm}{e} \Huge{\hspace{-.1cm}{p}}{t}ed}}}Accepted​