首页 > 其他分享 >CSP-J历年真题（部分）解析与题解

CSP-J历年真题（部分）解析与题解

时间：2024-09-29 20:23:44浏览次数：9  
标签：排序 idx 真题 int 题解 num 100 include CSP

目录

序言：

[CSP-J2020] 直播获奖

前言：

题目描述

输入格式

输出格式

输入输出样例

说明/提示

样例 1 解释

数据规模与约定

提示

65分思路及代码

前言：

思路：

代码：

85分代码及思路：

前言：

插入排序：

思路：

代码： 

AC思路及代码：

前言：

思路：

    代码：

 [CSP-J 2022] 乘方

前言：

题目描述

输入格式

输出格式

输入输出样例

说明/提示

代码：

补充包：

        前言：

        插入排序：

             原理：

        插入排序的实现步骤：

         

        插入排序的代码:

 冒泡排序：

             原理：

  

        冒泡排序的实现步骤：

        冒泡排序的代码:

  桶排序：

             原理：

       桶排序的代码:

 sort排序：

             sort排序的用法：

结言：

序言：

我给大家这次一次看够，要考CSP-J的学生看过来，这里包含了历年三四道真题

[CSP-J2020] 直播获奖

前言：

CSP2020T2，我历时5天AC；我的思路希望给予你帮助；

题目描述

NOI2130 即将举行。为了增加观赏性，CCF 决定逐一评出每个选手的成绩，并直播即时的获奖分数线。本次竞赛的获奖率为 w%w%，即当前排名前 w%w% 的选手的最低成绩就是即时的分数线。

更具体地，若当前已评出了 pp 个选手的成绩，则当前计划获奖人数为 max⁡(1,⌊p×w%⌋)max(1,⌊p×w%⌋)，其中 ww 是获奖百分比，⌊x⌋⌊x⌋ 表示对 xx 向下取整，max⁡(x,y)max(x,y) 表示 xx 和 yy 中较大的数。如有选手成绩相同，则所有成绩并列的选手都能获奖，因此实际获奖人数可能比计划中多。

作为评测组的技术人员，请你帮 CCF 写一个直播程序。

输入格式

第一行有两个整数 n,wn,w。分别代表选手总数与获奖率。
第二行有 nn 个整数，依次代表逐一评出的选手成绩。

输出格式

只有一行，包含 nn 个非负整数，依次代表选手成绩逐一评出后，即时的获奖分数线。相邻两个整数间用一个空格分隔。

输入输出样例

输入 #1复制

10 60
200 300 400 500 600 600 0 300 200 100

输出 #1复制

200 300 400 400 400 500 400 400 300 300

输入 #2复制

10 30
100 100 600 100 100 100 100 100 100 100

输出 #2复制

100 100 600 600 600 600 100 100 100 100

说明/提示

样例 1 解释

数据规模与约定

各测试点的 nn 如下表：

测试点编号n=n=
1∼31∼31010
4∼64∼6500500
7∼107∼1020002000
11∼1711∼17104104
18∼2018∼20105105

对于所有测试点，每个选手的成绩均为不超过 600600 的非负整数，获奖百分比 ww 是一个正整数且 1≤w≤991≤w≤99。

提示

在计算计划获奖人数时，如用浮点类型的变量（如 C/C++ 中的 float 、 double，Pascal 中的 real 、 double 、 extended 等）存储获奖比例 w%w%，则计算 5×60%5×60% 时的结果可能为 3.0000013.000001，也可能为 2.9999992.999999，向下取整后的结果不确定。因此，建议仅使用整型变量，以计算出准确值。

65分思路及代码

前言：

        这一题哇一眼看下去，好简单！！！不就是来一个人插进去，排个序，一直重复，好像也不难！！！

思路：

1.定义基本变量及数组

const int N=1e4+5;
int a[N];
int n,w,idx=0;

