CSP-J第二轮试题-2021年-4题

参考：

https://www.luogu.com.cn/problem/P7911

总结

本系列为CSP-J/S算法竞赛真题讲解，会按照年份分析每年的真题，并给出对应的答案。本文为2021年真题。
https://www.luogu.com.cn/problem/list?tag=343&page=1

[CSP-J 2021] 小熊的果篮

题目描述

小熊的水果店里摆放着一排 $n$ 个水果。每个水果只可能是苹果或桔子，从左到右依次用正整数 $1,2,\dots ,n$ 编号。连续排在一起的同一种水果称为一个“块”。小熊要把这一排水果挑到若干个果篮里，具体方法是：每次都把每一个“块”中最左边的水果同时挑出，组成一个果篮。重复这一操作，直至水果用完。注意，每次挑完一个果篮后，“块”可能会发生变化。比如两个苹果“块”之间的唯一桔子被挑走后，两个苹果“块”就变成了一个“块”。请帮小熊计算每个果篮里包含的水果。

输入格式

第一行，包含一个正整数 $n$，表示水果的数量。

第二行，包含 $n$ 个空格分隔的整数，其中第 $i$ 个数表示编号为 $i$ 的水果的种类，$1$ 代表苹果，$0$ 代表桔子。

输出格式

输出若干行。

第 $i$ 行表示第 $i$ 次挑出的水果组成的果篮。从小到大排序输出该果篮中所有水果的编号，每两个编号之间用一个空格分隔。

样例 #1

样例输入 #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

样例输入 #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

样例输入 #3

见附件中的 fruit/fruit3.in。

样例输出 #3

见附件中的 fruit/fruit3.ans。

提示

【样例解释 #1】

这是第一组数据的样例说明。

所有水果一开始的情况是 $[1,1,0,0,1,1,1,0,1,1,0,0]$，一共有 $6$ 个块。

在第一次挑水果组成果篮的过程中，编号为 $1,3,5,8,9,11$ 的水果被挑了出来。

之后剩下的水果是 $[1,0,1,1,1,0]$，一共 $4$ 个块。

在第二次挑水果组成果篮的过程中，编号为 $2,4,6,12$ 的水果被挑了出来。

之后剩下的水果是 $[1,1]$，只有 $1$ 个块。

在第三次挑水果组成果篮的过程中，编号为 $7$ 的水果被挑了出来。

最后剩下的水果是 $[1]$，只有 $1$ 个块。

在第四次挑水果组成果篮的过程中，编号为 $10$ 的水果被挑了出来。

【数据范围】

对于 $10\%$ 的数据，$n\le 5$。
对于 $30\%$ 的数据，$n\le 1000$。
对于 $70\%$ 的数据，$n\le 50000$。
对于 $100\%$ 的数据，$1\le n\le 2\times {10}^5$。

【提示】

由于数据规模较大，建议 C/C++ 选手使用 scanf 和 printf 语句输入、输出。

答案

//#include <bits/stdc++.h>
#include<cstdio>//必须包含cstdio头文件
#include<iostream>
//#include<algorithm> //sort排序
//#include<cmath> //pow
using namespace std;// 定义个变量接受n n表示n水果数量
int n;
// 定义数组存储n个水果 1表示苹果 0表示橙子
int a[10010];
//定义计数器
int cnt=0;int main(){//freopen("candy.in","r",stdin);//freopen("candy.out","w",stdout);//接受nscanf("%d",&n);//存储n个水果到数组a中for(int i=1;i<=n;i++){scanf("%d",&a[i]);}
//    for(int i=1;i<=n;i++){
//        printf("%d",a[i]);
//    }// 遍历 退出条件是数组中取出的水果数量cnt为nwhile(cnt!=n){// 设置flag flag表示当前的水果 有没有变化，如果变了就取出水果，把计数器cnt+1int flag=2;// 遍历数组 每次取出一个值进行判断for(int i=1;i<=n;i++){// 如果a[i]与标记不相同if(a[i]!=flag && a[i]!=3){// 取出a[i]printf("%d ",i);flag=a[i];a[i]=3;cnt +=1;}}cout<<endl;}//system("pause");//fclose(stdin);//fclose(stdout);return 0;
}

答案1

#include <bits/stdc++.h>
//#include<cstdio>//必须包含cstdio头文件
//#include<iostream>
using namespace std;
int a[200010],n,cnt;int main(){//freopen("candy.in","r",stdin);//freopen("candy.out","w",stdout);scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%d",&a[i]);}while(cnt<n){int flag=2;for(int i=1;i<=n;i++){if(a[i]!=-1 && a[i]!=flag){flag = a[i];a[i] = -1;printf("%d ",i);cnt++;}}printf("\n");}//    system("pause");//fclose(stdin);//fclose(stdout);return 0;
}

答案2

