第37次CCF CSP认证(2025.03)真题+详细答案解析(实战版)_第1页
第37次CCF CSP认证(2025.03)真题+详细答案解析(实战版)_第2页
第37次CCF CSP认证(2025.03)真题+详细答案解析(实战版)_第3页
第37次CCF CSP认证(2025.03)真题+详细答案解析(实战版)_第4页
第37次CCF CSP认证(2025.03)真题+详细答案解析(实战版)_第5页
已阅读5页,还剩3页未读, 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

第37次CCFCSP认证(2025.03)真题+详细答案解析(实战版)总分:400分|时长:240分钟|适用:CSP入门/提高备考、考前刷题复盘T1区间统计(100分)题目描述给定n个整数,再给出m次询问,每次询问给出l,r,求区间[l,r]中不同数字的个数。输入格式:第一行两个整数n,m。第二行n个整数,表示数组a[1~n]。接下来m行,每行两个整数l,r。输出格式:对于每个询问,单独一行输出区间不同数数量。数据范围:1≤n,m≤1000,数组元素绝对值≤1000解题思路数据范围很小,不需要高级算法,暴力枚举即可稳过。对于每个询问,开一个标记数组/哈希集合,遍历区间内所有数,记录出现过的数字,最后统计标记总数就行。不用前缀、不用莫队,纯模拟,新手零难度,考场直接写,不卡时间。满分代码cpp

#include<iostream>

#include<cstring>

usingnamespacestd;

constintN=1005;

inta[N];

boolvis[2005];//处理负数,偏移1000

intmain(){

intn,m;

cin>>n>>m;

for(inti=1;i<=n;i++)cin>>a[i];

while(m--){

intl,r;

cin>>l>>r;

memset(vis,0,sizeof(vis));

intcnt=0;

for(inti=l;i<=r;i++){

intpos=a[i]+1000;

if(!vis[pos]){

vis[pos]=true;

cnt++;

}

}

cout<<cnt<<endl;

}

return0;

}易错点&得分总结1、数组存在负数,直接下标访问会越界,必须做偏移处理;2、每次询问必须清空标记数组,否则上一组数据会干扰结果;3、下标从1开始读入,匹配题目区间输入习惯,避免边界错误。得分:写法无脑,细心即可满分。T2最大公约数求和(100分)题目描述给定n个正整数,求出数组中所有不同下标对(i,j)(i<j)的gcd(a[i],a[j])的总和。输入格式:第一行一个整数n。第二行n个正整数。输出格式:输出所有数对最大公约数的和。数据范围:1≤n≤1000,数值≤1000解题思路n最大1000,总数对数量约50万,完全可以双重循环暴力枚举所有i<j的数对,逐个计算gcd累加即可。C++自带__gcd函数(algorithm头文件),注意只支持正整数,本题数据满足条件,直接调用即可。满分代码cpp

#include<iostream>

#include<algorithm>

usingnamespacestd;

constintN=1005;

inta[N];

intmain(){

intn;

cin>>n;

for(inti=1;i<=n;i++)cin>>a[i];

longlongans=0;//防止爆int

for(inti=1;i<=n;i++){

for(intj=i+1;j<=n;j++){

ans+=__gcd(a[i],a[j]);

}

}

cout<<ans<<endl;

return0;

}易错点&得分总结1、必须用longlong存答案!多组gcd累加容易超出int范围,直接int会爆数据、丢分;2、严格保证i<j,不要重复枚举(i,j)和(j,i);3、部分编译器__gcd参数需为正数,本题无坑。得分:暴力最优解,无优化必要,稳拿100。T3字符压缩解码(100分)题目描述有一种简易压缩规则:连续相同的字符会被压缩为字符+数字,单个字符不添加数字。现给出压缩后的字符串,要求还原出原始字符串。规则举例:a3→aaa;b→b;ab2c→abbcc输入:一行压缩字符串(仅小写字母、数字)输出:解码后的原始字符串数据范围:字符串长度≤1000,重复次数≤100解题思路逐字符遍历字符串:遇到字母就记录当前字符,继续往后读,如果后面紧跟着数字,就取出完整数字,重复对应次数拼接;如果后面不是数字,直接拼接一次当前字母。核心细节:数字可能是多位(比如a10代表10个a),不能只读个位。遍历的时候截取连续数字字符转整数即可。满分代码cpp

