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

参考：

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

总结

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

[CSP-J 2021] 分糖果

题目背景

红太阳幼儿园的小朋友们开始分糖果啦！

题目描述

红太阳幼儿园有 $n$ 个小朋友，你是其中之一。保证 $n\ge 2$。

有一天你在幼儿园的后花园里发现无穷多颗糖果，你打算拿一些糖果回去分给幼儿园的小朋友们。

由于你只是个平平无奇的幼儿园小朋友，所以你的体力有限，至多只能拿 $R$ 块糖回去。

但是拿的太少不够分的，所以你至少要拿 $L$ 块糖回去。保证 $n\le L\le R$。

也就是说，如果你拿了 $k$ 块糖，那么你需要保证 $L\le k\le R$。

如果你拿了 $k$ 块糖，你将把这 $k$ 块糖放到篮子里，并要求大家按照如下方案分糖果：只要篮子里有不少于 $n$ 块糖果，幼儿园的所有 $n$ 个小朋友（包括你自己）都从篮子中拿走恰好一块糖，直到篮子里的糖数量少于 $n$ 块。此时篮子里剩余的糖果均归你所有——这些糖果是作为你搬糖果的奖励。

作为幼儿园高质量小朋友，你希望让作为你搬糖果的奖励的糖果数量（而不是你最后获得的总糖果数量！）尽可能多；因此你需要写一个程序，依次输入 $n,L,R$，并输出你最多能获得多少作为你搬糖果的奖励的糖果数量。

输入格式

输入一行，包含三个正整数 $n,L,R$，分别表示小朋友的个数、糖果数量的下界和上界。

输出格式

输出一行一个整数，表示你最多能获得的作为你搬糖果的奖励的糖果数量。

样例 #1

样例输入 #1

7 16 23

样例输出 #1

6

样例 #2

样例输入 #2

10 14 18

样例输出 #2

8

样例 #3

样例输入 #3

见附件中的 candy/candy3.in。

样例输出 #3

见附件中的 candy/candy3.ans。

提示

【样例解释 #1】

拿 $k=20$ 块糖放入篮子里。

篮子里现在糖果数 $20\ge n=7$，因此所有小朋友获得一块糖；

篮子里现在糖果数变成 $13\ge n=7$，因此所有小朋友获得一块糖；

篮子里现在糖果数变成 $6<n=7$，因此这 $6$ 块糖是作为你搬糖果的奖励。

容易发现，你获得的作为你搬糖果的奖励的糖果数量不可能超过 $6$ 块（不然，篮子里的糖果数量最后仍然不少于 $n$，需要继续每个小朋友拿一块），因此答案是 $6$。

【样例解释 #2】

容易发现，当你拿的糖数量 $k$ 满足 $14=L\le k\le R=18$ 时，所有小朋友获得一块糖后，剩下的 $k-10$ 块糖总是作为你搬糖果的奖励的糖果数量，因此拿 $k=18$ 块是最优解，答案是 $8$。

【数据范围】

测试点	$n\le$	$R\le$	$R-L\le$
$1$	$2$	$5$	$5$
$2$	$5$	$10$	$10$
$3$	${10}^3$	${10}^3$	${10}^3$
$4$	${10}^5$	${10}^5$	${10}^5$
$5$	${10}^3$	${10}^9$	$0$
$6$	${10}^3$	${10}^9$	${10}^3$
$7$	${10}^5$	${10}^9$	${10}^5$
$8$	${10}^9$	${10}^9$	${10}^9$
$9$	${10}^9$	${10}^9$	${10}^9$
$10$	${10}^9$	${10}^9$	${10}^9$

对于所有数据，保证 $2\le n\le L\le R\le {10}^9$。

【感谢 hack 数据提供】
wangbinfeng

答案1

