参考：
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 nn 个水果。每个水果只可能是苹果或桔子，从左到右依次用正整数 1 , 2 , … , n 1, 2, \ldots, n1,2,…,n 编号。连续排在一起的同一种水果称为一个“块”。小熊要把这一排水果挑到若干个果篮里，具体方法是：每次都把每一个“块”中最左边的水果同时挑出，组成一个果篮。重复这一操作，直至水果用完。注意，每次挑完一个果篮后，“块”可能会发生变化。比如两个苹果“块”之间的唯一桔子被挑走后，两个苹果“块”就变成了一个“块”。请帮小熊计算每个果篮里包含的水果。
输入格式
第一行，包含一个正整数 n nn，表示水果的数量。
第二行，包含 n nn 个空格分隔的整数，其中第 i ii 个数表示编号为 i ii 的水果的种类，1 11 代表苹果，0 00 代表桔子。
输出格式
输出若干行。
第 i ii 行表示第 i ii 次挑出的水果组成的果篮。从小到大排序输出该果篮中所有水果的编号，每两个编号之间用一个空格分隔。
样例 #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 ] [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 66 个块。
在第一次挑水果组成果篮的过程中，编号为 1 , 3 , 5 , 8 , 9 , 11 1, 3, 5, 8, 9, 111,3,5,8,9,11 的水果被挑了出来。
之后剩下的水果是 [ 1 , 0 , 1 , 1 , 1 , 0 ] [1, 0, 1, 1, 1, 0][1,0,1,1,1,0]，一共 4 44 个块。
在第二次挑水果组成果篮的过程中，编号为 2 , 4 , 6 , 12 2, 4, 6, 122,4,6,12 的水果被挑了出来。
之后剩下的水果是 [ 1 , 1 ] [1, 1][1,1]，只有 1 11 个块。
在第三次挑水果组成果篮的过程中，编号为 7 77 的水果被挑了出来。
最后剩下的水果是 [ 1 ] [1][1]，只有 1 11 个块。
在第四次挑水果组成果篮的过程中，编号为 10 1010 的水果被挑了出来。
【数据范围】
对于 10 % 10 \%10% 的数据，n ≤ 5 n \le 5n≤5。
对于 30 % 30 \%30% 的数据，n ≤ 1000 n \le 1000n≤1000。
对于 70 % 70 \%70% 的数据，n ≤ 50000 n \le 50000n≤50000。
对于 100 % 100 \%100% 的数据，1 ≤ n ≤ 2 × 10 5 1 \le n \le 2 \times {10}^51≤n≤2×105。
【提示】
由于数据规模较大，建议 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); //接受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
#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
注意事项
- 文件名（程序名和输入输出文件名）必须使用英文小写。（提交必须使用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语句，
内容详见模板代码如下。
*/
#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; }