#include<iostream>

#include<string>

usingnamespacestd;

intmain(){

strings;

cin>>s;

stringres;

intlen=s.size();

for(inti=0;i<len;){

charch=s[i];

i++;

intnum=0;

//读取后续所有数字

while(i<len&&isdigit(s[i])){

num=num*10+s[i]-'0';

i++;

}

if(num==0)num=1;//无数字则出现1次

for(intj=0;j<num;j++){

res+=ch;

}

}

cout<<res<<endl;

return0;

}易错点&得分总结1、忽略多位数字,只处理个位,会直接WA大半测试点;2、忘记默认次数为1,单个字符无法正常输出;3、遍历指针i必须手动递增,不能用for自动++,否则会跳过数字位。得分:字符串模拟经典题,处理好多位数即可满分。T4路径最优计数(100分)题目描述给定一个n×m的网格,每个格子有一个非负权值。只能从左上角(1,1)出发,只能向右、向下走,走到右下角(n,m)。求两个结果:1、所有可行路径中,路径权值和的最小值;2、权值和等于最小值的路径总条数(答案对1e9+7取模)输入格式:第一行n,m。接下来n行,每行m个整数,为网格权值。输出:一行两个数,最小权值和、最短路路径数。数据范围:1≤n,m≤50解题思路经典二维DP模板题。开两个DP数组:1、dis[i][j]:走到(i,j)的最小路径和;2、cnt[i][j]:走到(i,j)的最小路径数量。状态转移:每个格子只能从上方(i-1,j)或左方(i,j-1)走来。-上方距离更小:继承上方的最小值和数量;-左方距离更小:继承左方的最小值和数量;-两边距离相等:数量累加,距离不变。初始化:起点dis[1][1]=权值,cnt[1][1]=1;其余dis初始为极大值。满分代码cpp

#include<iostream>

#include<cstring>

#include<algorithm>

usingnamespacestd;

typedeflonglongll;

constintMOD=1e9+7;

constllINF=1e18;

constintN=55;

lldis[N][N];

llcnt[N][N];

intmp[N][N];

intmain(){

intn,m;

cin>>n>>m;

for(inti=1;i<=n;i++){

for(intj=1;j<=m;j++){

cin>>mp[i][j];

}

}

//初始化

for(inti=1;i<=n;i++){

for(intj=1;j<=m;j++){

dis[i][j]=INF;

}

}

dis[1][1]=mp[1][1];

cnt[1][1]=1;

for(inti=1;i<=n;i++){

for(intj=1;j<=m;j++){

if(i==1&&j==1)continue;

llmin_pre=INF;

//从上方来

if(i>1)min_pre=min(min_pre,dis[i-1][j]);

//从左方来

if(j>1)min_pre=min(min_pre,dis[i][j-1]);

dis[i][j]=min_pre+mp[i][j];

//统计路径数

llsum=0;

if(i>1&&dis[i-1][j]==min_pre)sum=(sum+cnt[i-1][j])%MOD;

if(j>1&&dis[i][j-1]==min_pre)sum=(sum+cnt[i][j-1])%MOD;

cnt[i][j]=sum;

}

}

cout<<dis[n][m]<<""<<cnt[n][m]%MOD<<endl;

return0;

}易错点&得分总结1、路径数必须取模,不取模会溢出、答案错误;2、初始距离要设极大值,避免初始状态干扰转移;3、只能向右、向下,不能写上下左右,方

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论