#include <bits/stdc++.h>
//#include<cstdio>//必须包含cstdio头文件
//#include<iostream>
using namespace std;int main(){freopen("candy.in","r",stdin);freopen("candy.out","w",stdout);int n,L,R,maxn=-1;cin>>n>>L>>R;for(int k=L;k<=R;k++){maxn = max(maxn,k%n);}cout<<maxn<<endl;//fclose(stdin);//fclose(stdout);return 0;
}

答案2-优化

#include <bits/stdc++.h>
//#include<cstdio>//必须包含cstdio头文件
//#include<iostream>
using namespace std;int main(){//freopen("candy.in","r",stdin);//freopen("candy.out","w",stdout);int n,L,R,maxn=-1;cin>>n>>L>>R;if(L%n+R-L >= n-1){cout<<n-1<<endl;}else{cout<<L%n + R - L<<endl;}//fclose(stdin);//fclose(stdout);return 0;
}

[CSP-J 2021] 插入排序

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

题目描述

插入排序是一种非常常见且简单的排序算法。小 Z 是一名大一的新生，今天 H 老师刚刚在上课的时候讲了插入排序算法。

假设比较两个元素的时间为 $\mathcal{O}(1)$，则插入排序可以以 $\mathcal{O}(n^2)$ 的时间复杂度完成长度为 $n$ 的数组的排序。不妨假设这 $n$ 个数字分别存储在 $a_1,a_2,\dots ,a_n$ 之中，则如下伪代码给出了插入排序算法的一种最简单的实现方式：

这下面是 C/C++ 的示范代码：

for (int i = 1; i <= n; i++)for (int j = i; j >= 2; j--)if (a[j] < a[j-1]) {int t = a[j-1];a[j-1] = a[j];a[j] = t;}

这下面是 Pascal 的示范代码：

for i:=1 to n dofor j:=i downto 2 doif a[j]<a[j-1] thenbegint:=a[i];a[i]:=a[j];a[j]:=t;end;

为了帮助小 Z 更好的理解插入排序，小 Z 的老师 H 老师留下了这么一道家庭作业：

H 老师给了一个长度为 $n$ 的数组 $a$，数组下标从 $1$ 开始，并且数组中的所有元素均为非负整数。小 Z 需要支持在数组 $a$ 上的 $Q$ 次操作，操作共两种，参数分别如下：

$1xv$：这是第一种操作，会将 $a$ 的第 $x$ 个元素，也就是 $a_x$ 的值，修改为 $v$。保证 $1\le x\le n$，$1\le v\le 10^9$。注意这种操作会改变数组的元素，修改得到的数组会被保留，也会影响后续的操作。

$2x$：这是第二种操作，假设 H 老师按照上面的伪代码对 $a$ 数组进行排序，你需要告诉 H 老师原来 $a$ 的第 $x$ 个元素，也就是 $a_x$，在排序后的新数组所处的位置。保证 $1\le x\le n$。注意这种操作不会改变数组的元素，排序后的数组不会被保留，也不会影响后续的操作。

H 老师不喜欢过多的修改，所以他保证类型 $1$ 的操作次数不超过 $5000$。

小 Z 没有学过计算机竞赛，因此小 Z 并不会做这道题。他找到了你来帮助他解决这个问题。

输入格式

第一行，包含两个正整数 $n,Q$，表示数组长度和操作次数。

第二行，包含 $n$ 个空格分隔的非负整数，其中第 $i$ 个非负整数表示 $a_i$。

接下来 $Q$ 行，每行 $2\sim 3$ 个正整数，表示一次操作，操作格式见【题目描述】。

输出格式

对于每一次类型为 $2$ 的询问，输出一行一个正整数表示答案。

样例 #1

样例输入 #1

3 4
3 2 1
2 3
1 3 2
2 2
2 3

样例输出 #1

1
1
2

提示

【样例解释 #1】

在修改操作之前，假设 H 老师进行了一次插入排序，则原序列的三个元素在排序结束后所处的位置分别是 $3,2,1$。

在修改操作之后，假设 H 老师进行了一次插入排序，则原序列的三个元素在排序结束后所处的位置分别是 $3,1,2$。