2.边输入，便把数插入数组末端

	for(int i=1;i<=n;++i){
		int x;
		cin>>x;
		idx++;
		a[idx] = x;

3.对数组进行排序

sort(a+1,a+idx+1,cmp);

4.算出得分的概率

	int ans = 0; 
	ans = max(1,idx*w/100);

5，输出

cout<<a[ans]<<" ";

好的，只见我自信提交

代码：

#include <bits/stdc++.h>//万能头文件
#include <iostream>//无聊多打几个头文件
#include <cmath>//无聊多打几个头文件
#include <cstring>//无聊多打几个头文件
const int N=1e4+5;
int a[N];
int n,w,idx=0;
bool cmp(int x,int y){return x>y;}
using namespace std;
int main()//代码开始
{
	/*ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);*/
	cin>>n>>w;
	for(int i=1;i<=n;++i){
		int x;
		cin>>x;
		idx++;
		a[idx] = x;
		sort(a+1,a+idx+1,cmp);
		int ans = 0; 
		ans = max(1,idx*w/100);
		cout<<a[ans]<<" ";
	}
	return 0;//愉快的结束了
}
/*
时间：

做题人 ：jason

语言 ：c++
*/
/*
in :
out: 
*/

现实打我脸了；

85分代码及思路：

前言：

不死心的我决定再次挑战，我看了样例分析和计算过程；

先插入一个，在排序；不就是插入排序吗？

番外：

插入排序：

#include <bits/stdc++.h>//万能头文件
#include <iostream>//无聊多打几个头文件
#include <cmath>//无聊多打几个头文件
#include <cstring>//无聊多打几个头文件
using namespace std;
const int N=10;
int a[N] = {9,1,0,2,3,7,5,4,8,6};
void insert_sort(){
	for(int i=0;i<N;++i){
		int idx = i -1 ;
		while(idx >= 0 && a[idx]>a[idx+1]){
			swap(a[idx],a[idx+1]);
			idx--;
		}
	}
}
int main()//代码开始
{
	ios :: sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	insert_sort();
	for(int i=0;i<N;++i) cout<<a[i]<<" ";
	return 0;//愉快的结束了
}

于是我模拟了一下插入排序的

思路：

1.定义基本变量及数组

 1.定义基本变量及数组

const int N=1e4+5;
int a[N];
int n,w,idx=0,num=0;

2.边输入，便把数插入数组末端

	for(int i=1;i<=n;++i){
		int x;
		cin>>x;
		idx++;
		a[idx] = x;

3.插排

	while(num>=1 && a[num] < a[num+1]){
			swap(a[num],a[num+1]);
			num--;
		}

 4.计算

		int ans = 0; 
		ans = max(1,idx*w/100);

5.输出

cout<<a[ans]<<" ";

代码： 

#include <bits/stdc++.h>//万能头文件
#include <iostream>//无聊多打几个头文件
#include <cmath>//无聊多打几个头文件
#include <cstring>//无聊多打几个头文件
const int N=1e4+5;
int a[N];
int n,w,idx=0,num=0;
bool cmp(int x,int y){return x>y;}
using namespace std;
int main()//代码开始
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>w;
	for(int i=1;i<=n;++i){
		int x;
		cin>>x;
		idx++;
		a[idx] = x;
		num = idx - 1;
		while(num>=1 && a[num] < a[num+1]){
			swap(a[num],a[num+1]);
			num--;
		}
		//sort(a+1,a+idx+1,cmp);
		int ans = 0; 
		ans = max(1,idx*w/100);
		cout<<a[ans]<<" ";
	}
	return 0;//愉快的结束了
}

这次总该没问题了吧

啊啊啊啊，我要疯了；

AC思路及代码：

前言：

我觉定换一种排序，什么排序能解决这样的问题呢；

不超过600，可以开桶啊，那就用桶排序！！！；

思路：

1.定义基本变量和数据；

const int N=1e4+5;
int a[N];
int n,w,idx=0,num=0;

2.边输入，便将数字放入桶

		int x;
		cin>>x;
		a[x]++;
		idx++;

3.计算ans值

ans = max(1 ,idx*w/100);

4.循环判断桶里有没有数

		for(int j = 600 ; j >= 0;--j){
			if(a[j]!=0){
				num+=a[j];
			}

5.如果有数，判断数是否在ans位

			if(num >= ans){
				cout<<j<<" ";
				break;
			}

    代码：

#include <bits/stdc++.h>//万能头文件
#include <iostream>//无聊多打几个头文件
#include <cmath>//无聊多打几个头文件
#include <cstring>//无聊多打几个头文件
const int N=1e4+5;
int a[N];
int n,w,idx=0,num=0;
bool cmp(int x,int y){return x>y;}
using namespace std;
int main()//代码开始
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>w;
	for(int i=1;i<=n;++i){
		int x;
		cin>>x;
		a[x]++;
		idx++;
		int ans = 0,num = 0; 
		ans = max(1 ,idx*w/100);
		for(int j = 600 ; j >= 0;--j){
			if(a[j]!=0){
				num+=a[j];
			}
			if(num >= ans){
				cout<<j<<" ";
				break;
			}
		}
	}
	return 0;//愉快的结束了
}

这一题结束啦！！！

 [CSP-J 2022] 乘方

前言：

CSP2022T1，看了这么长，来一道简单的放松一下吧；

题目描述

小文同学刚刚接触了信息学竞赛，有一天她遇到了这样一个题：给定正整数 aa 和 bb，求 abab 的值是多少。

abab 即 bb 个 aa 相乘的值，例如 2323 即为 33 个 22 相乘，结果为 2×2×2=82×2×2=8。

“简单！”小文心想，同时很快就写出了一份程序，可是测试时却出现了错误。

小文很快意识到，她的程序里的变量都是 int 类型的。在大多数机器上，int 类型能表示的最大数为 231−1231−1，因此只要计算结果超过这个数，她的程序就会出现错误。

由于小文刚刚学会编程，她担心使用 int 计算会出现问题。因此她希望你在 abab 的值超过 109109 时，输出一个 -1 进行警示，否则就输出正确的 abab 的值。

然而小文还是不知道怎么实现这份程序，因此她想请你帮忙。

输入格式

输入共一行，两个正整数 a,ba,b。

输出格式

输出共一行，如果 abab 的值不超过 109109，则输出 abab 的值，否则输出 -1。

输入输出样例

输入 #1复制

10 9

输出 #1复制

1000000000

输入 #2复制

23333 66666

输出 #2复制

-1

说明/提示

对于 10%10% 的数据，保证 b=1b=1。
对于 30%30% 的数据，保证 b≤2b≤2。
对于 60%60% 的数据，保证 b≤30b≤30，ab≤1018ab≤1018。
对于 100%100% 的数据，保证 1≤a,b≤1091≤a,b≤109。

upd 2022.11.14upd 2022.11.14：新增加一组 HackHack 数据。

这一题应该很简单吧，我放代码了；

代码：

#include <bits/stdc++.h>//万能头文件
#include <iostream>//无聊多打几个头文件
#include <cmath>//无聊多打几个头文件
#include <cstring>//无聊多打几个头文件
using namespace std;
const long long inf = 1e9;
long long a,b,c;
int main()//代码开始
{
	cin>>a>>b;
	if(a == 1) {
		cout<<1;
		return 0;
	}
	if(b>29){
		cout<<-1;
		return 0;
	}
	long long sum = 1;
	for(int i=1;i<=b;++i){
		sum*=a;
		if(sum>inf){
			cout<<-1;
			return 0;
		}
	}
	cout<<sum;
	return 0;//愉快的结束了
}

 

补充包：

        前言：

                大家应该用到排序的方法挺多的，今天我为大家总结几种方法

                

        插入排序：

             原理：

               插入排序的基本思想是将待排序的元素序列看作是一个‌有序序列和一个无序序列的组          合。初始时，有序序列仅包含一个元素，其余为无序序列。然后，每次从无序序列中取出一个元素，将其按大小插入到有序序列的适当位置，使之成为新的有序序列。这个过程重复进行，直到无序序列为空，整个序列变为有序

                 

        插入排序的实现步骤：

               

  1. 从第一个元素开始，该元素可以认为已经被排序。
  2. 取出下一个元素，在已经排序的元素序列中从后向前扫描。
  3. 如果该元素大于新元素，将该元素移到下一位置。
  4. 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置。
  5. 将新元素插入下一位置中。
  6. 重复步骤2~5，直到整个序列有序

        

         

        插入排序的代码:


#include <iostream>
#include <vector>
 
void insertionSort(vector<int>& arr) {
    int i, j, key;
    for (i = 1; i < arr.size(); i++) {
        key = arr[i];
        j = i - 1;
 
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j = j - 1;
        }
        arr[j + 1] = key;
    }
}
 
