hao
f54affb805
- 45页详细PDF学习文档 - 89个知识点全覆盖，含详细说明和代码示例 - AI模型重评分（81个知识点评分变化，黄色高亮标记） - 基于全网深度调研（CSP-J历年真题考点分析） - 涵盖：基础知识、C++程序设计、数据结构、算法、数学
1447 行
69 KiB
HTML
1447 行
69 KiB
HTML
<!DOCTYPE html>
|
||
<html lang="zh-CN">
|
||
<head>
|
||
<meta charset="UTF-8">
|
||
<title>NOI 入门级完整学习手册（2025年修订版）</title>
|
||
<style>
|
||
@page {
|
||
size: A4;
|
||
margin: 2cm 2.5cm;
|
||
}
|
||
body {
|
||
font-family: "Noto Sans SC", "Microsoft YaHei", "SimSun", sans-serif;
|
||
font-size: 11pt;
|
||
line-height: 1.8;
|
||
color: #1a1a1a;
|
||
max-width: 210mm;
|
||
margin: 0 auto;
|
||
padding: 20px;
|
||
}
|
||
h1 {
|
||
text-align: center;
|
||
font-size: 22pt;
|
||
color: #1a237e;
|
||
border-bottom: 3px solid #1a237e;
|
||
padding-bottom: 15px;
|
||
margin-bottom: 5px;
|
||
}
|
||
.subtitle {
|
||
text-align: center;
|
||
font-size: 12pt;
|
||
color: #555;
|
||
margin-bottom: 30px;
|
||
}
|
||
h2 {
|
||
font-size: 16pt;
|
||
color: #283593;
|
||
border-left: 5px solid #283593;
|
||
padding-left: 12px;
|
||
margin-top: 35px;
|
||
page-break-after: avoid;
|
||
}
|
||
h3 {
|
||
font-size: 13pt;
|
||
color: #3949ab;
|
||
margin-top: 25px;
|
||
page-break-after: avoid;
|
||
}
|
||
h4 {
|
||
font-size: 11.5pt;
|
||
color: #5c6bc0;
|
||
margin-top: 18px;
|
||
page-break-after: avoid;
|
||
}
|
||
.score-changed {
|
||
background-color: #fff9c4;
|
||
border: 1px solid #f9a825;
|
||
border-radius: 4px;
|
||
padding: 2px 8px;
|
||
font-size: 10pt;
|
||
font-weight: bold;
|
||
color: #e65100;
|
||
display: inline-block;
|
||
margin: 3px 0;
|
||
}
|
||
.score-same {
|
||
background-color: #e8eaf6;
|
||
border: 1px solid #9fa8da;
|
||
border-radius: 4px;
|
||
padding: 2px 8px;
|
||
font-size: 10pt;
|
||
color: #283593;
|
||
display: inline-block;
|
||
margin: 3px 0;
|
||
}
|
||
.reason {
|
||
font-weight: normal;
|
||
font-size: 9pt;
|
||
color: #795548;
|
||
}
|
||
pre {
|
||
background-color: #f5f5f5;
|
||
border: 1px solid #ddd;
|
||
border-radius: 5px;
|
||
padding: 12px;
|
||
font-size: 9.5pt;
|
||
line-height: 1.5;
|
||
overflow-x: auto;
|
||
font-family: "Consolas", "Courier New", monospace;
|
||
page-break-inside: avoid;
|
||
}
|
||
code {
|
||
font-family: "Consolas", "Courier New", monospace;
|
||
background-color: #f0f0f0;
|
||
padding: 1px 4px;
|
||
border-radius: 3px;
|
||
font-size: 10pt;
|
||
}
|
||
table {
|
||
width: 100%;
|
||
border-collapse: collapse;
|
||
margin: 10px 0;
|
||
font-size: 10pt;
|
||
page-break-inside: avoid;
|
||
}
|
||
th {
|
||
background-color: #283593;
|
||
color: white;
|
||
padding: 8px 10px;
|
||
text-align: left;
|
||
}
|
||
td {
|
||
border: 1px solid #ccc;
|
||
padding: 6px 10px;
|
||
}
|
||
tr:nth-child(even) { background-color: #f5f5f5; }
|
||
.highlight-row { background-color: #fff9c4 !important; }
|
||
.tip {
|
||
background-color: #e3f2fd;
|
||
border-left: 4px solid #1565c0;
|
||
padding: 10px 15px;
|
||
margin: 10px 0;
|
||
font-size: 10pt;
|
||
border-radius: 0 5px 5px 0;
|
||
}
|
||
.warning {
|
||
background-color: #fff3e0;
|
||
border-left: 4px solid #e65100;
|
||
padding: 10px 15px;
|
||
margin: 10px 0;
|
||
font-size: 10pt;
|
||
border-radius: 0 5px 5px 0;
|
||
}
|
||
.toc {
|
||
background-color: #f5f5f5;
|
||
border: 1px solid #ddd;
|
||
border-radius: 8px;
|
||
padding: 20px 30px;
|
||
margin: 20px 0;
|
||
}
|
||
.toc h2 { border: none; padding: 0; margin-top: 0; }
|
||
.toc ul { list-style-type: none; padding-left: 0; }
|
||
.toc li { margin: 5px 0; }
|
||
.toc a { color: #283593; text-decoration: none; }
|
||
.page-break { page-break-before: always; }
|
||
.legend {
|
||
background-color: #fafafa;
|
||
border: 1px solid #ddd;
|
||
border-radius: 5px;
|
||
padding: 12px 15px;
|
||
margin: 15px 0;
|
||
font-size: 10pt;
|
||
}
|
||
</style>
|
||
</head>
|
||
<body>
|
||
|
||
<h1>NOI 入门级完整学习手册</h1>
|
||
<p class="subtitle">基于 NOI 大纲（2025年修订版） | 含全网调研AI重评分 | 详细知识点讲解与代码示例</p>
|
||
|
||
<div class="legend">
|
||
<strong>评分说明：</strong><br>
|
||
<span class="score-changed">黄色背景</span> 表示经过全网深度调研和AI模型重新评估后，评分发生了变化的知识点。<br>
|
||
<span class="score-same">蓝色背景</span> 表示评分与原始大纲一致的知识点。<br>
|
||
评分维度：考试重要性（考频）、学习难度、区分度（拉开差距能力）、实用性（竞赛应用广度），综合1-10分。
|
||
</div>
|
||
|
||
<div class="toc">
|
||
<h2>目 录</h2>
|
||
<ul>
|
||
<li><strong>第一章 基础知识与编程环境</strong></li>
|
||
<li><strong>第二章 C++程序设计</strong></li>
|
||
<li> 2.1 程序基本概念 | 2.2 基本数据类型 | 2.3 程序基本语句</li>
|
||
<li> 2.4 基本运算 | 2.5 数学库常用函数 | 2.6 结构化程序设计</li>
|
||
<li> 2.7 数组 | 2.8 字符串处理 | 2.9 函数与递归</li>
|
||
<li> 2.10 结构体与联合体 | 2.11 指针与引用 | 2.12 文件读写 | 2.13 STL模板</li>
|
||
<li><strong>第三章 数据结构</strong></li>
|
||
<li> 3.1 线性结构 | 3.2 简单树 | 3.3 特殊树 | 3.4 简单图</li>
|
||
<li><strong>第四章 算法</strong></li>
|
||
<li> 4.1 算法概念 | 4.2 入门算法 | 4.3 基础算法 | 4.4 算法策略</li>
|
||
<li> 4.5 数值处理 | 4.6 排序算法 | 4.7 搜索算法 | 4.8 图论算法 | 4.9 动态规划</li>
|
||
<li><strong>第五章 数学与其他</strong></li>
|
||
<li> 5.1 数及其运算 | 5.2 初等数学 | 5.3 初等数论 | 5.4 离散与组合数学</li>
|
||
<li><strong>附录 评分变化汇总表</strong></li>
|
||
</ul>
|
||
</div>
|
||
|
||
<!-- ==================== 第一章 ==================== -->
|
||
<div class="page-break"></div>
|
||
<h2>第一章 基础知识与编程环境</h2>
|
||
|
||
<h3>1.1 计算机的基本构成</h3>
|
||
<p><span class="score-changed">原始评分【1】→ AI重评【2】<span class="reason">(基础重要，竞赛环境必备)</span></span></p>
|
||
<p>计算机系统由<strong>硬件</strong>和<strong>软件</strong>两大部分组成。硬件是计算机的物理组成部分，主要包括以下核心组件：</p>
|
||
<table>
|
||
<tr><th>组件</th><th>功能说明</th><th>竞赛关注点</th></tr>
|
||
<tr><td><strong>CPU（中央处理器）</strong></td><td>执行指令和运算的核心部件，包含运算器和控制器</td><td>理解时间复杂度的物理基础</td></tr>
|
||
<tr><td><strong>内存（RAM）</strong></td><td>临时存储正在运行的程序和数据，断电后数据丢失</td><td>理解空间复杂度、数组大小限制</td></tr>
|
||
<tr><td><strong>外存（硬盘/SSD）</strong></td><td>永久存储数据和程序</td><td>文件读写操作的基础</td></tr>
|
||
<tr><td><strong>输入设备</strong></td><td>键盘、鼠标等，用于向计算机输入数据</td><td>标准输入(stdin)</td></tr>
|
||
<tr><td><strong>输出设备</strong></td><td>显示器、打印机等，用于输出处理结果</td><td>标准输出(stdout)</td></tr>
|
||
</table>
|
||
<div class="tip"><strong>竞赛要点：</strong>在NOI竞赛中，程序的运行时间和内存使用都有严格限制（通常时间1-2秒，内存256MB）。理解CPU执行速度（约10<sup>8</sup>-10<sup>9</sup>次基本运算/秒）和内存容量对于估算算法可行性至关重要。</div>
|
||
|
||
<h3>1.2 操作系统基本概念</h3>
|
||
<p><span class="score-changed">原始评分【1】→ AI重评【2】<span class="reason">(环境操作基础，实用性提升)</span></span></p>
|
||
<p>操作系统（Operating System, OS）是管理计算机硬件和软件资源的系统软件。NOI竞赛环境主要使用<strong>Linux</strong>操作系统（NOI Linux 2.0，基于Ubuntu 20.04）。选手需要了解操作系统的基本功能：进程管理、内存管理、文件系统管理和设备管理。</p>
|
||
|
||
<h3>1.3 计算机网络和Internet基本概念</h3>
|
||
<p><span class="score-same">难度评级【1】</span></p>
|
||
<p>了解计算机网络的基本概念，包括局域网（LAN）、广域网（WAN）、Internet的基本架构、IP地址、域名系统（DNS）等。此部分在CSP-J初赛中偶有考察。</p>
|
||
|
||
<h3>1.4 计算机的历史和常见用途</h3>
|
||
<p><span class="score-same">难度评级【1】</span></p>
|
||
<p>了解计算机发展的重要里程碑：从ENIAC（1946年）到现代计算机。了解图灵（Alan Turing）、冯·诺依曼（John von Neumann）等计算机科学先驱的贡献。冯·诺依曼体系结构（存储程序概念）是现代计算机的基础架构。</p>
|
||
|
||
<h3>1.5 NOI相关活动的历史与规则</h3>
|
||
<p><span class="score-same">难度评级【1】</span></p>
|
||
<p>NOI（全国青少年信息学奥林匹克竞赛）由中国计算机学会（CCF）主办。竞赛体系包括：CSP-J/S（非专业级软件能力认证）→ NOIP（联赛）→ NOI（国赛）→ IOI（国际赛）。CSP-J为入门级认证，面向初中及以下学生。</p>
|
||
|
||
<h3>1.6 位、字节与字</h3>
|
||
<p><span class="score-changed">原始评分【1】→ AI重评【3】<span class="reason">(位运算基础，竞赛常用)</span></span></p>
|
||
<p>计算机中数据的最小单位是<strong>位（bit）</strong>，只能存储0或1。8个位组成一个<strong>字节（Byte）</strong>。<strong>字（Word）</strong>的大小取决于CPU架构（32位或64位）。</p>
|
||
<table>
|
||
<tr><th>单位</th><th>大小</th><th>常见应用</th></tr>
|
||
<tr><td>1 bit</td><td>0 或 1</td><td>bool类型的逻辑值</td></tr>
|
||
<tr><td>1 Byte = 8 bits</td><td>0~255（无符号）</td><td>char类型</td></tr>
|
||
<tr><td>4 Bytes = 32 bits</td><td>约±21亿</td><td>int类型</td></tr>
|
||
<tr><td>8 Bytes = 64 bits</td><td>约±9.2×10<sup>18</sup></td><td>long long类型</td></tr>
|
||
</table>
|
||
<div class="warning"><strong>注意：</strong>CSP-J近年真题中多次出现需要使用<code>long long</code>类型的题目。当数据范围超过2×10<sup>9</sup>时，必须使用<code>long long</code>。</div>
|
||
|
||
<h3>1.7 程序设计语言及编译运行基本概念</h3>
|
||
<p><span class="score-changed">原始评分【1】→ AI重评【2】<span class="reason">(理解编译流程重要)</span></span></p>
|
||
<p>程序设计语言分为<strong>低级语言</strong>（机器语言、汇编语言）和<strong>高级语言</strong>（C、C++、Python等）。NOI系列竞赛使用<strong>C++</strong>语言。C++程序需要经过<strong>编译</strong>（将源代码转换为机器代码）才能运行，编译器将<code>.cpp</code>源文件编译为可执行文件。</p>
|
||
|
||
<h3>1.8 文件/目录的图形界面操作</h3>
|
||
<p><span class="score-same">难度评级【1】</span></p>
|
||
<p>掌握在Windows或Linux图形界面中进行文件和目录的基本操作：创建、复制、移动、删除、重命名文件和文件夹。</p>
|
||
|
||
<h3>1.9 集成开发环境（IDE）使用</h3>
|
||
<p><span class="score-changed">原始评分【1】→ AI重评【2】<span class="reason">(开发环境熟悉度重要)</span></span></p>
|
||
<p>常用的C++ IDE包括：Windows下的<strong>Dev-C++</strong>（轻量级，适合入门）、<strong>Code::Blocks</strong>（跨平台）、<strong>Visual Studio Code</strong>（功能强大）。Linux下可使用Code::Blocks或命令行编辑器（如vim、nano）配合g++编译器。</p>
|
||
|
||
<h3>1.10 编译命令g++的基本使用</h3>
|
||
<p><span class="score-changed">原始评分【1】→ AI重评【3】<span class="reason">(编译命令基础，实用性强)</span></span></p>
|
||
<p>g++是GNU C++编译器，是NOI竞赛环境中的标准编译器。基本使用方法：</p>
|
||
<pre>
|
||
# 基本编译
|
||
g++ -o program source.cpp
|
||
|
||
# 带优化的编译（竞赛常用）
|
||
g++ -O2 -o program source.cpp
|
||
|
||
# 编译并启用C++14标准
|
||
g++ -std=c++14 -O2 -o program source.cpp
|
||
|
||
# 运行程序
|
||
./program
|
||
</pre>
|
||
|
||
<!-- ==================== 第二章 ==================== -->
|
||
<div class="page-break"></div>
|
||
<h2>第二章 C++程序设计</h2>
|
||
|
||
<h3>2.1 程序基本概念</h3>
|
||
|
||
<h4>2.1.1 标识符、关键字、常量、变量、表达式</h4>
|
||
<p><span class="score-changed">原始评分【1】→ AI重评【3】<span class="reason">(编程基础，必备知识)</span></span></p>
|
||
<p><strong>标识符</strong>是程序中用来命名变量、函数、类型等的名称，由字母、数字和下划线组成，不能以数字开头。<strong>关键字</strong>是C++语言保留的具有特殊含义的标识符（如<code>int</code>、<code>if</code>、<code>for</code>、<code>return</code>等），不能用作变量名。</p>
|
||
<pre>
|
||
// 合法标识符
|
||
int count = 0;
|
||
double totalScore = 95.5;
|
||
int _value = 10;
|
||
|
||
// 非法标识符
|
||
// int 2nd = 5; // 不能以数字开头
|
||
// int class = 1; // class是关键字
|
||
</pre>
|
||
|
||
<h4>2.1.2 常量与变量的命名、定义及作用</h4>
|
||
<p><span class="score-changed">原始评分【1】→ AI重评【3】<span class="reason">(基础语法，重要性提升)</span></span></p>
|
||
<p><strong>常量</strong>是程序运行期间值不会改变的量，使用<code>const</code>关键字定义。<strong>变量</strong>是可以在程序运行过程中改变其值的量。</p>
|
||
<pre>
|
||
const int MAXN = 100005; // 常量，竞赛中常用于定义数组大小
|
||
const double PI = 3.14159265358979;
|
||
int n, m; // 变量
|
||
</pre>
|
||
|
||
<h4>2.1.3 头文件与名字空间</h4>
|
||
<p><span class="score-changed">原始评分【2】→ AI重评【3】<span class="reason">(代码组织关键)</span></span></p>
|
||
<p><strong>头文件</strong>包含了函数声明和宏定义。竞赛中常用<code>#include <bits/stdc++.h></code>万能头文件（包含所有标准库）。<strong>名字空间</strong>用于避免命名冲突，竞赛中常用<code>using namespace std;</code>。</p>
|
||
<pre>
|
||
#include <bits/stdc++.h> // 万能头文件（竞赛专用）
|
||
using namespace std; // 使用标准命名空间
|
||
|
||
int main() {
|
||
// 程序代码
|
||
return 0;
|
||
}
|
||
</pre>
|
||
|
||
<h4>2.1.4 编辑、编译、解释、调试概念</h4>
|
||
<p><span class="score-changed">原始评分【2】→ AI重评【3】<span class="reason">(调试能力重要)</span></span></p>
|
||
<p><strong>编辑</strong>是编写源代码的过程。<strong>编译</strong>是将源代码翻译成机器代码的过程（C++使用编译方式）。<strong>解释</strong>是逐行翻译并执行源代码（如Python）。<strong>调试</strong>是查找和修复程序错误的过程。</p>
|
||
|
||
<h3>2.2 基本数据类型</h3>
|
||
<p><span class="score-changed">原始评分【1】→ AI重评【3】<span class="reason">(类型理解基础)</span></span></p>
|
||
<table>
|
||
<tr><th>类型</th><th>大小</th><th>范围</th><th>用途</th></tr>
|
||
<tr><td><code>int</code></td><td>4字节</td><td>-2<sup>31</sup> ~ 2<sup>31</sup>-1（约±2.1×10<sup>9</sup>）</td><td>常规整数</td></tr>
|
||
<tr><td><code>long long</code></td><td>8字节</td><td>-2<sup>63</sup> ~ 2<sup>63</sup>-1（约±9.2×10<sup>18</sup>）</td><td>大整数</td></tr>
|
||
<tr><td><code>float</code></td><td>4字节</td><td>约7位有效数字</td><td>单精度浮点（少用）</td></tr>
|
||
<tr><td><code>double</code></td><td>8字节</td><td>约15位有效数字</td><td>双精度浮点</td></tr>
|
||
<tr><td><code>char</code></td><td>1字节</td><td>-128 ~ 127 或 0 ~ 255</td><td>字符</td></tr>
|
||
<tr><td><code>bool</code></td><td>1字节</td><td>true(1) 或 false(0)</td><td>逻辑值</td></tr>
|
||
</table>
|
||
<div class="warning"><strong>竞赛常见错误：</strong>当题目数据范围超过2×10<sup>9</sup>时忘记使用<code>long long</code>，导致整数溢出。建议养成习惯：看到大数据范围立即使用<code>long long</code>。</div>
|
||
|
||
<h3>2.3 程序基本语句</h3>
|
||
|
||
<h4>2.3.1 输入输出语句</h4>
|
||
<p><span class="score-changed">原始评分【2】→ AI重评【3】<span class="reason">(IO基础，频繁使用)</span></span></p>
|
||
<pre>
|
||
#include <bits/stdc++.h>
|
||
using namespace std;
|
||
int main() {
|
||
int n;
|
||
// C++风格输入输出
|
||
cin >> n;
|
||
cout << "n = " << n << endl;
|
||
|
||
// C风格输入输出（通常更快）
|
||
scanf("%d", &n);
|
||
printf("n = %d\n", n);
|
||
|
||
return 0;
|
||
}
|
||
</pre>
|
||
<div class="tip"><strong>性能提示：</strong>在大数据量输入时，<code>scanf/printf</code>比<code>cin/cout</code>更快。如果使用<code>cin/cout</code>，可以添加<code>ios::sync_with_stdio(false); cin.tie(0);</code>来加速。</div>
|
||
|
||
<h4>2.3.2 条件语句</h4>
|
||
<p><span class="score-changed">原始评分【2】→ AI重评【3】<span class="reason">(控制流基础)</span></span></p>
|
||
<pre>
|
||
// if-else语句
|
||
if (score >= 90) {
|
||
cout << "优秀" << endl;
|
||
} else if (score >= 60) {
|
||
cout << "及格" << endl;
|
||
} else {
|
||
cout << "不及格" << endl;
|
||
}
|
||
|
||
// switch语句
|
||
switch (grade) {
|
||
case 'A': cout << "优秀"; break;
|
||
case 'B': cout << "良好"; break;
|
||
default: cout << "其他"; break;
|
||
}
|
||
</pre>
|
||
|
||
<h4>2.3.3 循环语句</h4>
|
||
<p><span class="score-changed">原始评分【2】→ AI重评【3】<span class="reason">(循环结构核心)</span></span></p>
|
||
<pre>
|
||
// for循环 - 最常用
|
||
for (int i = 0; i < n; i++) {
|
||
// 循环体
|
||
}
|
||
|
||
// while循环
|
||
while (条件) {
|
||
// 循环体
|
||
}
|
||
|
||
// do-while循环（至少执行一次）
|
||
do {
|
||
// 循环体
|
||
} while (条件);
|
||
</pre>
|
||
|
||
<h4>2.3.4 多层循环语句</h4>
|
||
<p><span class="score-changed">原始评分【3】→ AI重评【4】<span class="reason">(复杂度提升，常见考点)</span></span></p>
|
||
<p>多层循环（嵌套循环）在竞赛中非常常见，用于处理二维数组、枚举多个变量等场景。需要注意<strong>时间复杂度</strong>：两层循环为O(n<sup>2</sup>)，三层为O(n<sup>3</sup>)。</p>
|
||
<pre>
|
||
// 打印九九乘法表
|
||
for (int i = 1; i <= 9; i++) {
|
||
for (int j = 1; j <= i; j++) {
|
||
printf("%d×%d=%-3d", j, i, i * j);
|
||
}
|
||
printf("\n");
|
||
}
|
||
</pre>
|
||
|
||
<h3>2.4 基本运算</h3>
|
||
|
||
<h4>2.4.1 算术/关系/逻辑运算</h4>
|
||
<p><span class="score-changed">原始评分【1】→ AI重评【3】<span class="reason">(运算基础，频繁使用)</span></span></p>
|
||
<table>
|
||
<tr><th>运算类型</th><th>运算符</th><th>示例</th><th>说明</th></tr>
|
||
<tr><td rowspan="5">算术运算</td><td><code>+</code> <code>-</code> <code>*</code></td><td><code>a + b</code></td><td>加减乘</td></tr>
|
||
<tr><td><code>/</code></td><td><code>7 / 2 = 3</code></td><td>整数除法取整</td></tr>
|
||
<tr><td><code>%</code></td><td><code>7 % 2 = 1</code></td><td>取余（模运算）</td></tr>
|
||
<tr><td><code>++</code> <code>--</code></td><td><code>i++</code></td><td>自增自减</td></tr>
|
||
<tr><td><code>?:</code></td><td><code>a>b ? a : b</code></td><td>三目运算</td></tr>
|
||
<tr><td>关系运算</td><td><code>> >= < <= == !=</code></td><td><code>a == b</code></td><td>返回bool值</td></tr>
|
||
<tr><td>逻辑运算</td><td><code>&& || !</code></td><td><code>a>0 && b>0</code></td><td>与、或、非</td></tr>
|
||
</table>
|
||
|
||
<h4>2.4.2 位运算</h4>
|
||
<p><span class="score-changed">原始评分【2】→ AI重评【5】<span class="reason">(高频考点，难度较大)</span></span></p>
|
||
<p>位运算直接操作二进制位，在竞赛中应用广泛（状态压缩、快速判断奇偶等）。</p>
|
||
<table>
|
||
<tr><th>运算符</th><th>名称</th><th>示例</th><th>结果</th><th>常见用途</th></tr>
|
||
<tr><td><code>&</code></td><td>按位与</td><td><code>5 & 3</code> (101 & 011)</td><td>1 (001)</td><td>判断奇偶：<code>n & 1</code></td></tr>
|
||
<tr><td><code>|</code></td><td>按位或</td><td><code>5 | 3</code> (101 | 011)</td><td>7 (111)</td><td>设置某一位</td></tr>
|
||
<tr><td><code>^</code></td><td>按位异或</td><td><code>5 ^ 3</code> (101 ^ 011)</td><td>6 (110)</td><td>交换两数、加密</td></tr>
|
||
<tr><td><code>~</code></td><td>按位取反</td><td><code>~5</code></td><td>-6</td><td>补码运算</td></tr>
|
||
<tr><td><code><<</code></td><td>左移</td><td><code>1 << 3</code></td><td>8</td><td>乘以2的幂</td></tr>
|
||
<tr><td><code>>></code></td><td>右移</td><td><code>8 >> 2</code></td><td>2</td><td>除以2的幂</td></tr>
|
||
</table>
|
||
<pre>
|
||
// 位运算常见技巧
|
||
int n = 10;
|
||
if (n & 1) cout << "奇数"; else cout << "偶数"; // 判断奇偶
|
||
int x = 1 << 10; // x = 1024，即2^10
|
||
// 交换两个数（不用临时变量）
|
||
a ^= b; b ^= a; a ^= b;
|
||
</pre>
|
||
|
||
<h3>2.5 数学库常用函数</h3>
|
||
<p><span class="score-changed">原始评分【3】→ AI重评【4】<span class="reason">(数学思维增强)</span></span></p>
|
||
<table>
|
||
<tr><th>函数</th><th>功能</th><th>示例</th></tr>
|
||
<tr><td><code>abs(x)</code></td><td>绝对值</td><td><code>abs(-5) = 5</code></td></tr>
|
||
<tr><td><code>sqrt(x)</code></td><td>平方根</td><td><code>sqrt(16) = 4.0</code></td></tr>
|
||
<tr><td><code>ceil(x)</code></td><td>上取整</td><td><code>ceil(3.2) = 4</code></td></tr>
|
||
<tr><td><code>floor(x)</code></td><td>下取整</td><td><code>floor(3.8) = 3</code></td></tr>
|
||
<tr><td><code>round(x)</code></td><td>四舍五入</td><td><code>round(3.5) = 4</code></td></tr>
|
||
<tr><td><code>pow(x,y)</code></td><td>x的y次方</td><td><code>pow(2,10) = 1024</code></td></tr>
|
||
<tr><td><code>log(x)</code></td><td>自然对数</td><td><code>log(e) = 1.0</code></td></tr>
|
||
<tr><td><code>log2(x)</code></td><td>以2为底的对数</td><td><code>log2(8) = 3.0</code></td></tr>
|
||
</table>
|
||
|
||
<h3>2.6 结构化程序设计</h3>
|
||
<p><span class="score-changed">原始评分【1】→ AI重评【3】<span class="reason">(基础结构，重要性提升)</span></span> <span class="score-changed">原始评分【2】→ AI重评【3】<span class="reason">(代码组织与设计)</span></span></p>
|
||
<p>程序的三种基本结构：<strong>顺序结构</strong>（按顺序执行）、<strong>分支结构</strong>（条件判断）、<strong>循环结构</strong>（重复执行）。模块化程序设计将复杂问题分解为若干子问题，每个子问题用一个函数实现。</p>
|
||
|
||
<h3>2.7 数组</h3>
|
||
|
||
<h4>2.7.1 一维数组</h4>
|
||
<p><span class="score-changed">原始评分【1】→ AI重评【4】<span class="reason">(基础数据结构，应用广)</span></span></p>
|
||
<p>数组是存储相同类型元素的连续内存空间。数组下标从0开始。</p>
|
||
<pre>
|
||
int a[100005]; // 定义数组，竞赛中通常开大一些
|
||
int n;
|
||
cin >> n;
|
||
for (int i = 0; i < n; i++) {
|
||
cin >> a[i]; // 读入数组
|
||
}
|
||
// 求数组元素之和
|
||
long long sum = 0;
|
||
for (int i = 0; i < n; i++) {
|
||
sum += a[i];
|
||
}
|
||
</pre>
|
||
|
||
<h4>2.7.2 二维数组与多维数组</h4>
|
||
<p><span class="score-changed">原始评分【3】→ AI重评【4】<span class="reason">(常见数据结构)</span></span></p>
|
||
<pre>
|
||
int grid[105][105]; // 二维数组，常用于矩阵、地图
|
||
int n, m;
|
||
cin >> n >> m;
|
||
for (int i = 0; i < n; i++)
|
||
for (int j = 0; j < m; j++)
|
||
cin >> grid[i][j];
|
||
</pre>
|
||
|
||
<h3>2.8 字符串处理</h3>
|
||
<p><span class="score-changed">原始评分【2】→ AI重评【4】<span class="reason">(字符串处理基础)</span></span></p>
|
||
<p>C++中处理字符串有两种方式：<strong>字符数组</strong>（C风格）和<strong>string类</strong>（C++风格，推荐）。</p>
|
||
<pre>
|
||
// string类常用操作
|
||
string s = "hello";
|
||
int len = s.length(); // 长度：5
|
||
s += " world"; // 拼接："hello world"
|
||
string sub = s.substr(0, 5); // 子串："hello"
|
||
int pos = s.find("world"); // 查找：6
|
||
char c = s[0]; // 访问字符：'h'
|
||
|
||
// 字符数组
|
||
char str[105];
|
||
scanf("%s", str);
|
||
int len2 = strlen(str);
|
||
</pre>
|
||
|
||
<h3>2.9 函数与递归</h3>
|
||
|
||
<h4>2.9.1 函数定义与调用</h4>
|
||
<p><span class="score-changed">原始评分【2】→ AI重评【5】<span class="reason">(递归难点，重要考点)</span></span></p>
|
||
<pre>
|
||
// 函数定义
|
||
int gcd(int a, int b) {
|
||
if (b == 0) return a;
|
||
return gcd(b, a % b); // 递归调用
|
||
}
|
||
|
||
// 函数调用
|
||
int result = gcd(12, 8); // result = 4
|
||
</pre>
|
||
|
||
<h4>2.9.2 传值与传引用参数</h4>
|
||
<p><span class="score-changed">原始评分【3】→ AI重评【4】<span class="reason">(参数传递细节重要)</span></span></p>
|
||
<pre>
|
||
// 传值：函数内修改不影响原变量
|
||
void addOne(int x) { x++; }
|
||
|
||
// 传引用：函数内修改会影响原变量
|
||
void addOne(int &x) { x++; }
|
||
|
||
int a = 5;
|
||
addOne(a); // 传引用后 a = 6
|
||
</pre>
|
||
|
||
<h3>2.10 结构体与联合体</h3>
|
||
<p><span class="score-changed">原始评分【3】→ AI重评【4】<span class="reason">(数据组织关键)</span></span></p>
|
||
<pre>
|
||
// 结构体：将不同类型的数据组合在一起
|
||
struct Student {
|
||
string name;
|
||
int score;
|
||
bool operator < (const Student &other) const {
|
||
return score > other.score; // 按分数降序排序
|
||
}
|
||
};
|
||
|
||
Student stu[105];
|
||
sort(stu, stu + n); // 使用自定义排序
|
||
</pre>
|
||
|
||
<h3>2.11 指针与引用</h3>
|
||
<p><span class="score-changed">原始评分【4】→ AI重评【5】<span class="reason">(核心难点，区分度高)</span></span></p>
|
||
<p>指针存储变量的内存地址，引用是变量的别名。在竞赛中，指针主要用于链表、树等数据结构的实现。</p>
|
||
<pre>
|
||
int x = 10;
|
||
int *p = &x; // p指向x的地址
|
||
cout << *p; // 解引用，输出10
|
||
*p = 20; // 通过指针修改x的值
|
||
|
||
int &ref = x; // ref是x的引用（别名）
|
||
ref = 30; // 等价于 x = 30
|
||
</pre>
|
||
|
||
<h3>2.12 文件读写</h3>
|
||
<p><span class="score-changed">原始评分【2】→ AI重评【3】<span class="reason">(竞赛中偶尔应用)</span></span></p>
|
||
<pre>
|
||
// 文件重定向（竞赛常用）
|
||
freopen("input.txt", "r", stdin);
|
||
freopen("output.txt", "w", stdout);
|
||
|
||
// C++文件流
|
||
ifstream fin("input.txt");
|
||
ofstream fout("output.txt");
|
||
int n;
|
||
fin >> n;
|
||
fout << n << endl;
|
||
</pre>
|
||
|
||
<h3>2.13 STL模板</h3>
|
||
|
||
<h4>2.13.1 常用函数</h4>
|
||
<p><span class="score-changed">原始评分【3】→ AI重评【5】<span class="reason">(高频实用，效率提升)</span></span></p>
|
||
<pre>
|
||
#include <bits/stdc++.h>
|
||
using namespace std;
|
||
|
||
int a[] = {3, 1, 4, 1, 5, 9, 2, 6};
|
||
int n = 8;
|
||
|
||
sort(a, a + n); // 排序：1 1 2 3 4 5 6 9
|
||
sort(a, a + n, greater<int>()); // 降序排序
|
||
int mx = *max_element(a, a + n); // 最大值
|
||
int mn = *min_element(a, a + n); // 最小值
|
||
swap(a[0], a[1]); // 交换两个元素
|
||
reverse(a, a + n); // 反转数组
|
||
</pre>
|
||
|
||
<h4>2.13.2 STL容器</h4>
|
||
<p><span class="score-changed">原始评分【4】→ AI重评【6】<span class="reason">(竞赛必备，应用广泛)</span></span></p>
|
||
<table>
|
||
<tr><th>容器</th><th>特点</th><th>常用操作</th><th>竞赛应用</th></tr>
|
||
<tr><td><code>vector</code></td><td>动态数组</td><td>push_back, size, []</td><td>邻接表、动态存储</td></tr>
|
||
<tr><td><code>stack</code></td><td>后进先出</td><td>push, pop, top</td><td>表达式求值、括号匹配</td></tr>
|
||
<tr><td><code>queue</code></td><td>先进先出</td><td>push, pop, front</td><td>BFS</td></tr>
|
||
<tr><td><code>list</code></td><td>双向链表</td><td>push_back, insert</td><td>频繁插入删除</td></tr>
|
||
</table>
|
||
<pre>
|
||
// vector示例
|
||
vector<int> v;
|
||
v.push_back(10);
|
||
v.push_back(20);
|
||
for (int i = 0; i < v.size(); i++) cout << v[i] << " ";
|
||
|
||
// stack示例
|
||
stack<int> st;
|
||
st.push(1); st.push(2); st.push(3);
|
||
while (!st.empty()) {
|
||
cout << st.top() << " "; // 输出 3 2 1
|
||
st.pop();
|
||
}
|
||
|
||
// queue示例（BFS常用）
|
||
queue<int> q;
|
||
q.push(1); q.push(2);
|
||
while (!q.empty()) {
|
||
int front = q.front(); q.pop();
|
||
cout << front << " "; // 输出 1 2
|
||
}
|
||
</pre>
|
||
|
||
<!-- ==================== 第三章 ==================== -->
|
||
<div class="page-break"></div>
|
||
<h2>第三章 数据结构</h2>
|
||
|
||
<h3>3.1 线性结构</h3>
|
||
|
||
<h4>3.1.1 链表</h4>
|
||
<p><span class="score-changed">原始评分【3】→ AI重评【4】<span class="reason">(数据结构基础)</span></span></p>
|
||
<p>链表是一种动态数据结构，每个节点包含数据域和指针域。与数组相比，链表支持O(1)的插入和删除，但不支持随机访问。</p>
|
||
<pre>
|
||
// 静态链表（竞赛常用，避免动态内存分配）
|
||
struct Node {
|
||
int val, next;
|
||
} nodes[100005];
|
||
int head = -1, cnt = 0;
|
||
|
||
void insert(int val) { // 头插法
|
||
nodes[cnt] = {val, head};
|
||
head = cnt++;
|
||
}
|
||
</pre>
|
||
|
||
<h4>3.1.2 栈</h4>
|
||
<p><span class="score-changed">原始评分【3】→ AI重评【5】<span class="reason">(高频考点，应用广)</span></span></p>
|
||
<p>栈是一种<strong>后进先出（LIFO）</strong>的数据结构。在CSP-J中，栈常用于表达式求值、括号匹配、单调栈等场景。</p>
|
||
<pre>
|
||
// 括号匹配示例
|
||
bool isValid(string s) {
|
||
stack<char> st;
|
||
for (char c : s) {
|
||
if (c == '(' || c == '[' || c == '{') st.push(c);
|
||
else {
|
||
if (st.empty()) return false;
|
||
char top = st.top(); st.pop();
|
||
if (c == ')' && top != '(') return false;
|
||
if (c == ']' && top != '[') return false;
|
||
if (c == '}' && top != '{') return false;
|
||
}
|
||
}
|
||
return st.empty();
|
||
}
|
||
</pre>
|
||
|
||
<h4>3.1.3 队列</h4>
|
||
<p><span class="score-changed">原始评分【3】→ AI重评【5】<span class="reason">(高频考点，应用广)</span></span></p>
|
||
<p>队列是一种<strong>先进先出（FIFO）</strong>的数据结构。在CSP-J中，队列是BFS（广度优先搜索）的核心数据结构。</p>
|
||
|
||
<h3>3.2 简单树</h3>
|
||
|
||
<h4>3.2.1 树的定义与基本概念</h4>
|
||
<p><span class="score-changed">原始评分【3】→ AI重评【5】<span class="reason">(基础数据结构)</span></span></p>
|
||
<p>树是一种非线性数据结构，由节点和边组成。重要概念包括：<strong>根节点</strong>、<strong>叶子节点</strong>（无子节点）、<strong>父节点</strong>、<strong>子节点</strong>、<strong>深度</strong>（根到该节点的路径长度）、<strong>高度</strong>（该节点到最深叶子的路径长度）。</p>
|
||
|
||
<h4>3.2.2 二叉树</h4>
|
||
<p><span class="score-changed">原始评分【3】→ AI重评【5】<span class="reason">(基础树结构)</span></span></p>
|
||
<p>二叉树是每个节点最多有两个子节点（左子节点和右子节点）的树。基本性质：</p>
|
||
<table>
|
||
<tr><th>性质</th><th>描述</th></tr>
|
||
<tr><td>第i层最多节点数</td><td>2<sup>i-1</sup></td></tr>
|
||
<tr><td>深度为k的二叉树最多节点数</td><td>2<sup>k</sup> - 1</td></tr>
|
||
<tr><td>叶子节点数 = 度为2的节点数 + 1</td><td>n<sub>0</sub> = n<sub>2</sub> + 1</td></tr>
|
||
</table>
|
||
|
||
<h4>3.2.3 树/二叉树的表示与存储</h4>
|
||
<p><span class="score-changed">原始评分【4】→ AI重评【6】<span class="reason">(存储实现关键)</span></span></p>
|
||
<pre>
|
||
// 二叉树的数组存储（适用于完全二叉树）
|
||
int tree[100005]; // tree[1]为根，tree[2i]为左子，tree[2i+1]为右子
|
||
|
||
// 二叉树的链式存储
|
||
struct TreeNode {
|
||
int val;
|
||
int left, right; // 左右子节点编号
|
||
} nodes[100005];
|
||
</pre>
|
||
|
||
<h4>3.2.4 二叉树的遍历</h4>
|
||
<p><span class="score-changed">原始评分【4】→ AI重评【6】<span class="reason">(遍历是基础技能)</span></span></p>
|
||
<pre>
|
||
// 前序遍历：根 → 左 → 右
|
||
void preorder(int u) {
|
||
if (u == -1) return;
|
||
cout << nodes[u].val << " ";
|
||
preorder(nodes[u].left);
|
||
preorder(nodes[u].right);
|
||
}
|
||
|
||
// 中序遍历：左 → 根 → 右
|
||
void inorder(int u) {
|
||
if (u == -1) return;
|
||
inorder(nodes[u].left);
|
||
cout << nodes[u].val << " ";
|
||
inorder(nodes[u].right);
|
||
}
|
||
|
||
// 后序遍历：左 → 右 → 根
|
||
void postorder(int u) {
|
||
if (u == -1) return;
|
||
postorder(nodes[u].left);
|
||
postorder(nodes[u].right);
|
||
cout << nodes[u].val << " ";
|
||
}
|
||
</pre>
|
||
|
||
<h3>3.3 特殊树</h3>
|
||
|
||
<h4>3.3.1 完全二叉树</h4>
|
||
<p><span class="score-changed">原始评分【4】→ AI重评【6】<span class="reason">(重要树结构)</span></span></p>
|
||
<p>完全二叉树是除最后一层外每层都满的二叉树，最后一层的节点从左到右连续排列。可以用数组高效存储：节点i的左子节点为2i，右子节点为2i+1，父节点为i/2。</p>
|
||
|
||
<h4>3.3.2 哈夫曼树与哈夫曼编码</h4>
|
||
<p><span class="score-changed">原始评分【4】→ AI重评【5】<span class="reason">(经典算法，应用有限)</span></span></p>
|
||
<p>哈夫曼树是带权路径长度最短的二叉树。构造方法：每次取权值最小的两个节点合并。哈夫曼编码是一种最优前缀编码，用于数据压缩。</p>
|
||
|
||
<h4>3.3.3 二叉搜索树（BST）</h4>
|
||
<p><span class="score-changed">原始评分【4】→ AI重评【5】<span class="reason">(重要树结构)</span></span></p>
|
||
<p>二叉搜索树满足：左子树所有节点值 < 根节点值 < 右子树所有节点值。中序遍历BST可以得到有序序列。</p>
|
||
|
||
<h3>3.4 简单图</h3>
|
||
|
||
<h4>3.4.1 图的定义与相关概念</h4>
|
||
<p><span class="score-changed">原始评分【3】→ AI重评【5】<span class="reason">(图论基础)</span></span></p>
|
||
<p>图由<strong>顶点（Vertex）</strong>和<strong>边（Edge）</strong>组成。图分为<strong>有向图</strong>和<strong>无向图</strong>。重要概念：度（与顶点相连的边数）、路径、环、连通性。</p>
|
||
|
||
<h4>3.4.2 图的存储</h4>
|
||
<p><span class="score-changed">原始评分【4】→ AI重评【6】<span class="reason">(图论基础实现)</span></span></p>
|
||
<pre>
|
||
// 邻接矩阵（适用于稠密图）
|
||
int adj[505][505]; // adj[i][j] = 1 表示i到j有边
|
||
adj[u][v] = 1;
|
||
adj[v][u] = 1; // 无向图
|
||
|
||
// 邻接表（适用于稀疏图，竞赛常用）
|
||
vector<int> G[100005];
|
||
G[u].push_back(v);
|
||
G[v].push_back(u); // 无向图
|
||
|
||
// 带权邻接表
|
||
vector<pair<int,int>> G[100005]; // {目标节点, 权值}
|
||
G[u].push_back({v, w});
|
||
</pre>
|
||
|
||
<!-- ==================== 第四章 ==================== -->
|
||
<div class="page-break"></div>
|
||
<h2>第四章 算法</h2>
|
||
|
||
<h3>4.1 算法概念与描述</h3>
|
||
<p><span class="score-changed">原始评分【1】→ AI重评【3】<span class="reason">(基础理论重要)</span></span> <span class="score-changed">原始评分【2】→ AI重评【3】<span class="reason">(表达能力提升)</span></span></p>
|
||
<p>算法是解决特定问题的一系列明确步骤。算法的五个基本特性：<strong>有穷性</strong>、<strong>确定性</strong>、<strong>可行性</strong>、<strong>输入</strong>、<strong>输出</strong>。评价算法的主要指标是<strong>时间复杂度</strong>和<strong>空间复杂度</strong>。</p>
|
||
<table>
|
||
<tr><th>时间复杂度</th><th>名称</th><th>n=10<sup>6</sup>时操作次数</th><th>可行性</th></tr>
|
||
<tr><td>O(1)</td><td>常数</td><td>1</td><td>极快</td></tr>
|
||
<tr><td>O(log n)</td><td>对数</td><td>20</td><td>极快</td></tr>
|
||
<tr><td>O(n)</td><td>线性</td><td>10<sup>6</sup></td><td>快</td></tr>
|
||
<tr><td>O(n log n)</td><td>线性对数</td><td>2×10<sup>7</sup></td><td>可行</td></tr>
|
||
<tr><td>O(n<sup>2</sup>)</td><td>平方</td><td>10<sup>12</sup></td><td>不可行</td></tr>
|
||
<tr><td>O(2<sup>n</sup>)</td><td>指数</td><td>极大</td><td>不可行</td></tr>
|
||
</table>
|
||
|
||
<h3>4.2 入门算法</h3>
|
||
|
||
<h4>4.2.1 枚举法</h4>
|
||
<p><span class="score-changed">原始评分【1】→ AI重评【3】<span class="reason">(基础解题方法)</span></span></p>
|
||
<p>枚举法（暴力法）是最基础的算法思想：遍历所有可能的解，逐一检验是否满足条件。</p>
|
||
<pre>
|
||
// 示例：找出1~n中所有质数
|
||
for (int i = 2; i <= n; i++) {
|
||
bool isPrime = true;
|
||
for (int j = 2; j * j <= i; j++) {
|
||
if (i % j == 0) { isPrime = false; break; }
|
||
}
|
||
if (isPrime) cout << i << " ";
|
||
}
|
||
</pre>
|
||
|
||
<h4>4.2.2 模拟法</h4>
|
||
<p><span class="score-changed">原始评分【1】→ AI重评【6】<span class="reason">(高频考点，实用性强)</span></span></p>
|
||
<p>模拟法是按照题目描述的过程，用代码逐步模拟实现。这是CSP-J中<strong>出现频率最高</strong>的算法类型，几乎每年T1和T2都会考察。</p>
|
||
<div class="warning"><strong>高频考点：</strong>根据CSP-J历年真题统计，模拟法在T1中出现率超过80%。关键是准确理解题意，注意边界条件和特殊情况。</div>
|
||
|
||
<h3>4.3 基础算法</h3>
|
||
|
||
<h4>4.3.1 贪心法</h4>
|
||
<p><span class="score-changed">原始评分【3】→ AI重评【6】<span class="reason">(高频且区分度高)</span></span></p>
|
||
<p>贪心算法在每一步都选择当前最优的方案，期望最终得到全局最优解。贪心算法不一定能得到最优解，但对于某些特定问题（如活动选择、哈夫曼编码）可以证明其正确性。</p>
|
||
<pre>
|
||
// 经典贪心：活动选择问题
|
||
// 给定n个活动的开始和结束时间，选择最多不冲突的活动
|
||
struct Activity {
|
||
int start, end;
|
||
};
|
||
bool cmp(Activity a, Activity b) {
|
||
return a.end < b.end; // 按结束时间排序
|
||
}
|
||
sort(act, act + n, cmp);
|
||
int count = 1, lastEnd = act[0].end;
|
||
for (int i = 1; i < n; i++) {
|
||
if (act[i].start >= lastEnd) {
|
||
count++;
|
||
lastEnd = act[i].end;
|
||
}
|
||
}
|
||
</pre>
|
||
|
||
<h4>4.3.2 递推法</h4>
|
||
<p><span class="score-changed">原始评分【3】→ AI重评【5】<span class="reason">(动态规划基础)</span></span></p>
|
||
<p>递推法通过已知的初始值和递推关系，逐步计算后续结果。递推是动态规划的基础。</p>
|
||
<pre>
|
||
// 斐波那契数列
|
||
int fib[105];
|
||
fib[1] = 1; fib[2] = 1;
|
||
for (int i = 3; i <= n; i++)
|
||
fib[i] = fib[i-1] + fib[i-2];
|
||
</pre>
|
||
|
||
<h4>4.3.3 递归法</h4>
|
||
<p><span class="score-changed">原始评分【4】→ AI重评【6】<span class="reason">(重要思维方式)</span></span></p>
|
||
<p>递归是函数调用自身的编程技巧。递归需要满足两个条件：<strong>基准情形</strong>（终止条件）和<strong>递归步骤</strong>（问题规模缩小）。</p>
|
||
<pre>
|
||
// 汉诺塔问题
|
||
void hanoi(int n, char from, char to, char aux) {
|
||
if (n == 1) {
|
||
cout << from << " -> " << to << endl;
|
||
return;
|
||
}
|
||
hanoi(n - 1, from, aux, to);
|
||
cout << from << " -> " << to << endl;
|
||
hanoi(n - 1, aux, to, from);
|
||
}
|
||
</pre>
|
||
|
||
<h4>4.3.4 二分法</h4>
|
||
<p><span class="score-changed">原始评分【4】→ AI重评【7】<span class="reason">(高频且效率关键)</span></span></p>
|
||
<p>二分法将搜索范围每次缩小一半，时间复杂度O(log n)。应用场景：有序数组查找、二分答案。</p>
|
||
<pre>
|
||
// 二分查找
|
||
int binarySearch(int a[], int n, int target) {
|
||
int left = 0, right = n - 1;
|
||
while (left <= right) {
|
||
int mid = left + (right - left) / 2;
|
||
if (a[mid] == target) return mid;
|
||
else if (a[mid] < target) left = mid + 1;
|
||
else right = mid - 1;
|
||
}
|
||
return -1; // 未找到
|
||
}
|
||
|
||
// 二分答案（竞赛高频模板）
|
||
int left = 0, right = 1e9;
|
||
while (left < right) {
|
||
int mid = (left + right) / 2;
|
||
if (check(mid)) right = mid; // check函数判断mid是否可行
|
||
else left = mid + 1;
|
||
}
|
||
// left就是答案
|
||
</pre>
|
||
<div class="warning"><strong>重要：</strong>二分法是CSP-J中区分度最高的算法之一。近年T2和T4中多次出现二分答案的考法。</div>
|
||
|
||
<h4>4.3.5 倍增法</h4>
|
||
<p><span class="score-changed">原始评分【4】→ AI重评【7】<span class="reason">(新增高效技巧)</span></span></p>
|
||
<p>倍增法是一种以2的幂次为步长进行跳跃的算法思想。常用于求解LCA（最近公共祖先）、稀疏表（ST表）等问题。核心思想：将任意整数分解为若干2的幂次之和。</p>
|
||
|
||
<h3>4.4 算法策略</h3>
|
||
|
||
<h4>4.4.1 前缀和</h4>
|
||
<p><span class="score-changed">原始评分【3】→ AI重评【5】<span class="reason">(常用优化技巧)</span></span></p>
|
||
<p>前缀和是一种预处理技巧，可以在O(1)时间内求出数组任意区间的和。</p>
|
||
<pre>
|
||
// 一维前缀和
|
||
int a[100005], prefix[100005];
|
||
prefix[0] = 0;
|
||
for (int i = 1; i <= n; i++)
|
||
prefix[i] = prefix[i-1] + a[i];
|
||
|
||
// 查询区间[l, r]的和
|
||
int sum = prefix[r] - prefix[l-1];
|
||
|
||
// 二维前缀和
|
||
int s[505][505];
|
||
for (int i = 1; i <= n; i++)
|
||
for (int j = 1; j <= m; j++)
|
||
s[i][j] = s[i-1][j] + s[i][j-1] - s[i-1][j-1] + a[i][j];
|
||
</pre>
|
||
|
||
<h4>4.4.2 差分</h4>
|
||
<p><span class="score-changed">原始评分【4】→ AI重评【6】<span class="reason">(新增且实用)</span></span></p>
|
||
<p>差分是前缀和的逆运算。差分数组可以在O(1)时间内对数组的一个区间进行加减操作。</p>
|
||
<pre>
|
||
// 差分数组
|
||
int diff[100005] = {0};
|
||
|
||
// 对区间[l, r]的所有元素加val
|
||
diff[l] += val;
|
||
diff[r + 1] -= val;
|
||
|
||
// 还原原数组
|
||
for (int i = 1; i <= n; i++)
|
||
diff[i] += diff[i-1]; // diff[i]就是原数组a[i]的值
|
||
</pre>
|
||
|
||
<h3>4.5 数值处理算法</h3>
|
||
|
||
<h4>4.5.1 高精度运算</h4>
|
||
<p><span class="score-changed">原始评分【4】→ AI重评【5】<span class="reason">(应用有限但难度较高)</span></span></p>
|
||
<p>当数值超过<code>long long</code>的范围时，需要使用高精度运算（用数组模拟大数运算）。</p>
|
||
<pre>
|
||
// 高精度加法
|
||
string add(string a, string b) {
|
||
string result = "";
|
||
int carry = 0;
|
||
int i = a.size() - 1, j = b.size() - 1;
|
||
while (i >= 0 || j >= 0 || carry) {
|
||
int sum = carry;
|
||
if (i >= 0) sum += a[i--] - '0';
|
||
if (j >= 0) sum += b[j--] - '0';
|
||
result = char(sum % 10 + '0') + result;
|
||
carry = sum / 10;
|
||
}
|
||
return result;
|
||
}
|
||
</pre>
|
||
|
||
<h3>4.6 排序算法</h3>
|
||
<p><span class="score-changed">原始评分【3】→ AI重评【5】<span class="reason">(基础且频繁)</span></span></p>
|
||
|
||
<table>
|
||
<tr><th>算法</th><th>时间复杂度（平均）</th><th>时间复杂度（最坏）</th><th>空间复杂度</th><th>稳定性</th></tr>
|
||
<tr><td>冒泡排序</td><td>O(n<sup>2</sup>)</td><td>O(n<sup>2</sup>)</td><td>O(1)</td><td>稳定</td></tr>
|
||
<tr><td>选择排序</td><td>O(n<sup>2</sup>)</td><td>O(n<sup>2</sup>)</td><td>O(1)</td><td>不稳定</td></tr>
|
||
<tr><td>插入排序</td><td>O(n<sup>2</sup>)</td><td>O(n<sup>2</sup>)</td><td>O(1)</td><td>稳定</td></tr>
|
||
<tr><td>计数排序</td><td>O(n+k)</td><td>O(n+k)</td><td>O(k)</td><td>稳定</td></tr>
|
||
<tr><td>sort(STL)</td><td>O(n log n)</td><td>O(n log n)</td><td>O(log n)</td><td>不稳定</td></tr>
|
||
</table>
|
||
|
||
<pre>
|
||
// 冒泡排序
|
||
for (int i = 0; i < n - 1; i++)
|
||
for (int j = 0; j < n - 1 - i; j++)
|
||
if (a[j] > a[j+1]) swap(a[j], a[j+1]);
|
||
|
||
// 选择排序
|
||
for (int i = 0; i < n - 1; i++) {
|
||
int minIdx = i;
|
||
for (int j = i + 1; j < n; j++)
|
||
if (a[j] < a[minIdx]) minIdx = j;
|
||
swap(a[i], a[minIdx]);
|
||
}
|
||
|
||
// 插入排序
|
||
for (int i = 1; i < n; i++) {
|
||
int key = a[i], j = i - 1;
|
||
while (j >= 0 && a[j] > key) {
|
||
a[j+1] = a[j]; j--;
|
||
}
|
||
a[j+1] = key;
|
||
}
|
||
|
||
// 计数排序（适用于值域较小的情况）
|
||
int cnt[100005] = {0};
|
||
for (int i = 0; i < n; i++) cnt[a[i]]++;
|
||
int idx = 0;
|
||
for (int i = 0; i <= maxVal; i++)
|
||
while (cnt[i]--) a[idx++] = i;
|
||
</pre>
|
||
|
||
<h3>4.7 搜索算法</h3>
|
||
|
||
<h4>4.7.1 深度优先搜索（DFS）</h4>
|
||
<p><span class="score-changed">原始评分【5】→ AI重评【8】<span class="reason">(高频关键算法)</span></span></p>
|
||
<p>DFS沿着一条路径尽可能深入，直到无法继续时回溯。通常用<strong>递归</strong>或<strong>栈</strong>实现。</p>
|
||
<pre>
|
||
// DFS模板 - 全排列
|
||
int n, path[15];
|
||
bool used[15];
|
||
|
||
void dfs(int depth) {
|
||
if (depth == n) {
|
||
for (int i = 0; i < n; i++) cout << path[i] << " ";
|
||
cout << endl;
|
||
return;
|
||
}
|
||
for (int i = 1; i <= n; i++) {
|
||
if (!used[i]) {
|
||
used[i] = true;
|
||
path[depth] = i;
|
||
dfs(depth + 1);
|
||
used[i] = false; // 回溯
|
||
}
|
||
}
|
||
}
|
||
</pre>
|
||
|
||
<h4>4.7.2 广度优先搜索（BFS）</h4>
|
||
<p><span class="score-changed">原始评分【5】→ AI重评【8】<span class="reason">(高频关键算法)</span></span></p>
|
||
<p>BFS逐层扩展搜索，使用<strong>队列</strong>实现。BFS可以找到<strong>最短路径</strong>（边权相同时）。</p>
|
||
<pre>
|
||
// BFS模板 - 迷宫最短路
|
||
int dx[] = {0, 0, 1, -1};
|
||
int dy[] = {1, -1, 0, 0};
|
||
int dist[505][505];
|
||
bool vis[505][505];
|
||
|
||
void bfs(int sx, int sy) {
|
||
queue<pair<int,int>> q;
|
||
q.push({sx, sy});
|
||
vis[sx][sy] = true;
|
||
dist[sx][sy] = 0;
|
||
while (!q.empty()) {
|
||
auto [x, y] = q.front(); q.pop();
|
||
for (int d = 0; d < 4; d++) {
|
||
int nx = x + dx[d], ny = y + dy[d];
|
||
if (nx >= 0 && nx < n && ny >= 0 && ny < m
|
||
&& !vis[nx][ny] && grid[nx][ny] != '#') {
|
||
vis[nx][ny] = true;
|
||
dist[nx][ny] = dist[x][y] + 1;
|
||
q.push({nx, ny});
|
||
}
|
||
}
|
||
}
|
||
}
|
||
</pre>
|
||
|
||
<h3>4.8 图论算法</h3>
|
||
|
||
<h4>4.8.1 图的遍历</h4>
|
||
<p><span class="score-changed">原始评分【4】→ AI重评【7】<span class="reason">(图论核心算法)</span></span> <span class="score-changed">原始评分【4】→ AI重评【7】<span class="reason">(图论核心算法)</span></span></p>
|
||
<pre>
|
||
// 图的DFS遍历
|
||
bool vis[100005];
|
||
void dfs(int u) {
|
||
vis[u] = true;
|
||
for (int v : G[u]) {
|
||
if (!vis[v]) dfs(v);
|
||
}
|
||
}
|
||
|
||
// 图的BFS遍历
|
||
void bfs(int start) {
|
||
queue<int> q;
|
||
q.push(start);
|
||
vis[start] = true;
|
||
while (!q.empty()) {
|
||
int u = q.front(); q.pop();
|
||
for (int v : G[u]) {
|
||
if (!vis[v]) {
|
||
vis[v] = true;
|
||
q.push(v);
|
||
}
|
||
}
|
||
}
|
||
}
|
||
</pre>
|
||
|
||
<h4>4.8.2 泛洪算法（Flood Fill）</h4>
|
||
<p><span class="score-changed">原始评分【5】→ AI重评【7】<span class="reason">(常见应用，区分度高)</span></span></p>
|
||
<p>泛洪算法用于填充连通区域，常用于统计连通块数量、图像填色等问题。</p>
|
||
<pre>
|
||
// Flood Fill - 统计连通块数量
|
||
int n, m, grid[505][505];
|
||
bool vis[505][505];
|
||
int dx[] = {0, 0, 1, -1};
|
||
int dy[] = {1, -1, 0, 0};
|
||
|
||
void floodFill(int x, int y, int color) {
|
||
vis[x][y] = true;
|
||
for (int d = 0; d < 4; d++) {
|
||
int nx = x + dx[d], ny = y + dy[d];
|
||
if (nx >= 0 && nx < n && ny >= 0 && ny < m
|
||
&& !vis[nx][ny] && grid[nx][ny] == color) {
|
||
floodFill(nx, ny, color);
|
||
}
|
||
}
|
||
}
|
||
|
||
// 统计连通块数量
|
||
int count = 0;
|
||
for (int i = 0; i < n; i++)
|
||
for (int j = 0; j < m; j++)
|
||
if (!vis[i][j]) {
|
||
floodFill(i, j, grid[i][j]);
|
||
count++;
|
||
}
|
||
</pre>
|
||
|
||
<h3>4.9 动态规划</h3>
|
||
|
||
<h4>4.9.1 动态规划的基本思路</h4>
|
||
<p><span class="score-changed">原始评分【4】→ AI重评【9】<span class="reason">(拉开差距关键)</span></span></p>
|
||
<p>动态规划（DP）是解决<strong>最优化问题</strong>的核心算法思想。DP的核心要素：</p>
|
||
<table>
|
||
<tr><th>要素</th><th>说明</th></tr>
|
||
<tr><td><strong>最优子结构</strong></td><td>问题的最优解包含子问题的最优解</td></tr>
|
||
<tr><td><strong>重叠子问题</strong></td><td>不同的决策路径会产生相同的子问题</td></tr>
|
||
<tr><td><strong>状态定义</strong></td><td>用数组dp[i]表示到第i个阶段的最优解</td></tr>
|
||
<tr><td><strong>状态转移方程</strong></td><td>描述状态之间的递推关系</td></tr>
|
||
<tr><td><strong>边界条件</strong></td><td>初始状态的值</td></tr>
|
||
</table>
|
||
<div class="warning"><strong>核心考点：</strong>动态规划是CSP-J中<strong>拉开差距的关键算法</strong>。根据历年真题统计，T3和T4中DP出现频率最高。掌握DP是获得省一等奖的必要条件。</div>
|
||
|
||
<h4>4.9.2 简单一维动态规划</h4>
|
||
<p><span class="score-changed">原始评分【4】→ AI重评【9】<span class="reason">(基础DP，频繁考)</span></span></p>
|
||
<pre>
|
||
// 经典问题：最长递增子序列（LIS）
|
||
// dp[i] = 以a[i]结尾的最长递增子序列长度
|
||
int dp[100005];
|
||
for (int i = 0; i < n; i++) {
|
||
dp[i] = 1;
|
||
for (int j = 0; j < i; j++) {
|
||
if (a[j] < a[i])
|
||
dp[i] = max(dp[i], dp[j] + 1);
|
||
}
|
||
}
|
||
int ans = *max_element(dp, dp + n);
|
||
|
||
// 经典问题：爬楼梯
|
||
// dp[i] = 到达第i级台阶的方案数
|
||
dp[1] = 1; dp[2] = 2;
|
||
for (int i = 3; i <= n; i++)
|
||
dp[i] = dp[i-1] + dp[i-2];
|
||
</pre>
|
||
|
||
<h4>4.9.3 简单背包类型动态规划</h4>
|
||
<p><span class="score-changed">原始评分【5】→ AI重评【9】<span class="reason">(高频难点)</span></span></p>
|
||
<pre>
|
||
// 0-1背包问题
|
||
// n个物品，背包容量W，第i个物品重量w[i]，价值v[i]
|
||
// dp[j] = 容量为j时的最大价值
|
||
int dp[100005] = {0};
|
||
for (int i = 1; i <= n; i++)
|
||
for (int j = W; j >= w[i]; j--) // 逆序遍历！
|
||
dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
|
||
cout << dp[W];
|
||
|
||
// 完全背包问题（每种物品可以选无限次）
|
||
for (int i = 1; i <= n; i++)
|
||
for (int j = w[i]; j <= W; j++) // 正序遍历！
|
||
dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
|
||
</pre>
|
||
|
||
<h4>4.9.4 简单区间类型动态规划</h4>
|
||
<p><span class="score-changed">原始评分【5】→ AI重评【9】<span class="reason">(高频难点)</span></span></p>
|
||
<pre>
|
||
// 区间DP模板：石子合并
|
||
// dp[i][j] = 合并第i堆到第j堆石子的最小代价
|
||
int dp[505][505], prefix[505];
|
||
memset(dp, 0x3f, sizeof(dp));
|
||
for (int i = 1; i <= n; i++) dp[i][i] = 0;
|
||
|
||
for (int len = 2; len <= n; len++) { // 枚举区间长度
|
||
for (int i = 1; i + len - 1 <= n; i++) { // 枚举左端点
|
||
int j = i + len - 1; // 右端点
|
||
for (int k = i; k < j; k++) { // 枚举分割点
|
||
dp[i][j] = min(dp[i][j],
|
||
dp[i][k] + dp[k+1][j] + prefix[j] - prefix[i-1]);
|
||
}
|
||
}
|
||
}
|
||
</pre>
|
||
|
||
<!-- ==================== 第五章 ==================== -->
|
||
<div class="page-break"></div>
|
||
<h2>第五章 数学与其他</h2>
|
||
|
||
<h3>5.1 数及其运算</h3>
|
||
<p><span class="score-changed">原始评分【1】→ AI重评【2】<span class="reason">(基础数学知识)</span></span></p>
|
||
<p>了解自然数、整数、有理数、实数的概念及其四则运算。在计算机中，整数和浮点数的表示方式不同，需要注意精度问题。</p>
|
||
|
||
<h4>5.1.1 进制与进制转换</h4>
|
||
<p><span class="score-changed">原始评分【1】→ AI重评【3】<span class="reason">(竞赛常用基础)</span></span></p>
|
||
<pre>
|
||
// 十进制转其他进制
|
||
void toBase(int n, int base) {
|
||
if (n == 0) return;
|
||
toBase(n / base, base);
|
||
cout << n % base;
|
||
}
|
||
|
||
// 其他进制转十进制
|
||
int toDecimal(string s, int base) {
|
||
int result = 0;
|
||
for (char c : s) {
|
||
result = result * base + (c - '0');
|
||
}
|
||
return result;
|
||
}
|
||
</pre>
|
||
|
||
<h3>5.2 初等数学</h3>
|
||
<p><span class="score-changed">原始评分【1】→ AI重评【2】<span class="reason">(基础数学)</span></span> <span class="score-changed">原始评分【1】→ AI重评【2】<span class="reason">(基础数学)</span></span></p>
|
||
<p>掌握初中阶段的代数知识（一元一次方程、一元二次方程、不等式等）和几何知识（三角形、四边形、圆的面积和周长等）。CSP-J 2023年T3就考察了一元二次方程的求解。</p>
|
||
|
||
<h3>5.3 初等数论</h3>
|
||
|
||
<h4>5.3.1 整除、因数、倍数、质数、合数</h4>
|
||
<p><span class="score-changed">原始评分【3】→ AI重评【5】<span class="reason">(数学基础，频繁考)</span></span></p>
|
||
<pre>
|
||
// 判断质数
|
||
bool isPrime(int n) {
|
||
if (n < 2) return false;
|
||
for (int i = 2; i * i <= n; i++)
|
||
if (n % i == 0) return false;
|
||
return true;
|
||
}
|
||
|
||
// 分解质因数
|
||
void factorize(int n) {
|
||
for (int i = 2; i * i <= n; i++) {
|
||
while (n % i == 0) {
|
||
cout << i << " ";
|
||
n /= i;
|
||
}
|
||
}
|
||
if (n > 1) cout << n;
|
||
}
|
||
</pre>
|
||
|
||
<h4>5.3.2 取整</h4>
|
||
<p><span class="score-changed">原始评分【3】→ AI重评【4】<span class="reason">(数学技巧)</span></span></p>
|
||
<p>上取整：<code>ceil(a/b) = (a + b - 1) / b</code>（整数除法技巧）。下取整：C++中整数除法默认下取整。</p>
|
||
|
||
<h4>5.3.3 模运算与取余</h4>
|
||
<p><span class="score-changed">原始评分【3】→ AI重评【6】<span class="reason">(高频数学技巧)</span></span></p>
|
||
<p>模运算的基本性质：<code>(a + b) % m = ((a % m) + (b % m)) % m</code>，乘法同理。竞赛中常见"答案对10<sup>9</sup>+7取模"。</p>
|
||
<pre>
|
||
const int MOD = 1e9 + 7;
|
||
long long ans = 0;
|
||
for (int i = 0; i < n; i++) {
|
||
ans = (ans + a[i]) % MOD;
|
||
}
|
||
</pre>
|
||
|
||
<h4>5.3.4 整数唯一分解定理</h4>
|
||
<p><span class="score-changed">原始评分【3】→ AI重评【5】<span class="reason">(数学基础)</span></span></p>
|
||
<p>任何大于1的正整数都可以唯一地分解为若干质数的乘积：n = p<sub>1</sub><sup>a<sub>1</sub></sup> × p<sub>2</sub><sup>a<sub>2</sub></sup> × ... × p<sub>k</sub><sup>a<sub>k</sub></sup>。</p>
|
||
|
||
<h4>5.3.5 辗转相除法（欧几里得算法）</h4>
|
||
<p><span class="score-changed">原始评分【3】→ AI重评【6】<span class="reason">(高频数学算法)</span></span></p>
|
||
<pre>
|
||
// 最大公约数（GCD）
|
||
int gcd(int a, int b) {
|
||
return b == 0 ? a : gcd(b, a % b);
|
||
}
|
||
|
||
// 最小公倍数（LCM）
|
||
int lcm(int a, int b) {
|
||
return a / gcd(a, b) * b; // 先除后乘防溢出
|
||
}
|
||
|
||
// C++14起可直接使用 __gcd(a, b)
|
||
</pre>
|
||
|
||
<h4>5.3.6 素数筛法</h4>
|
||
<p><span class="score-changed">原始评分【4】→ AI重评【7】<span class="reason">(高频数学算法)</span></span></p>
|
||
<pre>
|
||
// 埃氏筛法 O(n log log n)
|
||
bool notPrime[10000005];
|
||
void sieve(int n) {
|
||
notPrime[0] = notPrime[1] = true;
|
||
for (int i = 2; i * i <= n; i++) {
|
||
if (!notPrime[i]) {
|
||
for (int j = i * i; j <= n; j += i)
|
||
notPrime[j] = true;
|
||
}
|
||
}
|
||
}
|
||
|
||
// 线性筛（欧拉筛）O(n)
|
||
int primes[1000005], cnt = 0;
|
||
bool notPrime2[10000005];
|
||
void linearSieve(int n) {
|
||
for (int i = 2; i <= n; i++) {
|
||
if (!notPrime2[i]) primes[cnt++] = i;
|
||
for (int j = 0; j < cnt && i * primes[j] <= n; j++) {
|
||
notPrime2[i * primes[j]] = true;
|
||
if (i % primes[j] == 0) break;
|
||
}
|
||
}
|
||
}
|
||
</pre>
|
||
|
||
<h3>5.4 离散与组合数学</h3>
|
||
|
||
<h4>5.4.1 集合与计数原理</h4>
|
||
<p><span class="score-changed">原始评分【2】→ AI重评【3】<span class="reason">(基础数学概念)</span></span> <span class="score-changed">原始评分【2】→ AI重评【3】<span class="reason">(组合数学基础)</span></span> <span class="score-changed">原始评分【2】→ AI重评【3】<span class="reason">(组合数学基础)</span></span></p>
|
||
<p><strong>加法原理</strong>：完成一件事有n类方法，第i类有a<sub>i</sub>种，总方法数为 Σa<sub>i</sub>。<strong>乘法原理</strong>：完成一件事需要n个步骤，第i步有a<sub>i</sub>种方法，总方法数为 Πa<sub>i</sub>。</p>
|
||
|
||
<h4>5.4.2 排列与组合</h4>
|
||
<p><span class="score-changed">原始评分【4】→ AI重评【5】<span class="reason">(组合数学重要)</span></span> <span class="score-changed">原始评分【4】→ AI重评【5】<span class="reason">(组合数学重要)</span></span></p>
|
||
<p><strong>排列</strong>：从n个元素中取r个排列，P(n,r) = n!/(n-r)!。<strong>组合</strong>：从n个元素中取r个组合，C(n,r) = n!/(r!(n-r)!)。</p>
|
||
<pre>
|
||
// 计算组合数 C(n, r)
|
||
long long C[1005][1005];
|
||
void initC(int maxn) {
|
||
for (int i = 0; i <= maxn; i++) {
|
||
C[i][0] = 1;
|
||
for (int j = 1; j <= i; j++)
|
||
C[i][j] = (C[i-1][j-1] + C[i-1][j]) % MOD;
|
||
}
|
||
}
|
||
</pre>
|
||
|
||
<h4>5.4.3 杨辉三角</h4>
|
||
<p><span class="score-same">难度评级【4】</span></p>
|
||
<p>杨辉三角的第n行第k个数就是组合数C(n,k)。杨辉三角的递推关系：C(n,k) = C(n-1,k-1) + C(n-1,k)。</p>
|
||
|
||
<h4>5.4.4 ASCII码</h4>
|
||
<p><span class="score-changed">原始评分【2】→ AI重评【3】<span class="reason">(字符串处理基础)</span></span></p>
|
||
<table>
|
||
<tr><th>字符</th><th>ASCII码</th><th>常用关系</th></tr>
|
||
<tr><td>'0'~'9'</td><td>48~57</td><td>数字字符转数字：<code>c - '0'</code></td></tr>
|
||
<tr><td>'A'~'Z'</td><td>65~90</td><td>大写转小写：<code>c + 32</code> 或 <code>c + 'a' - 'A'</code></td></tr>
|
||
<tr><td>'a'~'z'</td><td>97~122</td><td>小写转大写：<code>c - 32</code> 或 <code>c - 'a' + 'A'</code></td></tr>
|
||
</table>
|
||
|
||
<!-- ==================== 附录 ==================== -->
|
||
<div class="page-break"></div>
|
||
<h2>附录：评分变化汇总表</h2>
|
||
<p>以下表格列出了所有经过AI模型重新评估后评分发生变化的知识点（黄色高亮标记）。评分基于全网深度调研数据，综合考虑考试重要性、学习难度、区分度和实用性四个维度。</p>
|
||
|
||
<table>
|
||
<tr><th>编号</th><th>知识点</th><th>原始评分</th><th>AI重评分</th><th>变化</th><th>评分理由</th></tr>
|
||
<tr class="highlight-row"><td>1</td><td>计算机的基本构成</td><td>【1】</td><td><strong>【2】</strong></td><td>+1</td><td>基础重要，竞赛环境必备</td></tr>
|
||
<tr class="highlight-row"><td>2</td><td>操作系统基本概念及常见操作</td><td>【1】</td><td><strong>【2】</strong></td><td>+1</td><td>环境操作基础，实用性提升</td></tr>
|
||
<tr><td>3</td><td>计算机网络和Internet基本概念</td><td>【1】</td><td>【1】</td><td>-</td><td>竞赛中应用较少</td></tr>
|
||
<tr><td>4</td><td>计算机的历史和常见用途</td><td>【1】</td><td>【1】</td><td>-</td><td>理论性强，实用性低</td></tr>
|
||
<tr><td>5</td><td>NOI相关活动的历史与规则</td><td>【1】</td><td>【1】</td><td>-</td><td>非技术核心内容</td></tr>
|
||
<tr class="highlight-row"><td>6</td><td>位、字节与字</td><td>【1】</td><td><strong>【3】</strong></td><td>+2</td><td>位运算基础，竞赛常用</td></tr>
|
||
<tr class="highlight-row"><td>7</td><td>程序设计语言及编译运行基本概念</td><td>【1】</td><td><strong>【2】</strong></td><td>+1</td><td>理解编译流程重要</td></tr>
|
||
<tr><td>8</td><td>文件/目录的图形界面操作</td><td>【1】</td><td>【1】</td><td>-</td><td>竞赛中应用少</td></tr>
|
||
<tr class="highlight-row"><td>9</td><td>Windows/Linux集成开发环境使用</td><td>【1】</td><td><strong>【2】</strong></td><td>+1</td><td>开发环境熟悉度重要</td></tr>
|
||
<tr class="highlight-row"><td>10</td><td>编译命令g++的基本使用</td><td>【1】</td><td><strong>【3】</strong></td><td>+2</td><td>编译命令基础，实用性强</td></tr>
|
||
<tr class="highlight-row"><td>11</td><td>标识符、关键字、常量、变量、表达式</td><td>【1】</td><td><strong>【3】</strong></td><td>+2</td><td>编程基础，必备知识</td></tr>
|
||
<tr class="highlight-row"><td>12</td><td>常量与变量的命名、定义及作用</td><td>【1】</td><td><strong>【3】</strong></td><td>+2</td><td>基础语法，重要性提升</td></tr>
|
||
<tr class="highlight-row"><td>13</td><td>头文件与名字空间</td><td>【2】</td><td><strong>【3】</strong></td><td>+1</td><td>代码组织关键</td></tr>
|
||
<tr class="highlight-row"><td>14</td><td>编辑、编译、解释、调试概念</td><td>【2】</td><td><strong>【3】</strong></td><td>+1</td><td>调试能力重要</td></tr>
|
||
<tr class="highlight-row"><td>15</td><td>基本数据类型(int,long long,float,double,char,bool)</td><td>【1】</td><td><strong>【3】</strong></td><td>+2</td><td>类型理解基础</td></tr>
|
||
<tr class="highlight-row"><td>16</td><td>输入输出语句(cin/cout/scanf/printf)</td><td>【2】</td><td><strong>【3】</strong></td><td>+1</td><td>IO基础，频繁使用</td></tr>
|
||
<tr class="highlight-row"><td>17</td><td>条件语句(if/switch)</td><td>【2】</td><td><strong>【3】</strong></td><td>+1</td><td>控制流基础</td></tr>
|
||
<tr class="highlight-row"><td>18</td><td>循环语句(for/while/do while)</td><td>【2】</td><td><strong>【3】</strong></td><td>+1</td><td>循环结构核心</td></tr>
|
||
<tr class="highlight-row"><td>19</td><td>多层循环语句</td><td>【3】</td><td><strong>【4】</strong></td><td>+1</td><td>复杂度提升，常见考点</td></tr>
|
||
<tr class="highlight-row"><td>20</td><td>算术/关系/逻辑运算</td><td>【1】</td><td><strong>【3】</strong></td><td>+2</td><td>运算基础，频繁使用</td></tr>
|
||
<tr class="highlight-row"><td>21</td><td>位运算</td><td>【2】</td><td><strong>【5】</strong></td><td>+3</td><td>高频考点，难度较大</td></tr>
|
||
<tr class="highlight-row"><td>22</td><td>数学库常用函数</td><td>【3】</td><td><strong>【4】</strong></td><td>+1</td><td>数学思维增强</td></tr>
|
||
<tr class="highlight-row"><td>23</td><td>顺序/分支/循环结构</td><td>【1】</td><td><strong>【3】</strong></td><td>+2</td><td>基础结构，重要性提升</td></tr>
|
||
<tr class="highlight-row"><td>24</td><td>模块化程序设计与流程图</td><td>【2】</td><td><strong>【3】</strong></td><td>+1</td><td>代码组织与设计</td></tr>
|
||
<tr class="highlight-row"><td>25</td><td>数组与数组下标</td><td>【1】</td><td><strong>【4】</strong></td><td>+3</td><td>基础数据结构，应用广</td></tr>
|
||
<tr class="highlight-row"><td>26</td><td>二维数组与多维数组</td><td>【3】</td><td><strong>【4】</strong></td><td>+1</td><td>常见数据结构</td></tr>
|
||
<tr class="highlight-row"><td>27</td><td>字符数组与string类</td><td>【2】</td><td><strong>【4】</strong></td><td>+2</td><td>字符串处理基础</td></tr>
|
||
<tr class="highlight-row"><td>28</td><td>函数定义与调用、递归函数</td><td>【2】</td><td><strong>【5】</strong></td><td>+3</td><td>递归难点，重要考点</td></tr>
|
||
<tr class="highlight-row"><td>29</td><td>传值与传引用参数</td><td>【3】</td><td><strong>【4】</strong></td><td>+1</td><td>参数传递细节重要</td></tr>
|
||
<tr class="highlight-row"><td>30</td><td>结构体与联合体</td><td>【3】</td><td><strong>【4】</strong></td><td>+1</td><td>数据组织关键</td></tr>
|
||
<tr class="highlight-row"><td>31</td><td>指针与引用</td><td>【4】</td><td><strong>【5】</strong></td><td>+1</td><td>核心难点，区分度高</td></tr>
|
||
<tr class="highlight-row"><td>32</td><td>文件读写</td><td>【2】</td><td><strong>【3】</strong></td><td>+1</td><td>竞赛中偶尔应用</td></tr>
|
||
<tr class="highlight-row"><td>33</td><td>STL常用函数(min/max/swap/sort)</td><td>【3】</td><td><strong>【5】</strong></td><td>+2</td><td>高频实用，效率提升</td></tr>
|
||
<tr class="highlight-row"><td>34</td><td>STL容器(stack/queue/list/vector)</td><td>【4】</td><td><strong>【6】</strong></td><td>+2</td><td>竞赛必备，应用广泛</td></tr>
|
||
<tr class="highlight-row"><td>35</td><td>链表(单/双向/循环)</td><td>【3】</td><td><strong>【4】</strong></td><td>+1</td><td>数据结构基础</td></tr>
|
||
<tr class="highlight-row"><td>36</td><td>栈</td><td>【3】</td><td><strong>【5】</strong></td><td>+2</td><td>高频考点，应用广</td></tr>
|
||
<tr class="highlight-row"><td>37</td><td>队列</td><td>【3】</td><td><strong>【5】</strong></td><td>+2</td><td>高频考点，应用广</td></tr>
|
||
<tr class="highlight-row"><td>38</td><td>树的定义与基本概念</td><td>【3】</td><td><strong>【5】</strong></td><td>+2</td><td>基础数据结构</td></tr>
|
||
<tr class="highlight-row"><td>39</td><td>二叉树定义与基本性质</td><td>【3】</td><td><strong>【5】</strong></td><td>+2</td><td>基础树结构</td></tr>
|
||
<tr class="highlight-row"><td>40</td><td>树/二叉树的表示与存储</td><td>【4】</td><td><strong>【6】</strong></td><td>+2</td><td>存储实现关键</td></tr>
|
||
<tr class="highlight-row"><td>41</td><td>二叉树的遍历(前序/中序/后序)</td><td>【4】</td><td><strong>【6】</strong></td><td>+2</td><td>遍历是基础技能</td></tr>
|
||
<tr class="highlight-row"><td>42</td><td>完全二叉树定义、性质与数组表示</td><td>【4】</td><td><strong>【6】</strong></td><td>+2</td><td>重要树结构</td></tr>
|
||
<tr class="highlight-row"><td>43</td><td>哈夫曼树与哈夫曼编码</td><td>【4】</td><td><strong>【5】</strong></td><td>+1</td><td>经典算法，应用有限</td></tr>
|
||
<tr class="highlight-row"><td>44</td><td>二叉搜索树</td><td>【4】</td><td><strong>【5】</strong></td><td>+1</td><td>重要树结构</td></tr>
|
||
<tr class="highlight-row"><td>45</td><td>图的定义与相关概念</td><td>【3】</td><td><strong>【5】</strong></td><td>+2</td><td>图论基础</td></tr>
|
||
<tr class="highlight-row"><td>46</td><td>图的存储(邻接矩阵/邻接表)</td><td>【4】</td><td><strong>【6】</strong></td><td>+2</td><td>图论基础实现</td></tr>
|
||
<tr class="highlight-row"><td>47</td><td>算法概念</td><td>【1】</td><td><strong>【3】</strong></td><td>+2</td><td>基础理论重要</td></tr>
|
||
<tr class="highlight-row"><td>48</td><td>算法描述(自然语言/流程图/伪代码)</td><td>【2】</td><td><strong>【3】</strong></td><td>+1</td><td>表达能力提升</td></tr>
|
||
<tr class="highlight-row"><td>49</td><td>枚举法</td><td>【1】</td><td><strong>【3】</strong></td><td>+2</td><td>基础解题方法</td></tr>
|
||
<tr class="highlight-row"><td>50</td><td>模拟法</td><td>【1】</td><td><strong>【6】</strong></td><td>+5</td><td>高频考点，实用性强</td></tr>
|
||
<tr class="highlight-row"><td>51</td><td>贪心法</td><td>【3】</td><td><strong>【6】</strong></td><td>+3</td><td>高频且区分度高</td></tr>
|
||
<tr class="highlight-row"><td>52</td><td>递推法</td><td>【3】</td><td><strong>【5】</strong></td><td>+2</td><td>动态规划基础</td></tr>
|
||
<tr class="highlight-row"><td>53</td><td>递归法</td><td>【4】</td><td><strong>【6】</strong></td><td>+2</td><td>重要思维方式</td></tr>
|
||
<tr class="highlight-row"><td>54</td><td>二分法</td><td>【4】</td><td><strong>【7】</strong></td><td>+3</td><td>高频且效率关键</td></tr>
|
||
<tr class="highlight-row"><td>55</td><td>倍增法</td><td>【4】</td><td><strong>【7】</strong></td><td>+3</td><td>新增高效技巧</td></tr>
|
||
<tr class="highlight-row"><td>56</td><td>前缀和</td><td>【3】</td><td><strong>【5】</strong></td><td>+2</td><td>常用优化技巧</td></tr>
|
||
<tr class="highlight-row"><td>57</td><td>差分</td><td>【4】</td><td><strong>【6】</strong></td><td>+2</td><td>新增且实用</td></tr>
|
||
<tr class="highlight-row"><td>58</td><td>高精度运算</td><td>【4】</td><td><strong>【5】</strong></td><td>+1</td><td>应用有限但难度较高</td></tr>
|
||
<tr class="highlight-row"><td>59</td><td>排序基本概念</td><td>【3】</td><td><strong>【5】</strong></td><td>+2</td><td>基础且频繁</td></tr>
|
||
<tr><td>60</td><td>冒泡排序</td><td>【3】</td><td>【3】</td><td>-</td><td>基础教学用</td></tr>
|
||
<tr><td>61</td><td>选择排序</td><td>【3】</td><td>【3】</td><td>-</td><td>基础教学用</td></tr>
|
||
<tr><td>62</td><td>插入排序</td><td>【3】</td><td>【3】</td><td>-</td><td>基础教学用</td></tr>
|
||
<tr class="highlight-row"><td>63</td><td>计数排序</td><td>【3】</td><td><strong>【4】</strong></td><td>+1</td><td>常用优化排序</td></tr>
|
||
<tr class="highlight-row"><td>64</td><td>深度优先搜索(DFS)</td><td>【5】</td><td><strong>【8】</strong></td><td>+3</td><td>高频关键算法</td></tr>
|
||
<tr class="highlight-row"><td>65</td><td>广度优先搜索(BFS)</td><td>【5】</td><td><strong>【8】</strong></td><td>+3</td><td>高频关键算法</td></tr>
|
||
<tr class="highlight-row"><td>66</td><td>图的深度优先遍历</td><td>【4】</td><td><strong>【7】</strong></td><td>+3</td><td>图论核心算法</td></tr>
|
||
<tr class="highlight-row"><td>67</td><td>图的广度优先遍历</td><td>【4】</td><td><strong>【7】</strong></td><td>+3</td><td>图论核心算法</td></tr>
|
||
<tr class="highlight-row"><td>68</td><td>泛洪算法(Flood Fill)</td><td>【5】</td><td><strong>【7】</strong></td><td>+2</td><td>常见应用，区分度高</td></tr>
|
||
<tr class="highlight-row"><td>69</td><td>动态规划基本思路</td><td>【4】</td><td><strong>【9】</strong></td><td>+5</td><td>拉开差距关键</td></tr>
|
||
<tr class="highlight-row"><td>70</td><td>简单一维动态规划</td><td>【4】</td><td><strong>【9】</strong></td><td>+5</td><td>基础DP，频繁考</td></tr>
|
||
<tr class="highlight-row"><td>71</td><td>简单背包类型动态规划</td><td>【5】</td><td><strong>【9】</strong></td><td>+4</td><td>高频难点</td></tr>
|
||
<tr class="highlight-row"><td>72</td><td>简单区间类型动态规划</td><td>【5】</td><td><strong>【9】</strong></td><td>+4</td><td>高频难点</td></tr>
|
||
<tr class="highlight-row"><td>73</td><td>自然数/整数/有理数/实数及运算</td><td>【1】</td><td><strong>【2】</strong></td><td>+1</td><td>基础数学知识</td></tr>
|
||
<tr class="highlight-row"><td>74</td><td>进制与进制转换</td><td>【1】</td><td><strong>【3】</strong></td><td>+2</td><td>竞赛常用基础</td></tr>
|
||
<tr class="highlight-row"><td>75</td><td>代数(初中部分)</td><td>【1】</td><td><strong>【2】</strong></td><td>+1</td><td>基础数学</td></tr>
|
||
<tr class="highlight-row"><td>76</td><td>几何(初中部分)</td><td>【1】</td><td><strong>【2】</strong></td><td>+1</td><td>基础数学</td></tr>
|
||
<tr class="highlight-row"><td>77</td><td>整除/因数/倍数/质数/合数</td><td>【3】</td><td><strong>【5】</strong></td><td>+2</td><td>数学基础，频繁考</td></tr>
|
||
<tr class="highlight-row"><td>78</td><td>取整</td><td>【3】</td><td><strong>【4】</strong></td><td>+1</td><td>数学技巧</td></tr>
|
||
<tr class="highlight-row"><td>79</td><td>模运算与取余</td><td>【3】</td><td><strong>【6】</strong></td><td>+3</td><td>高频数学技巧</td></tr>
|
||
<tr class="highlight-row"><td>80</td><td>整数唯一分解定理</td><td>【3】</td><td><strong>【5】</strong></td><td>+2</td><td>数学基础</td></tr>
|
||
<tr class="highlight-row"><td>81</td><td>辗转相除法(欧几里得算法)</td><td>【3】</td><td><strong>【6】</strong></td><td>+3</td><td>高频数学算法</td></tr>
|
||
<tr class="highlight-row"><td>82</td><td>素数筛法(埃氏筛/线性筛)</td><td>【4】</td><td><strong>【7】</strong></td><td>+3</td><td>高频数学算法</td></tr>
|
||
<tr class="highlight-row"><td>83</td><td>集合</td><td>【2】</td><td><strong>【3】</strong></td><td>+1</td><td>基础数学概念</td></tr>
|
||
<tr class="highlight-row"><td>84</td><td>加法原理</td><td>【2】</td><td><strong>【3】</strong></td><td>+1</td><td>组合数学基础</td></tr>
|
||
<tr class="highlight-row"><td>85</td><td>乘法原理</td><td>【2】</td><td><strong>【3】</strong></td><td>+1</td><td>组合数学基础</td></tr>
|
||
<tr class="highlight-row"><td>86</td><td>排列</td><td>【4】</td><td><strong>【5】</strong></td><td>+1</td><td>组合数学重要</td></tr>
|
||
<tr class="highlight-row"><td>87</td><td>组合</td><td>【4】</td><td><strong>【5】</strong></td><td>+1</td><td>组合数学重要</td></tr>
|
||
<tr><td>88</td><td>杨辉三角</td><td>【4】</td><td>【4】</td><td>-</td><td>基础数学工具</td></tr>
|
||
<tr class="highlight-row"><td>89</td><td>ASCII码</td><td>【2】</td><td><strong>【3】</strong></td><td>+1</td><td>字符串处理基础</td></tr>
|
||
|
||
</table>
|
||
|
||
<div class="tip" style="margin-top: 30px;">
|
||
<strong>数据来源与参考：</strong><br>
|
||
[1] NOI 大纲（2025年修订版）- <a href="https://www.noi.cn/xw/2025-04-18/841584.shtml">https://www.noi.cn/xw/2025-04-18/841584.shtml</a><br>
|
||
[2] CSP-J 历年复赛真题考察内容 (2010～2023) 考点分析<br>
|
||
[3] CSP-J/S2025 入门级题目知识构成分析报告<br>
|
||
[4] AI模型评分（gpt-4.1-mini），评分维度：考试重要性、学习难度、区分度、实用性
|
||
</div>
|
||
|
||
<p style="text-align: center; margin-top: 40px; color: #999; font-size: 9pt;">
|
||
— 文档生成日期：2026年3月14日 | 基于 NOI 大纲（2025年修订版）—
|
||
</p>
|
||
|
||
</body>
|
||
</html>
|