注意虽然此时 $a_2=a_3$，但是我们不能将其视为相同的元素。

【样例 #2】

见附件中的 sort/sort2.in 与 sort/sort2.ans。

该测试点数据范围同测试点 $1\sim 2$。

【样例 #3】

见附件中的 sort/sort3.in 与 sort/sort3.ans。

该测试点数据范围同测试点 $3\sim 7$。

【样例 #4】

见附件中的 sort/sort4.in 与 sort/sort4.ans。

该测试点数据范围同测试点 $12\sim 14$。

【数据范围】

对于所有测试数据，满足 $1\le n\le 8000$，$1\le Q\le 2\times {10}^5$，$1\le x\le n$，$1\le v,a_i\le 10^9$。

对于所有测试数据，保证在所有 $Q$ 次操作中，至多有 $5000$ 次操作属于类型一。

各测试点的附加限制及分值如下表所示。

测试点	$n\le$	$Q\le$	特殊性质
$1\sim 4$	$10$	$10$	无
$5\sim 9$	$300$	$300$	无
$10\sim 13$	$1500$	$1500$	无
$14\sim 16$	$8000$	$8000$	保证所有输入的 $a_i,v$ 互不相同
$17\sim 19$	$8000$	$8000$	无
$20\sim 22$	$8000$	$2\times 10^5$	保证所有输入的 $a_i,v$ 互不相同
$23\sim 25$	$8000$	$2\times 10^5$	无

答案1

#include <bits/stdc++.h>
//#include<cstdio>//必须包含cstdio头文件
//#include<iostream>
using namespace std;struct node
{int id,num;}a[8010];
int n,q;bool cmp(node a,node b)
{if(a.num == b.num){return a.id<b.id;}else{return a.num<b.num;}
}int main(){//freopen("candy.in","r",stdin);//freopen("candy.out","w",stdout);scanf("%d%d",&n,&q);for(int i=1;i<=n;i++){scanf("%d",&a[i].num);a[i].id = i;}sort(a+1,a+1+n,cmp);
//    cout<<"*****"<<endl;
//    for(int i=1;i<=n;i++)
//    {
//        cout<<a[i].id<<" "<<a[i].num<<endl;
//    }int op,u,v;while(q--){scanf("%d",&op);if(op == 1){//修改scanf("%d%d",&u,&v);//找到值，进行修改，排序for(int i=1;i<=n;i++){if(a[i].id==u){a[i].num = v;break;}}sort(a+1,a+1+n,cmp);}else{//查找scanf("%d",&u);for(int i=1;i<=n;i++){if(a[i].id==u){printf("%d\n",i);break;}}}}//    system("pause");//fclose(stdin);//fclose(stdout);return 0;
}

#include<bits/stdc++.h>using namespace std;// 一个元素结构体 321
struct node{int id;//原有的顺序int num;//初始值
}a[8010];bool cmp(node a,node b){if(a.num == b.num){return a.id<b.id;}else{return a.num<b.num;}}
int n,q;
int temp;
int main(){//freopen("candy.in","r",stdin);//freopen("candy.out","w",stdout);cin>>n>>q;// 初始化数组完成for(int i=1;i<=n;i++){cin>>a[i].num;a[i].id=i;}sort(a+1,a+1+n,cmp);// 因为结构体已经有原有的id了，所以可以直接排序int op,x,v;//op表示操作1 2 x表示原有数组中的位置 v表示替换的值while(q--){cin>>op;if(op == 1){cin>>x>>v;// 把原有的x替换为vfor(int i=1;i<=n;i++){if(a[i].id==x){// a[i].id 为原来的顺序a[i].num=v;}}sort(a+1,a+1+n,cmp);}else{cin>>x;// 根据x x为原有 数组中的id 求这个id的value再新数组中 的位置for(int i=1;i<=n;i++){if(a[i].id==x){// a[i].id 为原来的顺序cout<<i<<" "<<endl;}}}}return 0;
}

