简介面向具有C基础的编程学习者这份真题集完整收录了2024年信息素养大赛C算法创意实践初赛的选择题与编程题。内容覆盖C基础语法、布尔类型、变量声明、关系运算符等理论考点也包含完全数判断、质数识别、区间内数字出现次数统计、平方数装载等代码补全类算法题不少题目需要先拆解数字的各个位数再完成循环与条件判断或者通过累加因子验证完全数对参赛者的逻辑分析和编程实践都是很好的锻炼。资源为单个PDF文件约197KB轻量便携可直接打印或设备阅读方便对照练习。建议先独立完成再结合代码运行结果逐步检验思路。目前已有236人学习下载适合作为赛前自测、专项突破和查漏补缺的练习资料帮助系统熟悉竞赛节奏与常见题型。1. 2024信息素养大赛C算法创意实践初赛到底在考什么2024信息素养大赛的C算法创意实践初赛名字听起来像背题库实际上手才知道它考的不是你背过多少算法模板而是能不能在规定时间里从题目里找出暴力解法、优化到能跑过数据范围并且把代码写对。很多人栽在“会”与“能拿分”之间那道坎上。这篇笔记就围绕这类初赛的常见套路讲清楚怎么拆题、怎么写框架、怎么避坑。这类初赛的受众主要是学过一点C语法、但还没系统练过竞赛题的中学生和大学生也有带队的教练。它的题目风格和传统竞赛题不太一样不绕太深的数学但特别看重“创意实践”——你可以在暴力解法上做一点小优化也可以换个数据结构代码只要跑得对、写得清楚就能拿到大部分分数。所以如果你正准备参赛或者想拿C练练真实场景下的算法落地能力这篇笔记值得看完。后面所有代码都是可以直接复制到本地的通用模板不附加任何平台也不涉及任何大赛官方真题只讲这一类初赛最常见、最可靠的准备路径。2. 先拆题C算法创意实践的题目构成与评分逻辑2.1 题型分布从基础语法到算法思维的阶梯我平时给A同学准备这类比赛第一件事就是让他别把初赛当成“大模拟”来做。大多数初赛卷子按难度分四档前一两道是纯语法题可能要求你处理输入格式、数组逆序、字符串拼接中间一道开始考简单算法比如排序后按规则输出最后一道通常叫“创意实践”题目很短但数据范围很夸张或者处理逻辑有重叠需要你自行设计状态和剪枝。这个排列不是最近两天才变的过去几届基本稳定在这个框架上。所以做题顺序很关键。我一般按“从前往后”做但规定死一个时间前两题总共不超过20分钟。如果某道题读了3分钟还没思路先放下跳去做创意题。为什么这么安排因为初赛的得分往往不按题目难度线性给后一道题一个小数据点的分数可能抵前一道题所有点而它需要的思路时间更长。先保证简单题满分再啃创意题是性价比最高的路线。什么是“创意实践”举个例子题目可以很简单给你n个区间选出尽量多的互不重叠区间。这题一眼贪心但如果n不超过十万且区间坐标大到十的十八次方你可能要用离散化或带一点技巧的排序。另一种风格是“描述很短但状态很多”比如把一个矩阵的某些格子填上数字使得每行每列和相等让你输出方案。这种题没有固定模板考的是你能不能把条件翻译成代码再组织成可运行的程序。从我接触到的练习反馈看创意实践题最常出现的几个主题是区间问题、路径问题、分组问题。区间问题往往和排序、贪心绑定路径问题不是广度优先搜索就是动态规划分组问题常见用深度优先搜索枚举组合。把这些主题拆开练一个主题做三到五道题初赛最后一题就不会一见面就慌。看题时还要学会把长题面翻译成算法标签。题干里出现“求最大/最小”且“每次选择一个状态”优先想贪心和动态规划出现“求方案数”且n在20以内优先深搜枚举出现“给定序列多次查询”注意可能要前缀和、排序预处理。这种翻译能力是把“创意”变成“可执行代码”的第一步。2.2 评分看什么正确性、效率、创意与代码规范初赛大部分采用黑盒评测也就是说你只能通过机试系统提交源码系统跑预设的多组测试数据。正确性自然是最重要的但“效率”和“规范”也在拿分里。很多题数据分档小数据n不超过10大数据n到十万。如果你只会暴力可能拿一半分能优化到O(n log n)或O(n)就接近满分。所以准备的时候一定要养成“看数据范围定复杂度”的习惯。创意实践这部分除了跑分可能还有人工或半人工的评审。这里的“创意”不是要你发明新算法而是看你在常见解法里能否做出合理选择是滚动数组省空间还是用位运算优化常数有没有加注释。换句话说代码整洁是隐性得分点。我见过某同学把暴力代码写得极其混乱结果自己调了一个小时才发现是变量名写错这种亏不要在初赛吃。评分还有一个容易被忽视的点时间限制。同样两个程序一个是O(n^2)一个是O(n log n)n为十万时前者跑一秒多后者几十毫秒初赛机器配置一般前者可能卡在超时边界。所以即使题目没有特别要求你也尽量把复杂度压到数据范围允许的最低宁可用一点空间换时间。还要特别注意“输出格式”。题目要求每行一个数你多打一个空格样例也许不报但裁判数据可能判错。我自己的习惯是把输出语句先在草稿纸上写下格式比如printf(%d\n, ans)再写循环。下面是这类初赛做题顺序的推荐步骤你也可以贴在电脑前面先读完整题目圈出输入数据范围、空格和换行要求。把样例输入手动跑一遍确认输出。写一个绝对正确的暴力版本哪怕很慢先保证小数据全过。再根据数据范围考虑优化优化时保留暴力版本做对拍。最后留10分钟检查数组大小、变量类型、初始化。3. 用C快速搭建解题骨架输入输出与常用STL模板3.1 标准输入输出处理数组、字符串、大整数先解决最容易翻车的第一关读输入。这类初赛的输入格式千变万化但核心就几种一整行读入、多个数字用空格或换行分隔、字符串里夹杂空格。很多人用cin一口气读然后超时。原因很简单cin默认要同步stdio在数据量上百KB时就会慢。常见做法是用ios::sync_with_stdio(false)关同步再配cin.tie(nullptr)大多数题都能过。还有个土办法用scanf读快且稳。#include cstdio using namespace std; int main() { int n; scanf(%d, n); // 读取n个整数并输出两倍值 for (int i 0; i n; i) { int x; scanf(%d, x); printf(%d\n, x 1); } return 0; }逻辑说明这段代码演示scanf和printf的组合。scanf通过格式化字符串%d自动跳过空白空格和换行都能正确分隔x 1相当于x乘2但位运算速度更快。参数说明%d对应int输出用%d加换行如果数据范围超过int上限要换成%lld和long long这是初学者最容易忘的。如果遇到一行里有带空格的字符串比如“hello world”算一个变量scanf的%s会断在空格上这时常用cin.getline或fgets。下面给出一个比较稳的写法。#include iostream #include string using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); string line; getline(cin, line); // 读入一整行保留空格 cout line endl; return 0; }逻辑说明getline会把换行符之前的字符全部读入line适合处理“姓名学号”之类的行。ios::sync_with_stdio(false)是关闭C流与C标准库的同步cin.tie(nullptr)让cin不再每次绑定cout能明显提速。参数说明cin.tie(nullptr)接收一个指针参数传nullptr表示解除绑定。注意关同步后不要再混用cin和scanf、cout和printf否则数据顺序可能错乱。还有一个很容易踩的大数陷阱题目说答案不超过10^18你在代码里用int存中间结果累加几次就溢出。稳妥做法是只要题面出现“可能很大”“超过int范围”这类字样直接全部用long long。尤其是乘法两个int相乘结果可能超过int你必须显式转long long再乘。比如long long prod 1LL * a * b;那个1LL就是用来把计算提升到64位的。3.2 STL三件套vector/map/sort在初赛中的用法初赛里九成的“数据结构”需求用vector、map、sort就能解决。vector做动态数组map做字典统计sort做排序。其它平衡树、跳表之类的结构初赛基本用不上别把时间花在炫技上。下面给一个典型需求给定n个单词统计每个单词出现次数然后按次数降序输出。#include bits/stdc.h using namespace std; int main() { int n; cin n; vectorstring words(n); mapstring, int cnt; for (int i 0; i n; i) { cin words[i]; cnt[words[i]]; // 第一次访问自动初始化为0再自增 } // 把pair拷贝到vector里才能用sort按自定义规则排序 vectorpairstring, int v(cnt.begin(), cnt.end()); sort(v.begin(), v.end(), [](auto a, auto b) { if (a.second ! b.second) return a.second b.second; // 次数降序 return a.first b.first; // 次数相同按字典序 }); for (auto p : v) { cout p.first p.second \n; } return 0; }逻辑说明cnt[key]在key不存在时会对int做零初始化所以cnt[words[i]]能直接计数。排序要求按次数降序用lambda做比较器次数相同时按字典序升序保证输出唯一。参数说明map底层是红黑树插入和查询都是O(log n)n为十万也能接受如果想更快可以用unordered_map但哈希碰撞时可能退化初赛求稳还是map更保险。很多人写sort排序pair时搞混顺序。pair排序默认先比first再比second。如果你要按区间结束时间排序就把结束时间放first如果要按分数排序且同分按名字排也要把分数放first。这个习惯能省很多调试时间。3.3 一个最小可运行程序框架拿分的基础盘你到考场上最好有一个“万能开头”我一般这样写引入bits/stdc.h、打开同步、定义常量数组大小、留一个调试开关。这个框架不花哨但能防止低级错误。下面就是可以直接复制的基础盘后面做任何题都可以在这个框子里改。#include bits/stdc.h using namespace std; const int MAXN 100005; // 根据数据范围调整 int a[MAXN]; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin n; for (int i 0; i n; i) { cin a[i]; } // 在这里开始写解题逻辑 // ... return 0; }逻辑说明数组开在main外面是全局区不用手动初始化就自动清零而且不会占用有限的栈空间。MAXN设成比题目上限略大比如题面说n不超过100000就设100005这是经验值。参数说明如果需要二维数组写成int dp[1005][1005]就够n不超过1000时空间约4MBn超过5000就别再开二维整型了内存会到100MB以上评测机可能直接拒绝。这个基础盘还有一个隐藏优势全局数组在多次测试时天然清零不会因为上一次的脏数据出错。如果数组定义在main里你一定要自己memset或循环初始化。宁可每次多花几毫秒初始化也不要赌初始值一定为0。4. 算法思维核心枚举、贪心、动态规划与搜索4.1 枚举与剪枝用“冗余再减”的思路快速出解创意实践题给的输入小的时候不要一上来就想高深算法。先把所有可能状态枚举一遍拿一个正确结果垫底这一步叫暴力兜底。枚举也有技巧比如用深度优先搜索生成组合而不是写n层for循环。当选出的子集个数k不确定时for循环写不出来递归枚举却能优雅处理。#include bits/stdc.h using namespace std; int n, k, ans -1; vectorint a; int chosen[30]; // start表示从哪个下标开始选remain表示还剩几个要选sum表示当前累计和 void dfs(int start, int remain, int sum) { if (remain 0) { ans max(ans, sum); // 选够了k个更新答案 return; } if (n - start remain) return; // 剩余元素不够剪枝 for (int i start; i n; i) { chosen[remain - 1] a[i]; dfs(i 1, remain - 1, sum a[i]); } } int main() { cin n k; a.resize(n); for (int i 0; i n; i) cin a[i]; dfs(0, k, 0); cout ans \n; return 0; }逻辑说明dfs有三个状态参数start限制只能往后选避免组合重复remain控制还需要选几个sum记录当前累积值。remain为0时更新答案。剪枝那句n - start remain是核心如果后面剩余元素都不够选满k个就没必要继续枚举。参数说明这个写法的最坏复杂度是C(n,k)n为20、k为10时约十八万次递归完全能跑n超过30时这个剪枝不够用需要换成动态规划或数学公式。这个“先枚举、后剪枝”的过程也符合创意实践题的解题节奏。很多题的隐藏测试点故意卡超时但只要n小暴力加剪枝就能过。所以拿到题先看nn不超过20大胆枚举n到十万考虑贪心或动态规划n到十的九次方基本要靠数学公式。4.2 贪心策略如何证明你选的是当前最优贪心在初赛里的地位比很多人想象中高。一个经典例子是“区间选最多不重叠”有n个区间每个区间有开始时间和结束时间要选出尽量多的区间使它们两两不重叠。常见错误是按开始时间排序但正确解法是按结束时间排序每次都选最早结束的区间。#include bits/stdc.h using namespace std; int main() { int n; cin n; vectorpairint, int seg(n); // first存结束时间second存开始时间 for (int i 0; i n; i) { int s, e; cin s e; seg[i] {e, s}; // 按结束时间排序 } sort(seg.begin(), seg.end()); int ans 0, lastEnd -1; for (int i 0; i n; i) { if (seg[i].second lastEnd) { // 当前区间开始时间不小于上一区间结束时间 ans; lastEnd seg[i].first; } } cout ans \n; return 0; }逻辑说明把结束时间放进pair的firstsort自动按结束时间升序排。然后依次判断每个区间能不能接上。这个贪心的正确性要靠“交换论证”证明如果最优解里第一个区间不是最早结束的用最早结束那个替换它也不会让后面的区间更难安排。初赛拿到这种题型直接套模板不要临时改思路。参数说明lastEnd初始设为-1因为区间坐标可能是0这样第一个区间一定可选。贪心的坑在于“感觉能行”和“真的能行”是两回事。我自己的习惯是写完贪心后用暴力枚举在小数据上对拍验证几组随机样例。初赛创意题往往不会有特别刁钻的反例但一旦有你可能整道题零分。所以“能证明”四个字比代码本身更值钱。4.3 动态规划记忆化搜索到递推的落地写法动态规划是初赛最后一道题最常出现的算法。很多同学一看到dp就头疼其实初赛考的动态规划状态都很直白。我给一个思路先用记忆化搜索写出状态转移再改成递推。记忆化搜索的好处是你不用纠结遍历顺序直接用递归写“从当前状态怎么转移”。#include bits/stdc.h using namespace std; int n, m; long long dp[105][105]; long long f(int i, int j) { if (i 1 || j 1) return 0; // 越界返回0 if (i 1 || j 1) return 1; // 第一行或第一列只有一条路径 if (dp[i][j] ! -1) return dp[i][j]; return dp[i][j] f(i - 1, j) f(i, j - 1); } int main() { cin n m; memset(dp, -1, sizeof(dp)); cout f(n, m) \n; return 0; }逻辑说明这是一个n乘m网格只能向右向下走求左上到右下的路径数。状态dp[i][j]表示走到(i,j)的路径数转移是f(i-1,j)f(i,j-1)。第一行和第一列都是边界只能一条路走到底。递归配合记忆化数组避免重复计算。参数说明dp开成105是因为n,m不超过100如果数据范围超过500递归深度可能爆栈这时应改成递推数组。long long dp2[105][105]; for (int i 1; i n; i) { for (int j 1; j m; j) { if (i 1 || j 1) dp2[i][j] 1; else dp2[i][j] dp2[i-1][j] dp2[i][j-1]; } } cout dp2[n][m] \n;逻辑说明递推版和记忆化版状态转移完全一样但执行顺序明确。先初始化第一行第一列然后按行填充。初赛里如果你对递推方向没把握就先写记忆化搜索如果担心栈空间再改递推。创意题常常允许用空间换时间但路径数可能很大要用long long这是最容易忽略的一点。还有一个小技巧递推时要先想清楚“当前状态需要哪些前置状态”。比如grid路径问题dp[i][j]只依赖左边和上边所以按i从小到大、j从小到大填就行。如果你的状态依赖右边和下边就要反向遍历。写错遍历顺序样例过了但隐藏点全挂这种事太常见了。5. 初赛翻车现场编译、运行效率与数据边界的常见问题排查5.1 数组越界和未初始化现象、原因、解决现象是本地跑样例完全正常一提交就“运行错误”或答案错误。原因多半是数组越界或没初始化。全局数组默认是0但main里定义的局部数组不会清零比如int a[1000]; 然后在循环里a[i]i越界就会写进隔壁变量造成极其隐蔽的错误。解决方法是数组如果不需要动态分配一律放main外必须用vector时用vector a(n, 0)显式给初值循环边界严格写i n不要写i n。每写完一个循环回头看一眼下标最大值这一步能救回大半运行错误。5.2 输入读取超时现象、原因、解决现象是同样的算法用cin会超时改成scanf马上过。原因是cin和cout默认与C标准库同步还要频繁刷新缓冲区慢了不止一个量级。解决在main开头加ios::sync_with_stdio(false)和cin.tie(nullptr)然后继续用cin。如果题目数据量特别大且内含大量空格可以直接用scanf或者写一个基于getchar的快速读数字函数。注意关同步后不要再混用scanf和cin否则可能出现读入顺序错乱。还有一种情况是忘记读走换行符用getline读到空字符串原型是空行先getchar吃掉换行再getline。5.3 整数溢出与数据类型选错现象是答案在n为十万时正确n稍大就出错。原因可能是int上限约21亿但累加结果可能超过。解决看到题目要求答案可能超过10^9直接把变量声明为long long。还要注意中间乘法int a,b; long long c a * b;这里a乘b已经在int范围计算溢出了再赋给long long也救不回来。正确写法是long long c 1LL * a * b乘一个1LL强制把计算提升到64位。另外递归函数的返回值也要写long long别和局部变量类型不一致。5.4 创意题“无解输出”与特判现象是题目里没有说明无解时输出什么你随意写了-1导致隐藏点全错。很多初赛题会写“如果不存在输出-1”但有些题不说靠你从样例反推。解决读题时先圈出“无解分支”解题前先把这行写上避免最后忘了。比如搜索题找到一个解就输出循环结束后输出-1。这个一分不花丢分最冤。还有一类特判是输入里有重复值或空输入处理前先想一下n0、n1的情况把特判写在主逻辑之前。6. 进阶把“算法创意”变成你的得分点6.1 如何在题面上找可优化的空间初赛创意题不会直接告诉你“这道题用dp还是贪心”但题干里的数据范围和变量关系会泄露。看到n不超过1000可以用O(n^2)动态规划看到n到十万要么O(n log n)排序要么贪心看到坐标很大优先离散化。另一个优化空间藏在“无解”条件下如果答案不存在你可以在搜索里提前剪掉不可能的分支这比事后特判更省时间。我拿到题后会先写一行注释“n... - 复杂度目标”强迫自己选型。把题目看成“复杂度选择题”创意题就没那么玄学了。6.2 一个实用的输出验证脚本这里给一个我常用的对拍流程适合在家练习也适合初赛前检查代码。你用两个程序一个暴力版一个优化版然后让它们跑同一个随机输入对比输出。下面是一个bash脚本的简化版跑100轮随机数据。for i in $(seq 1 100); do python3 gen.py input.txt ./brute input.txt out1.txt ./solve input.txt out2.txt if ! diff -q out1.txt out2.txt /dev/null; then echo Round $i mismatch break fi done逻辑说明每次循环用gen.py生成随机输入brute是暴力程序solve是优化程序diff比较输出。如果发现不一致就停止用那一组input去调试。参数说明100轮是我常用的次数数据范围大、状态多时可以加到500轮。gen.py要覆盖边界比如n1、n最大、全部相同值等不能全随机否则测不出边界问题。这个脚本在前一天晚上跑一遍第二天考试会踏实很多。6.3 一句话收尾我参加这类初赛时最深的教训是不要在最后一分钟改算法。有一次模拟练习我临时想把一个O(n^2)优化成排序加贪心手一抖把比较器写反全部输出乱掉。从那以后我给自己定了一条规矩——初赛只写自己练过三遍以上的模板新想法在草稿纸上想清楚再动键盘。经验是创意实践的“创意”在于你对已有工具的灵活组合不在于考试现场发明新算法。希望这篇里的框架和坑能帮到你少走我走过的弯路。本文还有配套的精品资源点击获取