#include <bits/stdc++.h>
//#include<cstdio>//必须包含cstdio头文件
//#include<iostream>
using namespace std;
struct node{int L,R,num;
};
int n,t;
queue<node> q;
int main(){//freopen("candy.in","r",stdin);//freopen("candy.out","w",stdout);scanf("%d",&n);int flag =2;for(int i=1;i<=n;i++){scanf("%d",&t);if(t!=flag){//新建一个块q.push(node{i,i,t});flag=t;}else{//更新这个块q.back().R=i;}}while(!q.empty()){int k=q.size();int flag = 2;for(int i=1;i<=k;i++){if(q.front().num!=flag){printf("%d ",q.front().L);q.front().L++;flag=q.front().num;}if(q.front().L<=q.front().R){q.push(q.front());}q.pop();}printf("\n");}//    system("pause");//fclose(stdin);//fclose(stdout);return 0;
}

答案3

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <queue>using namespace std;struct kuai{ // 块int st, ed, th;
}f, x, ad;
int n, cnt, t[200002];
queue<kuai> q, q2;
bool used[200001]; // 记录是否被取出
int main(){scanf("%d", &n);for (int i = 1;i <= n;i ++) scanf("%d", &t[i]);t[n + 1] = !t[n];for (int i = 2, si = 1;i <= n + 1;i ++){if (t[i] != t[i - 1]) q.push((kuai){si, i - 1, t[i - 1]}), si = i; // 把连续一段相同的元素合成一个块}cnt = n;while (cnt){while (q.size()){f = q.front();q.pop();while (used[f.st] && f.st <= f.ed) f.st ++; // 如果已经被取了if (f.st > f.ed) continue;printf("%d ", f.st), cnt --;used[f.st] = 1; // 将块的开头元素去掉并输出if (f.ed == f.st) continue; // 如果这个块被取完了f.st ++;q2.push(f); // 先临时存到 q2 里进行合并}putchar('\n');while (q2.size()){ad = q2.front();q2.pop();while (q2.size()){x = q2.front();if (x.th == ad.th){ // 能合并就合并ad.ed = x.ed;q2.pop();}else break;}q.push(ad); // 丢回 q 里}}
}

现场真题注意事项

https://cspoj.com/contest.php?cid=1002
Fus5yz4x3EcSJH1Z

注意事项

1. 文件名（程序名和输入输出文件名）必须使用英文小写。（提交必须使用freopen()进行提交）
2. C/C++ 中函数 main() 的返回值类型必须是 int，程序正常结束时的返回值必须是0。
3. 提交的程序代码文件的放置位置请参考各省的具体要求。
4. 因违反以上三点而出现的错误或问题，申述时一律不予受理。
5. 若无特殊说明，结果的比较方式为全文比较（过滤行末空格及文末回车）。
6. 程序可使用的栈空间内存限制与题目的内存限制一致。
7. 全国统一评测时采用的机器配置为：Inter® Core™ i7-8700K CPU @3.70GHz，内存 32GB。上述时限以此配置为准。
8. 只提供 Linux 格式附加样例文件。
9. 评测在当前最新公布的 NOI Linux 下进行，各语言的编译器版本以此为准

/*
假设输入样例数据存在文件test.in中，输出样例数据存在文件test.out中，
则在CSP、NOI等比赛的代码中，需添加freopen、fclose语句，
内容详见模板代码如下。
*/

#include <bits/stdc++.h>
#include<cstdio>//必须包含cstdio头文件
#include<iostream>
using namespace std;int main(){freopen("test.in","r",stdin);freopen("test.out","w",stdout);cout<<"Hello NOI"<<endl;fclose(stdin);fclose(stdout);return 0;
}

下面为函数的简介，详细可参见 http://www.cplusplus.com/reference/clibrary/cstdio/freopen.html
函数名：freopen
声明：FILE *freopen( const char *path, const char *mode, FILE *stream );
所在文件： stdio.h
参数说明：
path: 文件名，用于存储输入输出的自定义文件名。
mode: 文件打开的模式。和fopen中的模式（如r-只读, w-写）相同。
stream: 一个文件，通常使用标准流文件。
返回值：成功，则返回一个path所指定文件的指针；失败，返回NULL。（一般可以不使用它的返回值）
功能：实现重定向，把预定义的标准流文件定向到由path指定的文件中。标准流文件具体是指stdin、stdout和stderr。其中stdin是标准输入流，默认为键盘；stdout是标准输出流，默认为屏幕；stderr是标准错误流，一般把屏幕设为默认。通过调用freopen，就可以修改标准流文件的默认值，实现重定向。

#include<iostream>
#include<cstdio>
using namespace std;
int main(){freopen("7532.in", "r", stdin);freopen("7532.out", "w", stdout);//原来的代码保持不变double a, b, r;int k;cin >> a >> b;k = int(a/b);r = a - b * k;printf("%g", r);//-------------fclose(stdin);fclose(stdout);return 0;
}