答案2

#include <bits/stdc++.h>
//#include<cstdio>//必须包含cstdio头文件
//#include<iostream>
using namespace std;struct node
{int id,num;}a[8010];
int n,q;
int b[8010];// 用来保存原来的下标和现在的下标
bool cmp(node a,node b)
{if(a.num == b.num){return a.id<b.id;}else{return a.num<b.num;}
}int main(){//freopen("candy.in","r",stdin);//freopen("candy.out","w",stdout);scanf("%d%d",&n,&q);for(int i=1;i<=n;i++){scanf("%d",&a[i].num);a[i].id = i;}sort(a+1,a+1+n,cmp);for(int i=1;i<=n;i++){b[a[i].id] = i;//}//    cout<<"*****"<<endl;
//    for(int i=1;i<=n;i++)
//    {
//        cout<<a[i].id<<" "<<a[i].num<<endl;
//    }int op,u,v;while(q--){scanf("%d",&op);if(op == 1){//修改scanf("%d%d",&u,&v);//找到值，进行修改，排序
//            for(int i=1;i<=n;i++){
//                if(a[i].id==u){
//                    a[i].num = v;
//                    break;
//                }
//            }a[b[u]].num=v;sort(a+1,a+1+n,cmp);// 新增for(int i=1;i<=n;i++){b[a[i].id]=i;}}else{//查找scanf("%d",&u);
//            for(int i=1;i<=n;i++){
//                if(a[i].id==u){
//                    printf("%d\n",i);
//                    break;
//                }
//
//            }printf("%d\n",b[u]);}}//    system("pause");//fclose(stdin);//fclose(stdout);return 0;
}

答案3

#include <bits/stdc++.h>
//#include<cstdio>//必须包含cstdio头文件
//#include<iostream>
using namespace std;struct node
{int id,num;}a[8010];
int n,q;
int b[8010];// 用来保存原来的下标和现在的下标
bool cmp(node a,node b)
{if(a.num == b.num){return a.id<b.id;}else{return a.num<b.num;}
}void change(int pos){while(pos > 1){if(a[pos].num>a[pos-1].num) break;if(a[pos].num==a[pos-1].num && a[pos].id>a[pos-1].id) break;swap(a[pos],a[pos-1]);b[a[pos].id]=pos;pos--;}while(pos<n){if(a[pos].num<a[pos+1].num) break;if(a[pos].num==a[pos+1].num && a[pos].id<a[pos+1].id) break;swap(a[pos],a[pos+1]);b[a[pos].id]=pos;pos++;}b[a[pos].id]=pos;}int main(){//freopen("candy.in","r",stdin);//freopen("candy.out","w",stdout);scanf("%d%d",&n,&q);for(int i=1;i<=n;i++){scanf("%d",&a[i].num);a[i].id = i;}sort(a+1,a+1+n,cmp);for(int i=1;i<=n;i++){b[a[i].id] = i;//}//    cout<<"*****"<<endl;
//    for(int i=1;i<=n;i++)
//    {
//        cout<<a[i].id<<" "<<a[i].num<<endl;
//    }int op,u,v;while(q--){scanf("%d",&op);if(op == 1){//修改scanf("%d%d",&u,&v);//找到值，进行修改，排序
//            for(int i=1;i<=n;i++){
//                if(a[i].id==u){
//                    a[i].num = v;
//                    break;
//                }
//            }a[b[u]].num=v;change(b[u]);
//            sort(a+1,a+1+n,cmp);
//            // 新增
//            for(int i=1;i<=n;i++){
//                b[a[i].id]=i;
//            }}else{//查找scanf("%d",&u);
//            for(int i=1;i<=n;i++){
//                if(a[i].id==u){
//                    printf("%d\n",i);
//                    break;
//                }
//
//            }printf("%d\n",b[u]);}}//    system("pause");//fclose(stdin);//fclose(stdout);return 0;
}

现场真题注意事项

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;
}