参考：
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] 小熊的果篮
题目描述
小熊的水果店里摆放着一排
个水果。每个水果只可能是苹果或桔子，从左到右依次用正整数
编号。连续排在一起的同一种水果称为一个“块”。小熊要把这一排水果挑到若干个果篮里，具体方法是：每次都把每一个“块”中最左边的水果同时挑出，组成一个果篮。重复这一操作，直至水果用完。注意，每次挑完一个果篮后，“块”可能会发生变化。比如两个苹果“块”之间的唯一桔子被挑走后，两个苹果“块”就变成了一个“块”。请帮小熊计算每个果篮里包含的水果。
输入格式
第一行，包含一个正整数
，表示水果的数量。
第二行，包含
个空格分隔的整数，其中第
个数表示编号为
的水果的种类，
代表苹果，
代表桔子。
输出格式
输出若干行。
第
行表示第
次挑出的水果组成的果篮。从小到大排序输出该果篮中所有水果的编号，每两个编号之间用一个空格分隔。
样例 #1
样例输入 #1
代码语言：javascript复制12
1 1 0 0 1 1 1 0 1 1 0 0样例输出 #1
代码语言：javascript复制1 3 5 8 9 11
2 4 6 12
7
10样例 #2
样例输入 #2
代码语言：javascript复制20
1 1 1 1 0 0 0 1 1 1 0 0 1 0 1 1 0 0 0 0样例输出 #2
代码语言：javascript复制1 5 8 11 13 14 15 17
2 6 9 12 16 18
3 7 10 19
4 20样例 #3
样例输入 #3
代码语言：javascript复制见附件中的 fruit/fruit3.in。样例输出 #3
代码语言：javascript复制见附件中的 fruit/fruit3.ans。提示
【样例解释 #1】
这是第一组数据的样例说明。
所有水果一开始的情况是
，一共有
个块。
在第一次挑水果组成果篮的过程中，编号为
的水果被挑了出来。
之后剩下的水果是
，一共
个块。
在第二次挑水果组成果篮的过程中，编号为
的水果被挑了出来。
之后剩下的水果是
，只有
个块。
在第三次挑水果组成果篮的过程中，编号为
的水果被挑了出来。
最后剩下的水果是
，只有
个块。
在第四次挑水果组成果篮的过程中，编号为
的水果被挑了出来。
【数据范围】
对于
的数据，
。 对于
的数据，
。 对于
的数据，
。 对于
的数据，
。
【提示】
由于数据规模较大，建议 C/C 选手使用 scanf 和 printf 语句输入、输出。
答案
代码语言：javascript复制//#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);
//接受n
scanf("%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为n
while(cnt!=n){
// 设置flag flag表示当前的水果 有没有变化，如果变了就取出水果，把计数器cnt 1
int 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
代码语言：javascript复制#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
代码语言：javascript复制#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
代码语言：javascript复制#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
注意事项
- 文件名（程序名和输入输出文件名）必须使用英文小写。（提交必须使用freopen()进行提交）
- C/C 中函数 main() 的返回值类型必须是 int，程序正常结束时的返回值必须是0。
- 提交的程序代码文件的放置位置请参考各省的具体要求。
- 因违反以上三点而出现的错误或问题，申述时一律不予受理。
- 若无特殊说明，结果的比较方式为全文比较（过滤行末空格及文末回车）。
- 程序可使用的栈空间内存限制与题目的内存限制一致。
- 全国统一评测时采用的机器配置为：Inter® Core™ i7-8700K CPU @3.70GHz，内存 32GB。上述时限以此配置为准。
- 只提供 Linux 格式附加样例文件。
- 评测在当前最新公布的 NOI Linux 下进行，各语言的编译器版本以此为准
/* 假设输入样例数据存在文件test.in中，输出样例数据存在文件test.out中， 则在CSP、NOI等比赛的代码中，需添加freopen、fclose语句， 内容详见模板代码如下。 */
代码语言：javascript复制#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，就可以修改标准流文件的默认值，实现重定向。
代码语言：javascript复制#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;
}