int main() {
    std::vector<int> arr = {12, 11, 13, 5, 6};
    insertionSort(arr);
 
    for (int num : arr) {
         cout << num << " ";
    }
 
    return 0;
}

 

 冒泡排序：

             原理：

        冒泡排序是一种简单的排序算法，其基本思想是通过重复遍历待排序的数列，比较相邻的元素，如果它们的顺序错误就交换过来。这个过程会重复进行，直到没有需要交换的元素为止。冒泡排序的名字来源于较小的元素会像气泡一样逐渐“浮”到数列的顶端。

             

  

        冒泡排序的实现步骤：

  1. 从数组的第一个元素开始，比较相邻的元素。
  2. 如果第一个比第二个大，就交换这两个元素的位置。
  3. 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。
  4. 针对所有的元素重复以上的步骤。
  5. 除了最后一个元素外，重复步骤1~3，直到排序完成。

        

        冒泡排序的代码:

    int i, j;
    for (i = 0; i < n-1; i++) {
        for (j = 0; j < n-i-1; j++) {
            if (arr[j] > arr[j+1]) {
                int temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }
        }
    }

  桶排序：

             原理：

                桶排序（Bucket sort）或箱排序，是一种分块的排序算法。它的工作原理是将数组分到有限数量的桶里，每个桶再个别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序）

        

       桶排序的代码:

void sort_d(){
    int a[600];
    int x,n;
    cin>>n;
    for(int i=1;i<=n;++i){
        cin>>x;
        a[x]++;
    }
}

 sort排序：

        

       sort排序的用法：

                

#include <algorithm>
#include <vector>
#include <iostream>
 
int main() {
    std::vector<int> v = {4, 2, 5, 3, 1};
    std::sort(v.begin(), v.end());
 
    for (int n : v) {
        std::cout << n << ' ';
    }
 
    return 0;
}

结言：

        真题讲解结束了，我们下次再见，哎对了，记得在下面投票！！！；

        

标签：排序,idx,真题,int,题解,num,100,include,CSP
From： https://blog.csdn.net/djy2024/article/details/142622968

相关文章

  • C语言 | Leetcode C语言题解之第445题两数相加II
    题目：题解：structListNode*addTwoNumbers(structListNode*l1,structListNode*l2){intstack1[100];intstack2[100];inttop1=0;inttop2=0;intcarry=0;intsum=0;structListNode*temp=NULL;structListNode*he......
  • C语言 | Leetcode C语言题解之第443题压缩字符串
    题目：题解：voidswap(char*a,char*b){chart=*a;*a=*b,*b=t;}voidreverse(char*a,char*b){while(a<b){swap(a++,--b);}}intcompress(char*chars,intcharsSize){intwrite=0,left=0;for(intr......
  • C++ | Leetcode C++题解之第445题两数相加II
    题目：题解：classSolution{public:ListNode*addTwoNumbers(ListNode*l1,ListNode*l2){stack<int>s1,s2;while(l1){s1.push(l1->val);l1=l1->next;}while(l2){......
  • C++ | Leetcode C++题解之第443题压缩字符串
    题目：题解：classSolution{public:intcompress(vector<char>&chars){intn=chars.size();intwrite=0,left=0;for(intread=0;read<n;read++){if(read==n-1||chars[read]!=chars[read......
  • [USACO22DEC] Palindromes P 题解
    T3[USACO22DEC]PalindromesP郝题。首先考虑给定一个串\(S\)怎么求出要换多少次。易得，不可能交换两个本来就相同的字符。不妨观察\(\textttG\)的回文关系，一对\(\textttG\)回文当且仅当第一个\(\textttG\)前面的\(\textttH\)数量等于第二个\(\textttG\)后面的......
  • CSP模拟5
    T1光我们来考虑一个格加\(4\)或者减\(4\),这样有一个比较好的性质，它能提供\(4,2,2,1\)的贡献还不会溢出，这样我们就有一个比较好的思路，我们枚举\(4,2,2,1\)所无法造成的贡献，很明显只有\(16\)种，然后我们就可以再枚举\(4,2,2,1\)来算贡献.点击查看代码#include<bits/......
  • CSP 模拟 36
    A一般图最小匹配首先排完序后肯定选连续两个。直接DP，\(f_{i,j}\)就是表面意思，\(f_{i,j}=min(f_{i-1,j},f_{i-2,j-1}+a_i-a_i-2)\)。差分后发现问题转化成了选择的数不能相邻，这时候也可以直接考虑DP，但是这是一个经典的反悔贪心。记下\(pre\)和\(nex\)，直接扔到堆里，选择一......
  • 「CSP-J」做题记录
    「CSP-J」做题记录记号：A：自己做出来的。B：看题解提示做出来的。C：对着题解做出来的。[CSP-J2019江西]道路拆除（A）我们可以把问题转化一下：求出最少要留下多少边，使得从首都出发，能到达\(s_1\)号与\(s_2\)号城市，且所要花费的最短时间分别不超过\(t_1\)与\(t_2\)。最终答......
  • 「CSP-S」 做题记录
    「CSP-S」做题记录[CSP-S2019江西]多叉堆自己做出来了，开心捏。先考虑对于一棵特定的树，如何计算答案（对应特殊性质1）。首先，根节点一定只能填\(0\)。其次，可以发现各个子树不会互相影响，所以可以分别考虑如何填各个子树。设填满以节点\(u\)为根的子树的方案数为\(f(u)\)，\(......
  • 【问题解决】win10日志错误：创建 TLS 客户端凭据时发生致命错误。 内部错误状态为 1001
    背景最近win10死机了一次，查看事件管理器发现有大量的报错：“创建TLS客户端凭据时发生致命错误。内部错误状态为10013”，如图：解决win键搜索internet选项确定。原因参考错误：“创建TLS客户端凭据时发生致命错误。内部错误状态为10013”的说法是win10对TLSv3.0兼容性......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99