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≥2。

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

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

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

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

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

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

输入格式

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

输出格式

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

样例 #1

样例输入 #1

7 16 23

样例输出 #1

样例 #2

样例输入 #2

10 14 18

样例输出 #2

样例 #3

样例输入 #3

见附件中的 candy/candy3.in。

样例输出 #3

见附件中的 candy/candy3.ans。

提示

【样例解释 #1】

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

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

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

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

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

【样例解释 #2】

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

【数据范围】

【感谢 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;
}

7b7aec356f1ece8b7cfe2ae8da7dd3d3_d4d6f7aed41a40a09c11cda1ad174e02.png

答案2-优化

f95b610d0c6536c1d7e75cbfa0321085_670056aafac747d18296b76dc2a90714.png

#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 老师刚刚在上课的时候讲了插入排序算法。

假设比较两个元素的时间为，则插入排序可以以的时间复杂度完成长度为 n 的数组的排序。不妨假设这 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 do
  for j:=i downto 2 do
    if a[j]<a[j-1] then
      begin
        t:=a[i];
        a[i]:=a[j];
        a[j]:=t;
      end;

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

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

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

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

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

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

输入格式

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

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

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

输出格式

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

样例 #1

样例输入 #1

样例输出 #1

1
1
2

提示

【样例解释 #1】

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

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

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

【样例 #2】

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

该测试点数据范围同测试点 1∼2。

【样例 #3】

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

该测试点数据范围同测试点 3∼7。

【样例 #4】

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

该测试点数据范围同测试点 12∼14。

【数据范围】

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

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

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

a3d0d5b5f9dadd5407c840c06f2e371e_3e05276339ad4eceb9788346c97c63aa.png

#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替换为v
            for(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;
}

3fc66e5d507221c552bd880e8e0fd8ba_0a310aa84e6b4be09e1193a0d32db6cf.png

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

df2f3db13247ca3c206e8ed13b117a82_fcb248f5342549fd819eeee3f6986c3b.png

现场真题注意事项

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

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

参考：

总结

[CSP-J 2021] 分糖果

题目背景

样例输入 #1

样例输出 #1

样例输入 #2

样例输出 #2

样例输入 #3

样例输出 #3

[CSP-J 2021] 插入排序

样例输入 #1

样例输出 #1

热门文章

最新文章

相关电子书