知识不是堆得越多越好，重要的是按照正确的顺序真正掌握。
了解 ICPC、CCPC、天梯赛、蓝桥杯与百度之星的特点，找到适合自己的参赛方向。
认识常见竞赛 →从代码框架、输入输出到数组、结构体和函数，每个知识点都有逐行解释、运行结果与练习。
进入 14 章教程 →基础算法、搜索、数据结构、动态规划与图论，按难度逐步建立完整知识网络。
查看算法目录 →按照 C++ 教程的学习顺序完成洛谷入门题，把刚学会的语法真正变成解题能力。
打开语法题单 →教程帮助你理解知识，题目帮助你真正掌握知识。可以根据当前阶段选择一个主平台持续练习。
Online Judge，在线评测系统。提交代码后，系统会自动编译、运行并判断答案是否正确。
中文题库与社区内容丰富，题目难度标记直观，适合从基础语法、算法模板逐步练习。
包含在线编程、竞赛题目与企业笔试训练，国内高校算法赛事和练习活动较为丰富。
国际竞技编程平台，拥有频繁的线上比赛、分级竞赛和 Rating 系统，题目强调思维与实现速度。
日本竞技编程平台，题目风格严谨、难度梯度稳定，Beginner Contest 很适合进行定期训练。
初学阶段可以先在洛谷或牛客完成基础题；熟悉常用算法后，再定期参加 Codeforces Div. 3/4 或 AtCoder Beginner Contest。不要同时追逐太多平台，持续练习比平台数量更重要。
掬水月在手，弄花香满衣。于良史《春山夜月》
写给第一次接触编程的你。我们会从一份完整的代码框架开始，把每个符号、每行代码和运行结果讲清楚。
从输入、输出和完整代码框架开始，不要求提前掌握任何编程知识。
每学完一个例子，都自己输入、运行并修改数据，观察程序结果。
学完对应语法后进入刷题训练，用协会 OJ 和练习题巩固知识。
第一次学习建议按左侧编号依次完成，已经有基础也可以直接选择章节。
编程环境就是我们写代码、检查错误、把代码翻译成程序并运行它的一套工具。Windows 初学者可以在下面两种方案中任选一种。
编辑器、编译器和调试工具可以一起安装，配置步骤少，适合想尽快写出第一段程序的同学。
MinGW64 的 Windows 安装版。hello.cpp。VS Code 本身是代码编辑器，不自带 C++ 编译器，需要额外安装编译工具。
C/C++ 扩展。g++ --version。hello.cpp。g++.exe。如果你现在只想学习语法，选小熊猫 C++ 最省心；如果你已经熟悉文件路径、终端和扩展，选 VS Code。两者写出的 C++ 代码没有区别。
新建 hello.cpp，复制下面的代码并运行。看到黑色运行窗口中出现 Hello, World! 就说明环境可用。
#include <iostream>
using namespace std;
int main() {
cout << "Hello, World!";
return 0;
}Hello, World!
先检查文件名是否以 .cpp 结尾、代码中的标点是否为英文符号、每条语句末尾是否有分号。VS Code 用户还要确认安装的是 C++ 编译器，而不只是 C/C++ 扩展。
一份竞赛程序就像一张固定格式的答题纸。刚开始不必背下来，先理解每一部分负责什么。
1#include <bits/stdc++.h>
2using namespace std;
3
4int main() {
5 // 解题代码写在这里
6 return 0;
7}#include 引入工具bits/stdc++.h 会一次性引入算法竞赛常用的标准库，让我们能够使用输入输出、数组容器和排序等工具。
using namespace std;让我们可以直接写 cout，不用每次都写完整的 std::cout。
int main() 是程序入口程序运行时会先找到 main 函数，再从左花括号开始逐行执行。
return 0; 正常结束告诉操作系统程序顺利执行完毕。在竞赛代码中通常保留这一行。
() 圆括号通常放条件或参数；{} 花括号包住一段代码；<> 尖括号在这里包住头文件名。注释是写给人看的说明，编译器会忽略它。单行注释从 // 开始；多行注释放在 /* 和 */ 之间。好的注释说明思路、边界或特殊处理，不必逐字翻译代码。
int answer = 0; // 保存目前找到的最大值
/* 枚举所有候选答案，
只保留满足条件的最大值 */
for (int x = 1; x <= n; x++) {
if (valid(x)) answer = max(answer, x);
}不要在一个 /* ... */ 中再放另一组多行注释。临时屏蔽代码时优先使用编辑器的单行注释快捷键，调试完成后及时清理。
代码必须使用英文输入法下的 ;、()、{} 和双引号。中文的 ；、（ ） 无法通过编译。
cout 用来把文字或计算结果输出到屏幕。符号 << 可以理解为“把右边的内容送到屏幕”。
cout << "Hello World" << '\n';Hello World
双引号中的内容叫做字符串，会原样输出。'\n' 表示换到下一行，它虽然由两个可见字符组成，但在 C++ 中代表一个换行符。
cout << "答案是：" << 3 + 5 << '\n';
cout << "A" << " " << "B";答案是：8 A B
"A"字符串，用双引号，可以包含多个字符。'A'单个字符，用单引号，只能表示一个字符。endl也能换行，但竞赛大量输出时通常使用更快的 '\n'。请输出两行文字：第一行是你的名字，第二行是 I love C++!。注意两行之间需要换行。
算法题的数据会通过标准输入交给程序。cin 负责读取数据，>> 可以理解为“把输入送进右边的变量”。
int a, b; // 准备两个整数变量
cin >> a >> b; // 依次读入 a 和 b
cout << a + b << '\n';12 8
20
空格和换行都可以分隔输入数据。因此输入写成第一行 12、第二行 8，程序仍能正确读取。
不能直接写 cin >> a; 而没有提前告诉 C++ 变量 a 的类型。这里的 int a; 就是在声明一个整数变量。
输入长和宽两个整数，输出它们的乘积。例如输入 4 6，应该输出 24。
变量可以想象成带名字的盒子：盒子中保存数据，类型决定这个盒子能装什么、能装多大。
int age = 15; // 整数
long long score = 10000000000LL; // 大整数
double pi = 3.14159; // 小数
char grade = 'A'; // 单个字符
bool passed = true; // 真或假
string name = "Alice"; // 字符串int普通整数绝对值不超过约 21 亿long long很大的整数乘法、总和或答案可能很大时优先考虑double带小数的数据平均数、几何计算等char / string单字符 / 一段文字字符题、字符串题题目要求“保留若干位小数”时，可以使用 fixed 和 setprecision 控制输出格式。fixed 表示按普通小数形式输出，setprecision(2) 表示小数点后固定保留 2 位。
#include <iomanip>
double value = 10.0 / 3.0;
cout << fixed << setprecision(2) << value;3.33
配合 fixed 时，setprecision(3) 会固定保留 3 位小数，例如 2.5 会输出为 2.500。如果省略 fixed，它控制的是有效数字位数，含义不同。
如果 a 和 b 都是整数，a / b 会先完成整数除法。需要小数结果时，应写成 1.0 * a / b，再使用 fixed 和 setprecision 控制显示位数。
int x = 5;
x = 8; // 把盒子里的 5 换成 8
x = x + 2; // 读取原来的 8，加 2，再存回 x
cout << x;10
sizeof 可以查看一种类型或一个变量占用多少字节（Byte）。它的结果是整数，写类型时通常要加括号，写变量时括号可以省略。
int x = 10;
double price = 3.5;
cout << sizeof(int) << ' ';
cout << sizeof x << ' ';
cout << sizeof(price);4 4 8
多数竞赛环境中 int 占 4 字节、long long 和 double 占 8 字节、char 占 1 字节。真正需要确认时，以当前程序的 sizeof 结果为准。
score / maxScore名字表达含义变量名由字母、数字和下划线组成，不能以数字开头。竞赛代码可以简洁，但仍要让自己看得懂。Score != score区分大小写C++ 严格区分大小写；sum、Sum 和 SUM 是三个不同的名字。int / for / return关键字不能作为名字语言已经使用的关键字不能再拿来命名变量、函数或结构体。total_score保持一种风格camelCase 与 snake_case 都可以，重要的是在同一份代码里保持一致。例如 __value、_Count 通常保留给编译器和标准库。自己写代码时使用 value、count 等普通名称最安全。
如果一个值初始化后不应该再被修改，就把它声明为常量。这样既能表达意图，也能让编译器帮你阻止误改。编译期就能确定的常量优先使用 constexpr。
constexpr int MAX_N = 100000; // 编译期常量
int input;
cin >> input;
const int n = input; // 运行时读到，但之后不修改
int a[MAX_N + 5];
// n = 20; // 错误：不能修改 const 变量现代 C++ 中通常使用 const 或 constexpr，而不是 #define MAX_N 100000。常量有明确类型，也更容易被编译器检查。
100000 * 100000 已超出 int 范围。写成 1LL * 100000 * 100000，或把变量声明为 long long。
运算符让程序进行数学计算、比较大小并组合条件。它们是后面判断和循环的基础。
+ - * /四则运算整数除法会舍去小数部分：7 / 2 得到 3。%取余数7 % 2 得到 1，常用来判断奇偶。== !=相等 / 不相等比较结果是 true 或 false。> < >= <=大小比较注意“大于等于”写作 >=。&& || !并且 / 或者 / 取反用来组合多个判断条件。++ --增加 1 / 减少 1i++ 等价于 i = i + 1。int a = 7, b = 2;
cout << a + b << ' '; // 加法：9
cout << a - b << ' '; // 减法：5
cout << a * b << ' '; // 乘法：14
cout << a / b << ' '; // 整数除法：3
cout << a * 1.0 / b; // 小数除法：3.59 5 14 3 3.5
int x = 10;
x += 3; // x = x + 3，现在是 13
x *= 2; // x = x * 2，现在是 26
x--; // x = x - 1，现在是 25
cout << x;25
+=、-=、*=、/= 和 %= 都是在原值上计算后再存回变量。单独使用时，++x 与 x++ 都会让 x 加 1；初学阶段不要把它们塞进复杂表达式。
int n;
cin >> n;
cout << (n % 2 == 0);如果输入 8，表达式 8 % 2 == 0 成立，输出 1；输入 7 时条件不成立，输出 0。
int age;
cin >> age;
bool isTeen = age >= 13 && age <= 18;
bool isFree = age < 6 || age >= 65;
cout << isTeen << ' ' << isFree << ' ';
cout << !isFree;15
1 0 1
&& 要求两边都成立，|| 只要一边成立，! 会把真假反过来。C++ 默认用 1 表示 true、0 表示 false。
条件 ? 条件成立时的值 : 条件不成立时的值 会产生一个结果，适合写简单的二选一。逻辑稍复杂时仍应使用更清晰的 if。
int a = 7, b = 12;
int larger = (a > b) ? a : b;
cout << larger;12
位运算会把整数看成一串二进制位。入门阶段先认识含义即可；学习状态压缩、集合表示或快速幂时会再次用到。
a & b按位与某一位只有在 a、b 对应位置都为 1 时才得到 1，常用于检查某个二进制位。a | b按位或对应位置只要有一个 1 就得到 1，常用于把某个状态位设为 1。a ^ b按位异或对应位置不同得到 1、相同得到 0；同一个数异或两次会抵消。1 << k左移把二进制的 1 向左移动 k 位；在不溢出的非负整数范围内等于 2 的 k 次方。int mask = 10; // 二进制 1010
int k = 1;
bool hasBit = (mask & (1 << k)) != 0;
mask = mask | (1 << 2); // 把第 2 位设为 1
cout << hasBit << ' ' << mask;&、| 逐位处理整数；&&、|| 判断整个条件的真假。移位只应在位数合法且不会溢出的情况下使用，不要把它机械理解成任何整数都能安全乘除 2。
* / % 通常先于 + - 计算，例如 2 + 3 * 4 得到 14。培训和比赛中都建议用括号主动表达意图：(2 + 3) * 4 得到 20。
= 和 == 完全不同x = 5 是把 5 存入 x；x == 5 才是在询问“x 是否等于 5”。这是条件判断中最常见的笔误。
当条件成立时执行一段代码，不成立时执行另一段代码，这就是分支结构。
int score;
cin >> score;
if (score >= 90) {
cout << "优秀";
} else if (score >= 60) {
cout << "及格";
} else {
cout << "继续努力";
}else if 会按从上到下的顺序检查。一旦某个条件成立并执行，对应的整组判断就结束了，因此更严格的条件通常写在前面。
if (age >= 13 && age <= 18) {
cout << "青少年";
}当变量只需要和几个固定值比较时，可以使用 switch。每个 case 表示一种情况，default 处理其他情况。
int day;
cin >> day;
switch (day) {
case 1:
cout << "Monday";
break;
case 2:
cout << "Tuesday";
break;
default:
cout << "Other day";
}Tuesday
执行某个 case 后，break 会离开整个 switch。如果漏写，程序会继续执行后面的 case，这种现象称为“贯穿”。
输入一个整数。大于 0 输出 positive，等于 0 输出 zero，小于 0 输出 negative。
当你知道一段代码需要执行多少次，for 循环通常最合适。它把“从哪里开始、何时继续、每次怎样变化”写在同一行。
for (int i = 1; i <= 5; i++)for (int i = 1; i <= 5; i++) {
cout << i << ' ';
}1 2 3 4 5
int n, sum = 0;
cin >> n;
for (int i = 1; i <= n; i++) {
sum += i; // 等价于 sum = sum + i
}
cout << sum;5
15
break 会立刻结束整个循环；continue 只跳过当前这一轮，随后进入下一轮。它们既可以用在 for 中，也可以用在 while 中。
for (int i = 1; i <= 10; i++) {
if (i == 8) break; // 到 8 时结束循环
if (i % 2 == 0) continue; // 偶数跳过输出
cout << i << ' ';
}1 3 5 7
i 为 2、4、6执行 continue，本轮后面的输出语句不再执行。
i 为 8执行 break，整个循环结束，9 和 10 也不会再处理。
外层循环每执行一轮，内层循环都会从头完整执行。常用于打印图形、枚举行列、处理二维数组。
for (int row = 1; row <= 3; row++) {
for (int col = 1; col <= 4; col++) {
cout << '*';
}
cout << '\n';
}**** **** ****
row 控制行外层共执行 3 轮，因此输出 3 行。
col 控制列每一行中内层执行 4 轮，因此每行输出 4 个星号。
循环体共执行 3 × 4 次若两层分别循环 n 次和 m 次，总次数就是 n × m。
在内层循环执行 break，外层循环仍会继续下一轮。如果需要同时结束两层，通常使用布尔标记，或把这段逻辑封装进函数后用 return。
i <= n 会包含 n，循环 n 次；i < n 不包含 n，只到 n - 1。写循环前先在纸上明确第一个值和最后一个值。
输入 n，输出 1 到 n 之间的所有偶数。你可以让 i 每次加 1 后判断，也可以思考怎样让 i 每次直接加 2。
当循环次数不确定，但“继续执行的条件”很清楚时，使用 while。每一轮开始前，程序都会先检查括号中的条件。
int n;
cin >> n;
while (n > 0) {
cout << n % 10 << ' ';
n /= 10;
}4 3 2 1
n % 10取得十进制个位数。
n /= 10删掉个位数，让 n 逐步变为 123、12、1、0。
n > 0当 n 变成 0 时条件不成立，循环结束。
下面的程序不断读入整数：遇到负数就跳过，遇到 0 就结束，其他数累加。循环次数由输入内容决定，所以很适合使用 while。
int sum = 0;
while (true) {
int x;
cin >> x;
if (x == 0) break; // 结束整个 while
if (x < 0) continue; // 跳过负数，继续读下一个
sum += x;
}
cout << sum;5 -2 7 0
12
while (true) 为什么能结束？它本身是无限循环，但读到 0 时会执行 break。这种“先循环、满足条件再退出”的写法在处理未知数量的输入时很常见。
int x;
do {
cin >> x;
} while (x < 0); // 别漏掉最后的分号while 是先判断再执行，可能一次也不执行；do while 是先执行再判断，因此循环体至少执行一次。
循环体必须让条件逐渐接近“不成立”。如果漏掉 n /= 10，n 永远不变，程序就会一直运行。遇到这种情况可以手动停止程序。
在手动维护循环变量的 while 中，如果先执行 continue，后面的 i++ 就会被跳过，程序可能永远停在同一个值。可以把更新语句放到判断之前，或改用 for。
for遍历 1 到 n、重复固定次数、遍历数组。while不断读入直到遇到 0、数字拆位、次数事先未知。如果要保存 100 个整数，没必要创建 100 个不同名字的变量。数组用一个名字管理一组类型相同的数据。
长度为 5 的数组，下标是 0、1、2、3、4。最后一个元素是 a[4]，访问 a[5] 已经越界。
int n;
cin >> n;
int a[1005];
for (int i = 0; i < n; i++) {
cin >> a[i];
}
int answer = a[0];
for (int i = 1; i < n; i++) {
answer = max(answer, a[i]);
}
cout << answer;5 8 3 6 1 9
9
int a[1005] 提前准备 1005 个位置。实际使用前 n 个位置，也就是 a[0] 到 a[n-1]。
int a[5] = {8, 3, 6, 1, 9};
int zero[100] = {}; // 所有元素初始化为 0
for (int i = 0; i < 5; i++) {
cout << a[i] << ' ';
}局部数组如果没有初始化，里面的值是不确定的，不能直接拿来累加或比较。计数数组常用 {} 将所有位置清零。
int a[3][4] 可以看成 3 行 4 列的表格。访问时先写行下标，再写列下标，例如 a[1][2] 表示第 2 行第 3 列。
int n, m;
cin >> n >> m;
int a[105][105];
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cin >> a[i][j];
}
}
int sum = 0;
for (int j = 0; j < m; j++) {
sum += a[0][j]; // 累加第 1 行
}
cout << sum;2 3 1 2 3 4 5 6
6
i = 0 ... n-1外层循环枚举每一行。
j = 0 ... m-1内层循环枚举这一行的每一列。
a[i][j]表示第 i + 1 行、第 j + 1 列的元素。
输入 n 行 m 列的整数矩阵，使用两层循环找出最大值，并输出它所在的行号和列号。
数组越界不一定立即报错，但会读写不属于它的内存，导致答案错误甚至程序崩溃。竞赛中应始终检查循环边界。
string 用来保存一串字符。它很像一个字符数组，同样可以通过从 0 开始的下标访问每个字符。
string s;
cin >> s;
cout << s.size() << '\n';
cout << s[0] << '\n';
for (char c : s) {
cout << c << ' ';
}4 c c o d e
cin >> s读取到空格就停止，适合单个单词。getline(cin, s)读取完整一行，能够包含空格。s.size()取得字符串长度，结果是字符数量。如果前面刚使用 cin >> 读过数字，输入缓冲区里通常还留着一个换行符。直接调用 getline 可能读到空行。可以使用 getline(cin >> ws, line)，先跳过开头残留的空白再读取。
int id;
string name;
cin >> id;
getline(cin >> ws, name);
cout << id << ' ' << name;7 Alice Wang
7 Alice Wang
ws 会跳过所有开头空白如果题目明确要求保留行首空格，就不要使用这种写法，应先用 cin.ignore() 精确丢弃上一行末尾的换行符，再调用 getline(cin, line)。
a + b拼接把两个字符串连接起来；也可以使用 s += t 把内容追加到 s 末尾。s.find(t)查找返回子串 t 第一次出现的位置；找不到时返回 string::npos。s.substr(pos, len)截取从下标 pos 开始取最多 len 个字符；省略 len 会一直取到末尾。s.insert(pos, t)插入在下标 pos 前插入字符串 t，原有内容自动向后移动。s.erase(pos, len)删除从下标 pos 开始删除 len 个字符；省略 len 会删除到末尾。s.replace(pos, len, t)替换把指定范围替换为字符串 t，替换前后的长度可以不同。string s = "algorithm";
cout << s.substr(0, 4) << '\n'; // algo
size_t pos = s.find("rith");
if (pos != string::npos) {
cout << pos << '\n';
}
s.insert(4, "-"); // algo-rithm
s.replace(5, 4, "code"); // algo-codem
s.erase(9, 1); // algo-code
cout << s;algo 4 algo-code
find 找不到时返回的 string::npos 不是合法下标。不要直接把它传给 erase、insert 或作为数组下标使用；应先判断 pos != string::npos。
<cctype> 提供字符分类和大小写转换工具。isalpha 判断字母，isdigit 判断数字，islower、isupper 判断大小写，tolower、toupper 完成转换。
string s = "A1go";
int digits = 0;
for (char &c : s) {
unsigned char value = static_cast<unsigned char>(c);
if (isdigit(value)) digits++;
c = static_cast<char>(toupper(value));
}
cout << s << ' ' << digits;<cctype> 的函数要求参数能安全表示为无符号字符。这个写法兼容性更稳；处理普通 ASCII 字母和数字时，最终效果与直接传入 char 相同。
string text = "2026";
int year = stoi(text);
long long score = 123456789LL;
string result = to_string(score);
cout << year + 1 << ' ' << result.size();2027 9
stoi(s)把字符串转换为 int；输入必须包含合法数字。stoll(s)把字符串转换为 long long，适合更大的整数。to_string(x)把数值转换成 string，便于拼接或逐位处理。bool ok = true;
for (int i = 0; i < s.size(); i++) {
if (s[i] != s[s.size() - 1 - i]) {
ok = false;
}
}第 i 个字符与倒数第 i 个字符比较。注意最后一个字符下标是 s.size() - 1。
读入一个初始字符串和若干操作，分别完成插入、截取与查找。查找不到时输出 -1；使用前面的 string::npos 判断，不要把它直接转换成普通下标。
结构体可以把多个不同类型、但彼此相关的数据组合成一个整体。竞赛中常用它表示学生、坐标、边、区间或题目记录。
struct Student {
string name;
int score;
int age;
}; // 结构体定义结束后需要分号Student我们创建的新类型名称，以后可以像 int 一样用它声明变量。
成员变量name、score 和 age 描述一名学生的不同信息。
末尾分号结构体右花括号后必须写分号，这是非常常见的编译错误。
Student a;
a.name = "Alice";
a.score = 95;
a.age = 16;
cout << a.name << ' ' << a.score;Alice 95
点号 . 表示访问结构体中的某个成员。例如 a.score 就是“学生 a 的分数”。
int n;
cin >> n;
Student students[105];
for (int i = 0; i < n; i++) {
cin >> students[i].name >> students[i].score;
}
int best = 0;
for (int i = 1; i < n; i++) {
if (students[i].score > students[best].score) {
best = i;
}
}
cout << students[best].name;3 Alice 95 Bob 88 Carol 97
Carol
成员值可以按照结构体中声明的顺序一次写出。结构体成员也可以是另一个结构体或容器，用来表示更完整的数据关系。
Student alice = {"Alice", 95, 16};
struct Team {
string name;
Student members[2];
};
Team team = {
"AlgoSpark",
{{"Alice", 95, 16}, {"Bob", 88, 17}}
};
cout << team.members[0].name;结构体可能包含字符串和容器，值传递会复制全部成员。只读时通常使用 const Student &：既避免复制，也保证函数不会修改原对象。
void printStudent(const Student &s) {
cout << s.name << ' ' << s.score;
}
Student alice = {"Alice", 95, 16};
printStudent(alice);Alice 95
定义结构体 Point，包含整数成员 x 和 y。输入两个点，输出它们横坐标之和与纵坐标之和。
函数把一段可以重复使用的逻辑封装起来。它可以接收参数，完成计算，再把结果返回给调用者。
int返回值类型maximum函数名称(int a, int b)参数列表int maximum(int a, int b) {
if (a > b) {
return a;
}
return b;
}
int main() {
int answer = maximum(7, 12);
cout << answer; // 输出 12
return 0;
}int f()函数会返回一个整数，需要写 return。bool f()函数返回 true 或 false，常用于判断。void f()函数不返回结果，只执行某些操作。调用函数时，括号中传入的是实参；函数定义中接收数据的 a、b 是形参。普通参数会复制一份数据，修改形参不会影响外面的变量。
void addOne(int x) {
x++;
}
int main() {
int n = 5;
addOne(n);
cout << n;
}5
在参数类型后加 & 表示引用。此时参数是外部变量的别名，对它的修改会保留下来。
void swapValue(int &a, int &b) {
int temp = a;
a = b;
b = temp;
}
int x = 3, y = 8;
swapValue(x, y);
cout << x << ' ' << y;8 3
int x值传递：复制一份，函数内修改不影响原变量。int &x引用传递：直接操作原变量，可以把修改带出函数。const string &s只读引用：避免复制较大的数据，同时禁止函数修改它。void printPositive(int x) {
if (x <= 0) {
return; // 立即结束函数，不返回具体数值
}
cout << x;
}void 函数不返回计算结果，但仍可以用单独的 return; 提前结束。一个有返回值的函数则要保证每条可能执行的路径都能返回正确类型的值。
C++ 需要先知道函数长什么样，才能调用它。可以把完整函数写在 main 前，也可以先写函数声明，再把实现放到 main 后。
int square(int x); // 函数声明：末尾有分号
int main() {
cout << square(6);
}
int square(int x) { // 函数实现
return x * x;
}在函数的花括号中声明的变量，离开函数后就不能再访问。不同函数可以拥有同名的局部变量，它们互不影响。
编写 bool isPrime(int n)，判断 n 是否为质数。在 main 中读入一个整数，根据函数返回值输出 Yes 或 No。
STL 是 C++ 标准库提供的一套现成工具。入门阶段先掌握 vector、sort，以及 max、min、swap 等常用函数。
vector<int> a;
a.push_back(8); // 在末尾加入 8
a.push_back(3); // 在末尾加入 3
a.push_back(6); // 在末尾加入 6
cout << a.size(); // 输出 3a.push_back(x)末尾添加把 x 放到 vector 最后，长度自动增加 1。a.pop_back()删除末尾删除最后一个元素；调用前必须确认 vector 不为空。a.front() / a.back()访问两端分别取得第一个和最后一个元素，同样要求容器非空。a.empty() / a.clear()判空 / 清空empty() 判断是否没有元素，clear() 删除全部元素。a.insert(a.begin() + p, x)指定位置插入在下标 p 前插入 x，p 必须位于 0 到 size 之间。a.erase(a.begin() + p)指定位置删除删除下标 p 的元素，p 必须是现有元素的合法下标。vector<int> a = {8, 3, 6};
a.push_back(9);
cout << a.front() << ' ' << a.back() << '\n';
a.pop_back();
cout << a.size();8 9 3
front、back 或 pop_back空容器不存在首尾元素，这些操作会产生未定义行为。数据可能为空时，应先写 if (!a.empty())。
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; i++) cin >> a[i];
sort(a.begin(), a.end());
for (int x : a) cout << x << ' ';5 8 3 6 1 9
1 3 6 8 9
vector<int> a(n)创建长度为 n 的整数 vector。
a.begin()指向第一个元素的位置。
a.end()指向最后一个元素后面的位置，sort 排序范围左闭右开。
vector<int> a = {8, 3, 6, 1};
sort(a.begin(), a.end(), greater<int>());
int b[] = {7, 2, 9, 4};
int n = 4;
sort(b, b + n);a: 8 6 3 1 b: 2 4 7 9
sort(a.begin() + l, a.begin() + r) 排序下标 [l, r)，包含 l、不包含 r。普通数组的 sort(b + l, b + r) 也是同一规则。
给 sort 提供比较函数，就能规定结构体的先后顺序。下面先按分数从高到低；分数相同时，再按姓名字典序从小到大。
struct Student {
string name;
int score;
};
bool better(const Student &a, const Student &b) {
if (a.score != b.score) return a.score > b.score;
return a.name < b.name;
}
vector<Student> students = {
{"Bob", 88}, {"Carol", 97}, {"Alice", 95}
};
sort(students.begin(), students.end(), better);
for (const Student &s : students) {
cout << s.name << ' ' << s.score << '\n';
}>= 或 <=当两个对象完全相等时，比较结果必须为 false，否则排序规则会自相矛盾。需要并列规则时，继续比较另一个成员，最后仍使用严格的 < 或 >。
max 取较大值，min 取较小值，swap 交换两个变量的值。它们能让常见操作写得更直接。
int a = 8, b = 3;
cout << max(a, b) << ' '; // 较大值
cout << min(a, b) << '\n'; // 较小值
swap(a, b);
cout << a << ' ' << b;8 3 3 8
使用标准头文件时，max、min 位于 <algorithm>，swap 可由 <utility> 提供。竞赛中常用的 #include <bits/stdc++.h> 已经包含这些头文件。
例如 max(3, 4LL) 的一个参数是 int、另一个是 long long，可能无法编译。可以写成 max(3LL, 4LL)，让两边类型保持一致。
reverse翻转顺序reverse(a.begin(), a.end()) 将整个 vector 前后颠倒。count统计出现次数count(a.begin(), a.end(), 3) 统计 3 出现了几次。find寻找元素找不到时返回 a.end()，使用前要先判断。max_element寻找最大元素返回元素所在位置，前面加 * 取得数值。min_element寻找最小元素用法与 max_element 相同。fill批量赋值fill(a.begin(), a.end(), 0) 把所有元素改成 0。vector<int> a = {8, 3, 6, 3, 9};
cout << count(a.begin(), a.end(), 3) << '\n';
cout << *max_element(a.begin(), a.end()) << '\n';
reverse(a.begin(), a.end());
for (int x : a) cout << x << ' ';8 3 6 3 9
2 9 9 3 6 3 8
如果 vector 为空，max_element 会返回 a.end()，此时不能在前面加 *。应先用 a.empty() 判断容器中是否有元素。
abs(x)取得绝对值，例如 abs(-7) 得到 7。sqrt(x)计算平方根，返回小数，例如 sqrt(16) 得到 4。pow(a, b)计算 a 的 b 次方；整数幂在竞赛中常用循环计算，避免浮点误差。读入 n 个整数，输出其中的最大值、最小值和某个指定数字出现的次数，然后将整个序列逆序输出。
下一步不要急着学习更多语法。先用这些知识完成求和、最大值、统计、模拟等基础题目，让输入—计算—输出的过程变得熟练。
教程负责把知识讲明白，题目负责让知识真正属于你。语法题按课程顺序练习，算法题按模拟、贪心、二分等专题逐步进阶。
洛谷题可手动标记完成，协会 OJ 题需判题通过。当前积分：0
登录后填写你在协会 OJ 使用的用户名，再用一次性绑定码完成身份验证。
熟悉完整代码框架、cout、cin 和最基本的计算。
练习整数、小数、字符以及常用算术运算。
根据不同输入选择不同执行路径，练习逻辑表达式。
让程序重复工作，完成统计、累加和过程模拟。
保存一批数据，并按下标访问、统计或修改它们。
拆分重复逻辑、组织复合数据，并使用标准库完成排序。
这些题目由协会 Hydro 自动判题，AC 后本站会自动点亮并计入积分。
按照题目给出的顺序维护状态，逐步还原整个过程。
每一步选择当前最优方案，并思考它为什么能得到全局最优。
从有序数组查找开始，再利用单调性不断缩小答案范围。
预处理累计信息，快速回答区间查询。
这一专题将在算法学习补充对应课程后开放。
这一专题将在算法学习补充对应课程后开放。
这一专题将在算法学习补充对应课程后开放。
按一维顺序定义状态，并从已知状态递推答案。
在容量限制下选择物品，理解状态与枚举顺序。
按区间长度递推，合并更小区间的结果。
使用邻接表表示点和边，为遍历与图算法做准备。
按距离分层遍历图，求无权图最短路。
根据边权特点选择合适算法，求点之间的最短距离。
以最小总代价连接全部顶点。
语法告诉我们代码怎样写，算法告诉我们问题应该怎样解决。这里会从读懂题目开始，逐步建立复杂度意识，再进入数据结构、动态规划、图论和数论。
读题、复杂度、模拟、贪心、二分、前缀和、差分以及概率与期望。
9 节已开放学习线性结构、栈与队列、树等组织和处理数据的方法。
路线已规划学习状态设计、转移方程、递推顺序与空间优化。
线性、背包、树形、换根、区间 DP 已开放从图的存储与遍历开始，进入最短路和生成树。
路线已规划掌握整除、质数、快速幂和同余等竞赛工具。
路线已规划先建立读题和复杂度意识，再学习具体算法会更稳。
这一阶段先建立正确的解题流程和复杂度意识，再学习模拟、贪心、二分、前缀和、差分以及概率与期望。
先把题目描述翻译成清晰的输入、计算和输出任务。
模拟就是让程序按照题目规定的顺序，把一个过程一步一步执行出来。它通常没有难记的公式，真正考查的是：能否把较长的文字规则翻译成明确的状态、操作顺序和边界判断。
识别信号题目反复出现“依次”“每次”“执行操作”“经过若干轮”“最终状态”等描述。核心问题当前需要保存什么？读到一次操作后，哪些状态会怎样变化？常见复杂度有 q 次操作，每次只做常数次计算，通常就是 O(q)。先用一句话概括任务，例如“机器人按指令移动，越界时原地不动”。
只保存会影响后续过程的数据，例如位置、方向、时间、余额、队列或棋盘。
明确一次操作的读取、计算、合法性检查和状态更新顺序。
用表格走完一个小样例，确认每一步的状态都和题意一致。
机器人位于 n 行 m 列的网格中，初始位置为 (x, y)。依次执行字符串中的指令：U、D、L、R 分别尝试向四个方向移动一格；如果新位置越界，本次移动无效，机器人留在原地。
当前行 x、当前列 y。
根据当前字符计算候选位置 (nextX, nextY)。
1 ≤ nextX ≤ n 且 1 ≤ nextY ≤ m 时才能移动。
全部指令执行完后的 x y。
网格大小为 3 × 4，起点为 (2, 2)，指令是 UURRDDDRU。第二次 U、第三次 D 和 R 都会越界，因此状态不变。
int n, m, x, y;
string commands;
cin >> n >> m >> x >> y >> commands;
for (char command : commands) {
int nextX = x, nextY = y;
if (command == 'U') nextX--;
else if (command == 'D') nextX++;
else if (command == 'L') nextY--;
else if (command == 'R') nextY++;
bool inside = nextX >= 1 && nextX <= n
&& nextY >= 1 && nextY <= m;
if (inside) {
x = nextX;
y = nextY;
}
}
cout << x << ' ' << y << '\n';3 4 2 2 UURRDDDRU
2 4
候选状态把“尝试移动”和“正式更新”分开。只有候选位置合法时才同时更新 x、y，越界时自然保留旧状态。规则较多时，这比边判断边修改更不容易出错。
统一单位时间统一换成秒，方向统一编号为 0—3，坐标统一采用同一种下标规则，减少分类讨论。拆出单步函数把“一次操作”写成独立函数；主流程只负责按顺序调用，更容易单独测试。维护不变量写下每步结束后始终成立的条件，例如位置一定在网格内、余额不能为负，并在调试时检查。只记录当前位置，却忘记方向、剩余次数等会影响下一步的数据。
题目要求“先扣费再判断”，代码却先判断后扣费，结果会完全不同。
混淆下标从 0 还是从 1 开始，或把 < 写成 <=。
题目要最终状态，却在每一步输出；或者需要记录过程，却只保存最终答案。
如果操作次数只有 10^5，逐步执行通常没有问题；如果题目要求执行 10^18 次，就要寻找周期、公式或批量处理方法。先看数据范围，再决定是否真的一步一步做。
输入一个合法日期，输出它的下一天。先列出 year、month、day 三个状态，再分别处理普通日期、月末、年末和闰年二月。不要一开始就写一长串 if。
贪心算法会按照某条规则不断做出当前选择，并且不回头修改。代码往往只有“排序 + 遍历”，但真正的难点是找到正确规则，并说明这个局部选择为什么一定能组成全局最优答案。
“最大、最小、最早、最短”都只是候选策略。只有能够通过证明，并且找不到反例的策略，才能称为正确的贪心算法。
到底是让数量最多、总代价最小、等待时间最短，还是让剩余空间最大？
思考当前选谁会给未来留下更有利的局面，而不是只看眼前数值大小。
构造 3—5 个元素的小数据，专门寻找能让策略失败的反例。
常用交换论证：把某个最优解的第一步换成贪心选择，答案不会变差。
每个活动占用一个时间区间 [left, right)，目标是在同一间教室中安排尽可能多的活动。两个活动满足“后一个活动的开始时间 ≥ 前一个活动的结束时间”时不冲突。
最早开始？可能很早开始、很晚结束，一次占满几乎所有时间。持续最短？短活动可能卡在中间，同时挡住前后两个活动。最早结束 ✓结束越早，为所有尚未选择的活动留下的时间越多。把活动按结束时间从小到大排序后，依次检查。以下区间最终会选择 [2,3)、[3,5)、[5,6)、[6,8)，答案为 4。
struct Activity {
long long left, right;
};
bool byEnd(const Activity &a, const Activity &b) {
if (a.right != b.right) return a.right < b.right;
return a.left < b.left;
}
int n;
cin >> n;
vector<Activity> activities(n);
for (Activity &activity : activities) {
cin >> activity.left >> activity.right;
}
sort(activities.begin(), activities.end(), byEnd);
int answer = 0;
long long lastEnd = LLONG_MIN;
for (Activity activity : activities) {
if (activity.left >= lastEnd) {
answer++;
lastEnd = activity.right;
}
}
cout << answer << '\n';按结束时间排序让最早结束的可选活动最先被考虑。
lastEnd记录最后一个已选活动的结束时间，用于判断冲突。
总复杂度排序是 O(n log n)，之后遍历一次是 O(n)。
设贪心选择的第一个活动是 A，任意一个最优方案选择的第一个活动是 B。因为 A 是所有活动中结束最早的，所以 A 的结束时间不会晚于 B。
替换之后，活动数量没有减少，而且方案仍然合法。因此一定存在一个“第一步选择 A”的最优方案。对剩余活动重复同样的推理，贪心选择就能得到全局最优答案。这就是一个完整的交换论证。
交换论证把任意最优解中的某一步换成贪心选择，证明可行性不变且答案不会更差。归纳 / 始终领先证明完成前 k 步后，贪心方案至少不劣于任何其他方案，再推进到第 k + 1 步。无法证明怎么办把选择后剩余的问题写出来；若未来还需要比较多种历史状态，通常应考虑 DP，而不是强行贪心。每次选择持续时间最短的活动。
[0,5)、[4,6)、[5,10)。
选择最短的 [4,6) 后，另外两个都不能选，答案为 1。
选择 [0,5) 和 [5,10)，答案为 2。
例如硬币面值为 1、3、4，凑出 6。每次拿最大硬币会得到 4 + 1 + 1，共 3 枚；最优方案是 3 + 3，只需 2 枚。局部最优没有自动保证全局最优。
给出若干活动的开始与结束时间。先不用写代码：分别尝试“最早开始、持续最短、最早结束”三种策略，并为前两种寻找反例；确认理由后，再独立实现按结束时间排序的做法。
一道算法题通常由题目描述、输入格式、输出格式、数据范围和样例组成。很多错误不是算法不会，而是没有把输入、输出或数据范围读准确。
说明需要解决什么问题。先把故事背景翻译成一句明确任务，例如“求区间和”或“寻找第一个满足条件的位置”。
说明程序会读到哪些数据、每个数据的含义以及排列顺序。变量声明和循环次数都来自这里。
说明最终要输出什么。空格、换行、保留小数位数以及输出顺序都可能影响评测结果。
决定数据类型和算法复杂度。看到 n ≤ 10^5，通常就不能使用 O(n²)。
给定两个整数 a 和 b，输出它们的和。
一行两个整数 a, b，以空格分隔。
输出一个整数，表示 a + b。
|a|, |b| ≤ 10⁹
n、m、q总共会处理多少数据和询问估算 n × q、n × m 是否可行|a[i]|、答案上界中间结果最大可能是多少选择 int、long long 或取模时间 / 内存限制允许的操作量与状态数量选择算法，并决定能否开二维数组有序、连续、可重复输入隐含的结构和合法情况决定能否二分、怎样去重、边界是否包含样例只展示少数情况，不能替代题面。写代码前主动补测：最小规模、最大值、全相等、负数或零、答案在首尾，以及“无解”是否可能。若题目保证某条件成立，就按保证实现；不要从样例自行猜规则。
#include <bits/stdc++.h>
using namespace std;
int main() {
long long a, b;
cin >> a >> b;
cout << a + b << '\n';
return 0;
}12 8
20
时间复杂度描述输入规模 n 增大时，程序操作次数增长得有多快。它不直接等于运行秒数，而是帮助我们在写代码之前判断算法是否可能超时。
int answer = a[0] + a[n - 1];for (int i = 0; i < n; i++)
sum += a[i];for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
check(i, j);顺序执行：相加O(n) + O(m) = O(n + m)，不要在有两个输入规模时强行写成 O(n)。嵌套执行：相乘外层 n 次、每次内层 m 次，总计 O(nm)。分支：看最坏情况竞赛题通常分析最坏时间；if 的两个分支取增长更快的一边。规模反复减半n → n/2 → n/4，直到 1，次数为 O(log n)。3n² + 5n + 20 写作 O(n²)：忽略常数和低阶项，是为了描述 n 增大后的主导趋势。但两种同为 O(n) 的程序，常数、缓存访问和实现方式仍会影响真实速度。
n ≤ 20指数级、状态枚举可以尝试枚举许多组合n ≤ 500O(n³)三层循环需要谨慎n ≤ 5,000O(n²)大约数千万次操作n ≤ 10⁵O(n log n) 或 O(n)排序、二分、线性遍历n ≤ 10⁷O(n)通常只能做少量遍历实际速度还受到常数、语言、内存访问和评测机影响。竞赛中常用“约一秒执行一亿次简单操作”进行粗略判断，但不能把它当成精确保证。
空间复杂度描述算法额外使用的存储空间怎样随输入规模增长。数组、容器、递归调用栈都会占用内存；超过题目的内存限制会得到 MLE。
无论 n 多大，只使用固定数量的变量。
int sum, maximum;保存 n 个同类型元素，空间随 n 线性增长。
vector<int> a(n);保存 n × n 个元素，n 增大时内存增长很快。
int grid[n][n];常见的 int 通常占 4 字节，long long 通常占 8 字节。估算数组内存时，可以使用：
int a[1'000'000] 大约占用 1,000,000 × 4 B ≈ 3.8 MB
如果算法直接在输入数组上修改数据，只使用少量额外变量，它的额外空间可能是 O(1)。分析时要区分“输入本身占用的空间”和“算法额外申请的空间”。
递归调用栈递归深度为 n 时，即使没有显式数组，也可能使用 O(n) 栈空间并触发栈溢出。容器与副本vector 除元素外还有少量管理开销；按值传递大容器还会产生一份完整副本。滚动数组若当前状态只依赖前一层，可以复用存储，把 O(nW) 空间降到 O(W)。巨大的局部数组通常位于调用栈，可能在远未达到题目内存限制前就崩溃。竞赛中常用 vector 动态分配，或在确有固定上界时使用全局数组；无论哪种方式都要先计算字节数。
二分查找利用数据的有序性或答案的单调性，每次检查中间位置并排除一半范围，把线性查找的 O(n) 降低为 O(log n)。
例如数组已经从小到大排序；或者某个条件在一段范围内为 false，之后全部为 true。
第 1 次：left = 0, right = 6, mid = 3
发现 a[3] = 13，目标找到。
bool exists(const vector<int>& a, int target) {
int left = 0;
int right = (int)a.size() - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (a[mid] == target) return true;
if (a[mid] < target) left = mid + 1;
else right = mid - 1;
}
return false;
}left <= right闭区间 [left, right] 还有元素时继续查找。
left + (right-left)/2与 (left+right)/2 含义相同，但能够避免两数相加溢出。
更新时越过 mid已经检查过 mid，所以使用 mid+1 或 mid-1，否则可能死循环。
对于形如 false false false true true 的单调序列，可以在左闭右开区间 [left, right) 中寻找第一个 true。循环始终维护：答案一定还在当前区间内。
int firstTrue(int left, int right) { // 搜索 [left, right)
while (left < right) {
int mid = left + (right - left) / 2;
if (check(mid)) right = mid; // mid 可能就是答案
else left = mid + 1; // mid 一定不是答案
}
return left;
}lower_bound返回第一个 大于等于 x 的位置；若不存在，返回 end()。upper_bound返回第一个 严格大于 x 的位置；两者之差就是 x 的出现次数。前提搜索区间必须按相同规则排好序；在 vector 上查询是 O(log n)。auto first = lower_bound(a.begin(), a.end(), target);
auto afterLast = upper_bound(a.begin(), a.end(), target);
int firstIndex = first == a.end() ? -1 : (int)(first - a.begin());
int count = (int)(afterLast - first);例如“最小化最大分组和”：若上限为 x 时可以分组，那么更大的上限也一定可以，形成 false → true 的边界。关键不在套模板，而在先证明 check(x) 单调，并保证搜索区间包含答案。
区间定义混乱。写代码前先决定使用闭区间 [left, right] 还是左闭右开区间 [left, right)，循环条件和更新方式必须始终与它保持一致。
如果需要反复询问数组某个区间的元素总和，每次从左到右重新累加会很慢。前缀和先进行一次 O(n) 预处理，之后每次区间查询只需 O(1)。
定义 prefix[i] 表示原数组前 i 个元素之和。为了让公式更整齐，令 prefix[0] = 0。
把第 i 个元素加入前 i-1 个元素的总和。
前 r 个元素之和，减去 l 之前的所有元素。
求数组第 2 到第 4 个元素之和：
prefix[4] - prefix[1] = 9 - 3 = 6int n, q;
cin >> n >> q;
vector<long long> prefix(n + 1, 0);
for (int i = 1; i <= n; i++) {
long long x;
cin >> x;
prefix[i] = prefix[i - 1] + x;
}
while (q--) {
int left, right;
cin >> left >> right;
cout << prefix[right] - prefix[left - 1] << '\n';
}令 prefix[i] 记录前 i 个元素中“满足条件的数量”，就能 O(1) 查询区间计数；把加法换成异或，还能得到区间异或值。能否相减消去前段，取决于所用运算是否具有对应的逆运算。
即使数组中的每个元素都能放进 int，许多元素相加后的前缀和也可能超过 int 范围。只要总和可能很大，就使用 long long。
二维前缀和用于快速计算矩阵中的矩形区域和。它是一维前缀和的自然推广：prefix[i][j] 表示从左上角 (1, 1) 到右下角 (i, j) 的整个矩形元素之和。
例如地图区域统计、二维棋盘计数、图片像素区域求和等。
上方矩形与左方矩形都包含左上角重叠区域，因此相加后必须把 prefix[i-1][j-1] 减去一次。
a[i][j]prefix[i-1][j]prefix[i][j-1]prefix[i-1][j-1]设矩形左上角为 (x1, y1)，右下角为 (x2, y2)，包含边界。先取右下角的大前缀矩形，再减去上方和左方多余区域，最后把被重复减去的左上区域加回来。
int n, m, q;
cin >> n >> m >> q;
vector<vector<long long>> prefix(
n + 1, vector<long long>(m + 1, 0)
);
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
long long value;
cin >> value;
prefix[i][j] = value
+ prefix[i - 1][j]
+ prefix[i][j - 1]
- prefix[i - 1][j - 1];
}
}
while (q--) {
int x1, y1, x2, y2;
cin >> x1 >> y1 >> x2 >> y2;
long long answer = prefix[x2][y2]
- prefix[x1 - 1][y2]
- prefix[x2][y1 - 1]
+ prefix[x1 - 1][y1 - 1];
cout << answer << '\n';
}建议让矩阵下标从 1 开始，并额外保留第 0 行和第 0 列为 0。这样查询贴着上边界或左边界的矩形时，不需要额外分类讨论。
如果要对数组的许多区间整体加上一个数，逐个修改区间中的每个元素会很慢。差分只修改区间的两个边界，每次操作是 O(1)，最后再用一次前缀和还原整个数组。
令 diff[i] = a[i] - a[i - 1]，并规定 a[0] = 0。差分记录的是“当前位置相对前一个位置变化了多少”。
最后一个 0 是额外预留的 diff[n + 1]，用于处理右端点恰好为 n 的区间修改。它不属于原数组。
记录相邻元素之间的变化量。
对 diff 求前缀和，就能重新得到 a。
表示从位置 l 起，后面的元素都多出 k。
让这次增加只影响到 r，不继续传到后面。
原数组为 3 1 4 1 5，将区间 [2, 4] 全部加 2：
int n, m;
cin >> n >> m;
vector<long long> diff(n + 2, 0);
long long previous = 0;
for (int i = 1; i <= n; i++) {
long long value;
cin >> value;
diff[i] = value - previous;
previous = value;
}
while (m--) {
int left, right;
long long value;
cin >> left >> right >> value;
diff[left] += value;
diff[right + 1] -= value;
}
for (int i = 1; i <= n; i++) {
diff[i] += diff[i - 1];
cout << diff[i] << ' ';
}5 2 3 1 4 1 5 2 4 2 1 3 -1
2 2 5 3 5
前缀和擅长“数组不变，多次查询区间和”。差分擅长“多次修改区间，最后得到整个数组”。两者关系差分的前缀和是原数组，原数组的相邻差是差分。如果数组使用 1 到 n 的下标，差分数组至少开到 n + 1。代码中常写 vector<long long> diff(n + 2)，避免访问 diff[right + 1] 时越界。
如果每次修改后都要立刻查询当前区间和，不能每次重新还原数组；这类在线问题通常需要树状数组或线段树。
二维差分可以把矩形 (x1, y1) 到 (x2, y2) 内的所有元素同时加上 value。一次修改只需要改变四个角，最后对差分矩阵求二维前缀和即可还原。
左上角开始产生影响，下方和右方分别取消影响，右下角因为被减了两次，需要再加回来一次。
void addRectangle(int x1, int y1,
int x2, int y2, long long value) {
diff[x1][y1] += value;
diff[x2 + 1][y1] -= value;
diff[x1][y2 + 1] -= value;
diff[x2 + 1][y2 + 1] += value;
}所有矩形修改结束后，按照从上到下、从左到右的顺序计算：diff[i][j] += diff[i-1][j] + diff[i][j-1] - diff[i-1][j-1]。此时 diff[i][j] 就是最终矩阵中的值。
输入长度为 n 的数组和 m 次操作，每次把区间 [l, r] 加上 k。使用差分输出所有操作完成后的数组，并尝试与逐个修改元素的做法比较运行次数。
现在你已经能够根据数据范围判断复杂度，使用二分缩小查找范围，用前缀和优化区间查询，并用差分优化批量区间修改。
竞赛中的概率题通常不要求背完整本概率论。真正高频的是两种建模：统计“会出现多少个”时，把总贡献拆成许多 0-1 变量；询问“到结束还要多久”时，先分析下一步会走到哪里。
题目背景可能是抽球、排列、骰子或随机游走，但拆掉故事后，大多数入门题都会落到右边两句话中的一条。
枚举每一个可能贡献 1 的对象。
支付当前一步，再加上下一状态的期望。
分清样本空间、事件和条件概率，尤其注意不放回后总数会减少。
用期望线性性与 0-1 指示变量处理次数、位置和元素对。
从当前状态先走一步，列出每个下一状态及其发生概率。
知道 DAG 可以倒序递推，有自环要移项，互相依赖可能要解方程。
一次随机过程所有可能出现的基本结果组成样本空间。如果这些结果等概率，事件 A 的概率就是“满足 A 的结果数 ÷ 所有结果数”。例如公平骰子出现偶数，对应结果是 2、4、6，因此概率为 3 / 6 = 1 / 2。
袋中有 2 个黑球和 3 个白球，求“先黑后白”的概率。第一次抽黑球后不放回，袋里只剩 4 个球，其中 3 个是白球。
P(B | A) 表示在 A 已经发生的条件下，B 再发生的概率。不要把两个阶段都机械地写成原来的分母。
离散随机变量 X 可能取值 x₁, x₂, …，对应概率为 p₁, p₂, …，那么每个结果按出现概率加权：
公平骰子的期望是 (1+2+3+4+5+6) / 6 = 3.5。骰子不可能掷出 3.5，它描述的是重复许多次后的平均点数。
“期望为 1.2 次”不代表某一次会发生 1.2 次。一次结果仍然是整数，1.2 只描述很多次试验的平均水平。
X、Y 即使互相影响，这个等式仍然成立。
事件发生贡献 1，不发生贡献 0，期望正好等于发生概率。
独立性会影响乘积或联合概率的计算，但 E[X₁ + X₂ + …] = E[X₁] + E[X₂] + … 始终成立。随机排列中的不同逆序对并不独立，仍然可以逐对计算贡献。
01 出现多少次？把 n 个 0 和 m 个 1 随机排列。总长度记为 N = n + m，我们统计相邻位置中“左边是 0、右边是 1”的位置数量。
确定候选对象相邻位置对共有 N - 1 个：(1,2)、(2,3)、…、(N-1,N)。
为每一对设指示变量第 i 对恰好是 01 时 Iᵢ = 1，否则为 0。
算单个候选的概率左边取到 0 的概率为 n/N；用掉一个 0 后，右边取到 1 的概率为 m/(N-1)。
把所有贡献相加E[X] = (N-1) · n/N · m/(N-1) = nm/N。
01 与“相邻两位不同”不是同一道题异色相邻还包括 10。它与 01 对称，所以异色相邻的期望是 2nm/(n+m)；看到方向要求时不要顺手多乘或少乘 2。
使用 long double 保留计算精度
总长度是 n + m
直接代入 nm/(n+m)
按题目要求输出小数
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
long long zeroCount, oneCount;
cin >> zeroCount >> oneCount;
// ① 所有 N-1 个相邻位置的贡献相加后，公式约成 nm/N。
long double totalLength = zeroCount + oneCount;
long double expected =
(long double)zeroCount * oneCount / totalLength;
// ② 普通实数答案按题目要求保留小数位。
cout << fixed << setprecision(6)
<< expected << '\n';
return 0;
}候选相邻位置有 4 个，每一个成为 01 的概率是 2/5 × 3/4 = 3/10，所以期望为 4 × 3/10 = 1.2。
随机打乱 1…n。对于每一对数 a < b，只关心它们的相对顺序：a 在 b 前和 b 在 a 前完全对称，所以这一对形成逆序的概率为 1/2。
不同元素对会共享元素，彼此并不独立；这里仍然能相加，正是线性期望最有力量的地方。
令 f[u] 表示从状态 u 出发到结束的期望代价。站在 u 时先发生一次操作，付出当前代价；之后以不同概率进入下一状态 v：
如果一次操作的代价就是 1，最前面一定有一个 1。终止状态不再需要操作，所以通常令 f[target] = 0。
n²？位置为 0,1,…,n，从 0 出发；中间位置等概率向左或向右一步，到达 n 后停止；在 0 不能向左，只能走到 1。设 f[i] 为从 i 到 n 的期望步数。
先走一步，再按两种方向的概率加权。
在 0 没有随机选择，只能走到 1。
方程可化为 d[i+1] = d[i] + 2。
由 d[1]=1 得到连续奇数。
f[i] 同时依赖 f[i-1] 和 f[i+1]，依赖关系有环，本质是一组线性方程。这里利用一维结构作差化简；更一般的题可能需要移项、树形递推或高斯消元。
如果状态编号保证所有转移都从较小编号走向较大编号，就没有环。下面的模型中，从每个非终点状态会等概率选择一条出边，求从 1 走到终点 n 的期望步数。
expected[u] 表示从 u 到终点的期望步数
终点 expected[n] 默认为 0
倒序保证后继状态已经算好
每条出边概率都是 1/degree
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
vector<vector<int>> nextState(n + 1);
while (m--) {
int u, v;
cin >> u >> v; // 题目保证 u < v，因此状态图是 DAG
nextState[u].push_back(v);
}
// ① expected[n] = 0；从 n-1 倒推到 1。
vector<long double> expected(n + 1, 0);
for (int u = n - 1; u >= 1; u--) {
int degree = (int)nextState[u].size();
if (degree == 0) continue; // 没有出边的状态也视为终止状态
// ② 当前一步贡献 1，下一状态按 1/degree 加权。
expected[u] = 1;
for (int v : nextState[u]) {
expected[u] += expected[v] / degree;
}
}
cout << fixed << setprecision(6)
<< expected[1] << '\n';
return 0;
}4 4 1 2 1 3 2 4 3 4
2.000000
f[2]=f[3]=1，因为走一步就到 4；因此 f[1]=1+½f[2]+½f[3]=2。代码只是按照依赖顺序把这组方程算出来。
某状态 u 每次操作后，有 1/3 概率仍留在 u，有 2/3 概率进入 v。右边出现 f[u] 并不代表方程写错：
单个自环通常可以直接移项；多个状态互相依赖时，可能需要联立方程、高斯消元，或者利用题目的链、树等特殊结构化简。不要硬套普通 DP 的循环顺序。
如果答案是分数 a/b，题目却要求对质数 MOD 取模，通常把除以 b 改写成乘以 b 的模逆元：a / b ≡ a · b^(MOD-2) (mod MOD)。这表示“模意义下的分数”，不是小数近似。
快速幂把指数复杂度降到 O(log MOD)
指数为奇数时把当前底数乘入答案
底数每轮平方，指数每轮减半
质数模数下 x^(MOD-2) 是 x 的逆元
long long power(long long base, long long exponent, long long mod) {
long long answer = 1;
// 二进制快速幂：每轮处理 exponent 的最低位。
while (exponent > 0) {
if (exponent & 1) answer = answer * base % mod;
base = base * base % mod;
exponent >>= 1;
}
return answer;
}
long long inverse(long long value, long long primeMod) {
// 要求 primeMod 是质数，且 value 不能被 primeMod 整除。
return power(value, primeMod - 2, primeMod);
}输出小数使用 double / long double，按误差或小数位要求输出。对质数取模分母乘模逆元，所有加减乘都在模意义下进行。先看题目不要看到概率就默认用浮点数，也不要看到分数就擅自取模。期望可以是 3.5，即使一次试验永远取不到 3.5。
线性期望拆的是和，不要求各个贡献相互独立。
已经取走一个对象后，下一次选择的总数必须减一。
求期望步数时经常忘记首步方程最前面的 +1。
01 只是一种方向，异色相邻才同时包含 01 与 10。
互相依赖的期望状态是一组方程，必须先化简或求解。
随机排列 1…n，不用枚举排列，独立推导逆序对数量的期望。
掷公平骰子沿格子前进，超过终点时停在终点，写出每个位置的期望方程。
目标：状态与边界每轮有概率成功结束，否则留在原状态，先列方程，再通过移项求期望轮数。
目标：识别方程统计“多少个”就拆贡献，问“还要多久”就看下一步。先把随机过程翻译成随机变量和状态方程，再决定是直接求和、倒序 DP，还是解线性方程。
将从数据怎样组织和访问开始，逐步学习线性结构、栈与队列以及树结构，为后续算法打好基础。
动态规划不是背公式，而是把一个大问题拆成会重复出现的小问题，保存小问题答案，再按照依赖顺序组合出最终答案。先掌握线性递推和背包合并，再把状态依赖放到树结构上。
状态沿数组、时间或位置依次推进，当前状态通常依赖前面的若干状态。
在容量限制下做选择，重点区分物品能选几次以及容量的遍历方向。
先计算儿子，再把各个子树的信息合并到父亲；进一步认识树形背包。
用两次 DFS 同时得到每个节点作为根时的整树答案。
从短区间到长区间，按分界点或左右端点组合出答案。
DP 适合具有重复子问题和无后效性的结构。先明确状态能否完整描述过去对未来的影响，再决定是否使用动态规划。
每个状态是一个节点，依赖关系是一条边。记忆化搜索从答案出发，只计算真正访问到的状态；递推则按拓扑顺序主动填表。两者复用的是同一套状态与转移，选择更自然、更不易越界的实现即可。
先学会把一句状态定义写完整，再推导每一种可能的决策。
线性 DP 的状态按照数组下标、位置或时间从前向后排列。计算第 i 个状态时，只依赖已经算出的较小下标，因此可以按固定顺序递推。
状态用一句完整的话说明 dp[i] 表示什么，尤其要说清“处理到哪里”和“是否必须选择当前位置”。转移枚举到达当前状态的最后一个决策，从已经正确的小状态转移过来。顺序必须保证计算 dp[i] 时，它依赖的状态已经计算完成。例如依次处理前 1 个、前 2 个……前 n 个元素，或依次到达每个位置。
不同决策可能继续询问同一个“小规模问题”，保存答案能避免重复计算。
大问题的最优答案，可以由一个或多个小问题的最优答案组合得到。
只要状态值和必要维度相同，未来不需要知道此前具体怎样走到这里。
定义状态先写中文：dp[i] 表示考虑前 i 个元素时的最大收益。
枚举最后决策第 i 个元素选还是不选？最后一步从哪个位置走来？
写出转移把所有合法来源列全，再取最大、最小、求和或逻辑或。
初始化与边界明确空集合、起点和不可达状态分别应该是什么值。
确定答案位置答案是 dp[n]、所有状态最大值，还是某个指定终点？
给定长度为 n（n ≥ 1）的整数数组，可以选择若干元素，但不能选择两个相邻元素。允许一个元素都不选，求所选元素之和的最大值。
dp[i] 表示只考虑前 i 个元素时，可以获得的最大和。
答案保持为 dp[i - 1]。
第 i - 1 个不能选，答案为 dp[i - 2] + value[i]。
dp[i] = max(dp[i-1], dp[i-2] + value[i])。
数组为 [2, 7, 9, 3, 1]。设 dp[0] = 0，逐个比较“选当前”和“不选当前”。
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<long long> value(n + 1);
for (int i = 1; i <= n; i++) {
cin >> value[i];
}
vector<long long> dp(n + 1, 0);
dp[1] = max(0LL, value[1]);
for (int i = 2; i <= n; i++) {
dp[i] = max(dp[i - 1], dp[i - 2] + value[i]);
}
cout << dp[n] << '\n';
return 0;
}5 2 7 9 3 1
12
计算 dp[i] 时只使用 dp[i-1] 和 dp[i-2]，更早的状态不会再次使用，因此只需保存最近两个值。
long long twoBack = 0; // dp[i - 2]
long long oneBack = max(0LL, value[1]); // dp[i - 1]
for (int i = 2; i <= n; i++) {
long long current = max(oneBack, twoBack + value[i]);
twoBack = oneBack;
oneBack = current;
}初学时建议先写含义清晰的 dp 数组，确认状态和转移正确后再改成滚动变量。需要还原具体选择方案时，通常仍要保留完整状态或前驱记录。
记忆化搜索从目标状态递归求解，写法接近原始递推关系；要设置“未计算”标记并留意递归深度。递推填表从初始状态按依赖顺序计算，没有递归栈；需要明确哪些状态可达以及循环顺序。还原方案除最优值外保存 parent 或当前决策，最后从答案状态反向追踪。前 i 个的答案dp[i] 包含前 i 个元素的整体最优值，答案常在 dp[n]，本节例题属于这一类。必须以 i 结尾dp[i] 表示必须选择第 i 个元素的答案，例如最长上升子序列；最终答案通常是所有 dp[i] 的最大值。多状态如果当前位置有“选 / 不选”“持有 / 不持有”等不同状态，可增加一维或分别维护多个数组。前者允许第 i 个元素不参与答案，后者要求答案必须落在 i。状态定义只差几个字，转移和最终答案位置却会完全不同。
只写“dp[i] 是最大值”，没有说明考虑范围以及是否必须选择 i。
只考虑选择当前元素，忘记“不选当前”同样是一种合法决策。
不允许空方案时却把所有状态初始化为 0，会把不存在的方案当成合法答案。
“必须以 i 结尾”的状态通常需要在所有 i 中取最优，而不一定直接输出 dp[n]。
第 i 级台阶有一个花费，每次可以走 1 级或 2 级。请定义“到达第 i 级的最小花费”，分别写出转移、初值和答案位置，再尝试用两个变量优化空间。
背包问题研究“若干物品 + 一个容量限制 + 如何选择物品”。真正需要掌握的不是模板本身，而是状态表示、物品使用次数以及容量为什么要按特定方向遍历。
0/1 背包每件物品最多选择一次；一维优化后，容量必须从大到小遍历。完全背包每件物品可以选择无限次；一维写法通常让容量从小到大遍历。多重背包每件物品有指定数量，需要拆分、二进制优化或使用单调队列等方法。有 n 件物品，第 i 件物品重量为 weight[i]、价值为 value[i]，背包容量为 W。每件物品只能选择 0 次或 1 次，求总重量不超过 W 时的最大总价值。
依次考虑前 1 件、前 2 件……前 n 件物品。
dp[i][capacity] 表示只考虑前 i 件物品、容量上限为 capacity 时的最大价值。
第 i 件物品只有“不选”和“选择”两种情况。
处理完全部物品后，答案是 dp[n][W]。
当 capacity < weight[i] 时装不下当前物品，只能不选；否则在两种决策中取最大值：
两种来源都在第 i - 1 行，因此同一件物品不会被重复使用。
容量 W = 8，四件物品分别为 (重量, 价值) = (2,3)、(3,4)、(4,5)、(5,8)。每处理一件物品，就用上一行更新当前行。
最终 dp[4][8] = 12，对应选择重量 3、价值 4 的物品和重量 5、价值 8 的物品。
vector<vector<long long>> dp(
n + 1, vector<long long>(capacityLimit + 1, 0)
);
for (int i = 1; i <= n; i++) {
for (int capacity = 0; capacity <= capacityLimit; capacity++) {
dp[i][capacity] = dp[i - 1][capacity];
if (capacity >= weight[i]) {
dp[i][capacity] = max(
dp[i][capacity],
dp[i - 1][capacity - weight[i]] + value[i]
);
}
}
}第 i 行只依赖第 i - 1 行，可以复用同一个 dp[capacity] 数组。为了让右侧的 dp[capacity-weight] 仍然代表“没有处理当前物品”的旧值，容量必须从大到小更新。
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, capacityLimit;
cin >> n >> capacityLimit;
vector<long long> dp(capacityLimit + 1, 0);
for (int i = 1; i <= n; i++) {
int weight;
long long value;
cin >> weight >> value;
for (int capacity = capacityLimit; capacity >= weight; capacity--) {
dp[capacity] = max(dp[capacity], dp[capacity - weight] + value);
}
}
cout << dp[capacityLimit] << '\n';
return 0;
}4 8 2 3 3 4 4 5 5 8
12
假设只有一件重量 2、价值 3 的物品，容量为 6。如果容量从小到大更新：
倒序读取的是上一轮保留下来的旧状态，保证当前物品最多使用一次；正序会读取本轮刚更新的新状态，因此允许继续使用当前物品。
完全背包仍可使用一维 dp[capacity]，但容量从小到大更新。这样 dp[capacity-weight] 可能已经在本轮加入当前物品，继续转移正好表示再次选择它。
vector<long long> dp(capacityLimit + 1, 0);
for (int i = 1; i <= n; i++) {
int weight;
long long value;
cin >> weight >> value;
for (int capacity = weight; capacity <= capacityLimit; capacity++) {
dp[capacity] = max(dp[capacity], dp[capacity - weight] + value);
}
}0/1：容量倒序右侧读取上一轮状态，阻止同一件物品在本轮重复进入答案。完全：容量正序右侧允许读取本轮新状态，从而继续使用当前物品。循环不能随便交换求最值时物品在外、容量在内最清晰；求方案数时交换循环还可能改变“组合 / 排列”的含义。不超过容量允许什么都不选，通常把所有 dp[capacity] 初始化为 0，最后读取 dp[W]。恰好装满只有 dp[0] = 0 合法，其他容量初始化为负无穷，表示暂时不可达。方案计数若求方案数，初始通常是 dp[0] = 1，转移使用加法而不是取最大值。const long long NEGATIVE_INFINITY = -(1LL << 60);
vector<long long> dp(capacityLimit + 1, NEGATIVE_INFINITY);
dp[0] = 0;
// 转移时只有来源可达，才能继续选择物品。
if (dp[capacity - weight] != NEGATIVE_INFINITY) {
dp[capacity] = max(dp[capacity], dp[capacity - weight] + value);
}n × W ≤ 10⁷ 左右普通 O(nW) 通常可行，仍需结合语言、时限和常数判断。W 非常大容量不能直接作为数组维度，考虑按价值 DP、稀疏状态或其他问题结构。价值可能溢出 int总价值可能超过 2 × 10⁹ 时，dp 数组应使用 long long。给出 n 件物品和容量 W，分别按“每件最多一次”和“每件不限次数”求最大价值。先用二维 0/1 背包打印小数据的整张 dp 表，再压缩成一维，并用“一件重量 2、价值 3、容量 6”的数据验证倒序得到 3、正序得到 9。
现在你已经掌握状态、转移、初始化、遍历顺序和答案位置，并能解释 0/1 背包与完全背包循环方向不同的原因。下一步把这些方法带到树结构中。
在线性 DP 中，我们沿着数组从左到右计算；到了树上，节点会同时分出多个方向，应该先算谁就不再显然。树形 DP 做的第一件事，就是把无向的树整理成“父亲依赖儿子”的计算结构，再把每棵小子树的答案一层层向上合并。
选 1 为根后，节点 2 管理子树 {2, 4, 5}，节点 3 管理子树 {3}。只要先算出这两棵小子树，根 1 就不必重新进入它们逐个检查。
分清有向父子输入与无向边输入，知道根、父亲、儿子和子树分别是什么。
程序虽然从根向下进入，DP 状态却在回溯时从叶子向上完成。
从一个状态的子树大小，过渡到选 / 不选两个状态，并推导完整转移。
理解加入人数限制后，为什么每个儿子会变成一个需要逐组合并的背包。
遍历工具DFS 负责给出后序计算顺序：先进入子树，回溯时再处理当前节点。DP 核心明确 dp[u] 描述以 u 为根的子树中的什么信息，以及怎样合并每个儿子。一句话模板先算儿子，再用儿子的答案计算父亲；DFS 决定顺序，状态转移决定答案。如果输入直接说明“父亲是谁”，可以只保存父亲到儿子的有向边；如果输入只是 n - 1 条无向边，就要双向加边，并在 DFS 中跳过父亲。无根树在题目没有特殊要求时通常可任选 1 号节点为根。
parent child 已经确定方向，只需 children[parent].push_back(child)。
同时加入 u → v 和 v → u，遍历时通过 parent 防止走回头路。
根只是在无向树上人为确定计算方向，不会改变树的边和连通关系。
一次 DFS 的完成顺序是叶子到根，恰好满足子状态先于父状态。
vector<vector<int>> graph(n + 1);
void dfs(int u, int parent) {
// 1. 初始化 dp[u]
for (int v : graph[u]) {
if (v == parent) continue;
dfs(v, u);
// 2. 使用已经算好的 dp[v] 更新 dp[u]
}
}这是初学树形 DP 最容易混淆的一点。调用 dfs(1, 0) 时，程序先进入 1，再进入 2、4；但 4 没有儿子，会最先完成状态。回到 2 后继续完成 5，等 4、5 都算完，2 才能合并它们。
dfs(v, u) 只是保证计算顺序；真正的 DP 是回溯后的 dp[u] += dp[v]、取最大值或背包合并。没有清晰的状态定义与转移，只有搜索。
定义 subtreeSize[u] 为“以 u 为根的子树节点数”。初始化时 u 自己贡献 1；每完成一个儿子 v，就把 subtreeSize[v] 加到 u。于是：
每个节点访问一次，每条边至多检查两次，时间复杂度 O(n)，邻接表与状态数组占 O(n) 空间。
以 u 的不同儿子为根的子树互不重叠：一个节点不可能同时属于两个儿子的子树。因此，u 的子树可以被完整拆成“u 自己 + 每个儿子的子树”，既没有遗漏，也不会重复计算。
叶子没有儿子，求和部分为空，只剩自己这 1 个节点，所以 subtreeSize[leaf] = 1。这同时解释了为什么初始化必须放在遍历儿子之前。
当前节点先算自己
跳过来时的父亲
先递归算完儿子
回溯时合并答案
#include <bits/stdc++.h>
using namespace std;
// 保存无向树，以及每个节点的子树大小。
vector<vector<int>> graph;
vector<int> subtreeSize;
void dfs(int u, int parent) {
subtreeSize[u] = 1; // ① 先把节点 u 自己算进去
for (int v : graph[u]) {
if (v == parent) continue; // ② 无向边会通回父亲，必须跳过
dfs(v, u); // ③ 先得到儿子 v 的完整答案
subtreeSize[u] += subtreeSize[v]; // ④ 回溯时合并 v 的子树
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
graph.assign(n + 1, {});
subtreeSize.assign(n + 1, 0);
// 输入 n-1 条无向边，每条边必须双向加入邻接表。
for (int i = 1; i < n; i++) {
int u, v;
cin >> u >> v;
graph[u].push_back(v);
graph[v].push_back(u);
}
dfs(1, 0); // 任取 1 为根，0 表示 1 没有父亲
for (int u = 1; u <= n; u++) cout << subtreeSize[u] << " \n"[u == n];
}5 1 2 1 3 2 4 2 5
5 3 1 1 1
每位员工 u 有快乐值 happiness[u]。如果 u 参加舞会，u 的直接下属不能参加；求整棵公司树能获得的最大快乐值。父亲能否选择某个儿子，取决于父亲自己是否参加，因此一个状态不够。
假设儿子 v 的最大值恰好来自“选择 v”。当父亲 u 也被选择时，这个最大值就不合法；但单独一个 best[v] 已经丢失了“v 是否参加”的信息。父亲未来还要询问的条件，必须保留在状态中。
u 不参加时，u 的整棵子树能够获得的最大快乐值。
u 参加时，u 的整棵子树能够获得的最大快乐值。
dp[u][0] = 0，dp[u][1] = happiness[u]。
根可参加也可不参加，取 max(dp[root][0], dp[root][1])。
先暂时忘掉整棵树，只看相邻的父亲 u 和儿子 v。父亲不参加时没有给 v 施加限制，v 可以在自己的两种状态里选较大的；父亲参加时，为避免相邻两人同时出现，v 只能不参加。
继续使用开头那棵树，节点 1—5 的快乐值分别是 5、4、3、6、2。把状态写成二元组 (不参加, 参加)，严格按照 4、5、2、3、1 的顺序计算：
根 1 参加，所以直接儿子 2、3 都不参加；但限制只作用于直接相邻节点，孙子 4、5 仍然可以参加。最终选择 1、4、5，快乐值为 5 + 6 + 2 = 13。
下面约定每行 employee boss 表示 boss 是 employee 的直接上司。建边时使用 children[boss].push_back(employee)，并用 hasParent 找到唯一没有上司的根，不能默认根一定是 1。
先定义选与不选
叶子也满足初始化
按父亲状态合并儿子
找到真正的根后取答案
#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> children;
// dp[u][0]：u 不参加；dp[u][1]：u 参加。
vector<array<long long, 2>> dp;
vector<long long> happiness;
void dfs(int u) {
dp[u][0] = 0; // ① u 不参加，自己的贡献为 0
dp[u][1] = happiness[u]; // ② u 参加，先加入自己的快乐值
for (int v : children[u]) {
dfs(v); // ③ 儿子的两个状态必须先算完
dp[u][0] += max(dp[v][0], dp[v][1]); // u 不参加：v 可选可不选
dp[u][1] += dp[v][0]; // u 参加：v 必须不参加
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
children.assign(n + 1, {});
dp.assign(n + 1, {0, 0});
happiness.resize(n + 1);
vector<bool> hasParent(n + 1, false);
for (int u = 1; u <= n; u++) cin >> happiness[u];
// 输入 employee boss：只保存 boss → employee，并标记谁有父亲。
for (int i = 1; i < n; i++) {
int employee, boss;
cin >> employee >> boss;
children[boss].push_back(employee);
hasParent[employee] = true;
}
int root = 1;
while (hasParent[root]) root++; // ④ 唯一没有上司的人才是根
dfs(root);
cout << max(dp[root][0], dp[root][1]) << '\n'; // 根可选可不选
}5 5 4 3 6 2 2 1 3 1 4 2 5 2
13
边应该指向谁？employee boss 表示 boss 管理 employee，所以保存 boss → employee。
根在哪里？每个员工出现为下属时标记 hasParent；唯一没被标记的人就是最高上司。
什么时候转移？必须放在 dfs(v) 之后，因为此时儿子的两个状态才已经完整。
为什么用 long long？单人的快乐值也许不大，但许多节点相加后可能超过 32 位整数范围。
负快乐值怎么办？u 不参加的初值是 0，转移会自然跳过负收益的儿子；无需强迫任何人参加。
答案为什么看根？根的子树就是整棵树，它的 0 / 1 两种状态已经覆盖所有合法方案。
普通舞会只关心“选不选 u”。如果再要求最多选择 m 个人，父亲合并儿子时还必须知道每棵子树用了几个名额。这个新增条件会影响后续决策，所以人数成为新的状态维度。
若要求“恰好选择 j 人”，状态可扩展为 dp[u][j][0/1]：在 u 的子树中恰好选择 j 人，且 u 不选 / 选择时的最大快乐值。处理一个儿子 v 时，枚举 k 表示从 v 的子树中选择多少人：
j 是合并后的总人数，k 分给当前儿子，j-k 属于 u 与此前已处理的儿子。父亲被选时，儿子只能取“不选”状态。
例如当前总人数 j = 4，正在合并儿子 v。k 可以是 0、1、2……；当 k = 2 时，就是把 2 个名额交给 v 的子树，把剩余 2 个名额留给此前已经合并的部分。枚举所有合法拆分并取最大值，才不会漏掉最优分配。
准确初始化dp[u][0][0] = 0、dp[u][1][1] = happiness[u]，其余状态为负无穷，防止不存在的方案参与转移。限制枚举范围k 不应超过 v 的子树大小，j 不应超过当前已经合并的节点数与人数上限 m。倒序枚举 j原地合并时从大到小枚举总人数，避免本轮刚加入的同一个儿子被重复使用；也可使用新数组合并。此前部分选了几人
当前儿子选了几人
合并后的新状态
过滤不存在的方案
// ① dp 的第二维表示“恰好选择的人数”，NEG 表示不可达。
fill(dp[u].begin(), dp[u].end(), array<long long, 2>{NEG, NEG});
dp[u][0][0] = 0; // 不选 u，已选 0 人
dp[u][1][1] = happiness[u]; // 选择 u，已选 1 人
subtreeSize[u] = 1;
for (int v : children[u]) {
dfs(v);
// ② 用 next 接收结果，保证当前儿子 v 只会被合并一次。
vector<array<long long, 2>> next(
limit + 1, array<long long, 2>{NEG, NEG}
);
// ③ 枚举名额拆分：used 给此前部分，take 给 v 的子树。
for (int used = 0; used <= min(limit, subtreeSize[u]); used++) {
for (int take = 0;
take <= min(limit - used, subtreeSize[v]);
take++) {
long long childBest = max(dp[v][take][0], dp[v][take][1]);
// ④ u 不选时，v 可选可不选；u 选时，v 只能不选。
if (dp[u][used][0] != NEG && childBest != NEG) {
next[used + take][0] = max(
next[used + take][0],
dp[u][used][0] + childBest
);
}
if (dp[u][used][1] != NEG && dp[v][take][0] != NEG) {
next[used + take][1] = max(
next[used + take][1],
dp[u][used][1] + dp[v][take][0]
);
}
}
}
dp[u] = move(next);
subtreeSize[u] += subtreeSize[v];
}新数组把“合并前”和“合并后”彻底分开，更容易证明同一个儿子只使用一次。熟练后再改成原地更新，并让总人数 j 倒序遍历；两种写法的状态与转移完全相同。
上面的合并式使用“恰好选择 j 人”，所以人数可以拆成明确的 k 与 j-k；若题目要求最多 m 人，最后在 0..m 中取最大值。直接把状态定义成“最多”却按“恰好”初始化，容易让不可达方案悄悄混入答案。
确定根与建边方式输入是否已经给出父子关系？无向边是否正确双向加入并跳过父亲？
写完整状态定义说明范围是 u 的子树，是否选择 u，以及容量维度表示“恰好”还是“至多”。
推导单个儿子的贡献假设 dp[v] 已知，逐种讨论 u 的状态，写出 v 可以提供哪些合法选择。
设计初始化和合并顺序先初始化叶子也成立的状态，再逐个儿子合并；不可达状态使用负无穷。
确认答案与复杂度根是否固定、答案取哪个状态、递归深度和 O(nm²) 是否能通过。
树高最坏可达 n。若 n 很大，递归 DFS 可能栈溢出；可以改用显式栈记录父亲与遍历顺序，再按顺序逆序做同样的“儿子 → 父亲”转移。算法仍是树形 DP，只是遍历实现不同。
只问每个子树尝试定义 dp[u]，让它完整描述 u 子树的大小、和、最大值或最优解。相邻节点互相限制尝试增加“u 选 / 不选”“u 是什么颜色”等状态，保留父亲做决策时仍需知道的信息。限制选择数量增加人数或容量维度，并把不同儿子的状态当成多个背包分组逐一合并。根固定且只求一次优先沿“儿子 → 父亲”的方向后序计算；先保证每个儿子的状态完整，再处理当前节点。求每个节点的子树权值和。先用中文定义 sum[u]，再说明为什么初始化为 value[u]。
树上每个节点有权值，任意相邻两点不能同时选择。不要看模板，先从父亲的两种情况推出转移。
目标：从限制设计状态恰好选择 m 个节点且相邻节点不能同时选。先写出三维状态，再用 next 数组逐棵合并子树。
目标：掌握树形背包① dp[u] 的范围为什么通常是 u 的子树？② 为什么转移写在 dfs(v) 之后？③ 父亲参加时为什么只能读取 dp[v][0]？④ 树形背包为什么要逐个儿子合并，并区分“恰好”与“至多”？能用自己的话说清楚，再开始刷题。
普通树形 DP 沿“儿子 → 父亲”完成子树状态，树形背包在此基础上增加容量并逐棵合并。下一节将面对一个新要求：当题目要每个节点都成为一次根，怎样避免重复计算整棵树。
从“固定一个根”走向“每个点都做根”，学习两次 DFS 如何复用答案。
树形 DP 通常先选定一个根，只计算这个根对应的答案；但有些题会追问“如果 1、2、3……每个节点分别作为根，答案是多少”。换根 DP 不会从每个节点重新跑一遍，而是先求出一个根的答案，再沿着每条边把已经算好的信息传给相邻节点。
把根从父亲 u 移到儿子 v 后，v 子树内的节点全部近 1，其余节点全部远 1。只要知道 v 的子树大小，就能 O(1) 得到新答案。
看到“每个节点作为根”或“求每个节点的整树答案”，知道暴力为什么会重复。
用子树大小与子树距离和，得到一个初始根的完整答案。
不背公式，亲自数清根移动后哪些节点变近、哪些节点变远。
正确处理无向边、父亲节点、long long，以及深链上的递归风险。
给定一棵 n 个节点的无权树，定义 answer[u] 为节点 u 到所有节点的距离之和。我们需要输出 answer[1..n]。例如下面这棵树，边为 1-2、1-3、2-4、2-5：
0 + 1 + 1 + 2 + 2 = 6以 2 为起点1 + 0 + 2 + 1 + 1 = 5以 3 为起点1 + 2 + 0 + 3 + 3 = 9一次遍历 O(n)，一共 n 次，最坏需要 O(n²)。
每条边只在两次 DFS 中经过，合计 O(n)。
相邻节点 u 与 v 的视角非常接近。根只沿一条边移动，所有节点的距离只可能增加 1 或减少 1；我们不需要重新寻找每条路径，只需要数出两类节点各有多少个。
size[u]以 1 为根时，u 的子树一共有多少个节点，包含 u 自己。
inside[u]从 u 出发，到 u 子树中所有节点的距离之和。
原树的边仍是无向的。传入 parent 只是避免 DFS 又沿原路返回，也让我们能够区分当前节点的儿子。
inside[v] 已经统计了 v 到它子树中所有节点的距离。现在起点从 v 移到父亲 u，每条路径都多经过边 u-v，而 v 子树共有 size[v] 个节点，所以统一增加 size[v]。
叶子初始化为 size[u] = 1、inside[u] = 0。等所有儿子都合并完，u 的两个状态才完整。
5311162000节点 2 收到叶子 4、5 的贡献：inside[2] = (0 + 1) + (0 + 1) = 2。节点 1 再收到 2 和 3：inside[1] = (2 + 3) + (0 + 1) = 6。因为 1 的子树就是整棵树，所以 answer[1] = inside[1]。
void collect(int u, int parent) {
size[u] = 1; // ① 子树先包含 u 自己
inside[u] = 0; // u 到自己的距离为 0
for (int v : graph[u]) {
if (v == parent) continue; // ② 不沿无向边走回父亲
collect(v, u); // ③ 先把儿子 v 的状态算完整
size[u] += size[v]; // ④ 合并 v 子树的节点数
// 从 v 换到 u 后，v 子树每个点的距离都多 1。
inside[u] += inside[v] + size[v];
}
}减去的是“变近”的总量，加上的是“变远”的总量。公式中的 size[v] 始终来自第一次 DFS 以 1 为根时得到的子树大小。
继续把根从 2 移到叶子 4：answer[4] = 5 + 5 - 2 × 1 = 8。同理可以得到所有节点的答案：
void reroot(int u, int parent) {
for (int v : graph[u]) {
if (v == parent) continue; // ① 每个节点只从父亲接收一次答案
// ② v 子树的 size[v] 个点近 1，其余 n-size[v] 个点远 1。
answer[v] = answer[u] + n - 2LL * size[v];
reroot(v, u); // ③ v 的答案已知，继续向它的儿子传递
}
}这里没有真的修改树，也没有把一个全局根来回搬动；我们只是由 answer[u] 计算并保存 answer[v]。每个节点只从它在第一次 DFS 中确定的父亲接收一次答案。
如果直接公式显得跳跃，可以先定义 outside[u]：从 u 到其子树之外所有节点的距离和。于是 answer[u] = inside[u] + outside[u]。对于 u 的儿子 v：
answer[u]inside[v] + size[v]n - size[v]把两式合并，inside[v] 会抵消，正好得到 answer[v] = answer[u] + n - 2 × size[v]。这说明两种写法本质相同。
直接换根代码更短，只保存 size、inside 和 answer，适合距离和模板题。inside / outside拆解更直观，也更容易迁移到不能直接化简的题目。真正要掌握的不是死记一个式子，而是找出“移根后哪些贡献改变、改变多少”。5
1 2
1 3
2 4
2 56 5 9 8 8读入无向树
向上收集 size 与 inside
确定初始根答案
向下推出所有 answer
#include <bits/stdc++.h>
using namespace std;
int n;
vector<vector<int>> graph;
vector<int> subtreeSize;
vector<long long> inside, answer;
// ② 第一遍 DFS：后序计算子树大小和子树内距离和。
void collect(int u, int parent) {
subtreeSize[u] = 1; // 叶子也包含自己
inside[u] = 0; // u 到自己的距离为 0
for (int v : graph[u]) {
if (v == parent) continue;
collect(v, u); // 儿子算完之后，父亲才能合并
subtreeSize[u] += subtreeSize[v];
// u 到 v 子树的每个点，都比 v 多走一条边。
inside[u] += inside[v] + subtreeSize[v];
}
}
// ④ 第二遍 DFS：由父亲的整树答案推出儿子的整树答案。
void reroot(int u, int parent) {
for (int v : graph[u]) {
if (v == parent) continue;
// v 子树内近 1，子树外远 1：-size[v] + (n-size[v])。
answer[v] = answer[u] + n - 2LL * subtreeSize[v];
reroot(v, u);
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
graph.assign(n + 1, {});
subtreeSize.assign(n + 1, 0);
inside.assign(n + 1, 0);
answer.assign(n + 1, 0);
// ① 输入 n-1 条无向边，每条边双向保存。
for (int i = 1; i < n; i++) {
int u, v;
cin >> u >> v;
graph[u].push_back(v);
graph[v].push_back(u);
}
collect(1, 0);
answer[1] = inside[1]; // ③ 1 的子树就是整棵树
reroot(1, 0); // 再把 answer[1] 传遍整棵树
for (int u = 1; u <= n; u++) {
cout << answer[u] << (u == n ? '\n' : ' ');
}
return 0;
}collect 只使用儿子的状态，方向是“叶子 → 根”；reroot 只使用父亲的整树答案，方向是“根 → 叶子”。两遍 DFS 的分工不同，不能交换执行顺序。
为什么用 long long？链形树的距离和可达到 n(n-1)/2，n 较大时会超过 int。
为什么每条边要加入两次？输入给的是无向树；第二次 DFS 也需要沿父亲到儿子的方向遍历所有邻接点。
为什么有 2LL？让乘法按 long long 计算，避免乘法先以 int 溢出后再赋值。
先任选一个根通常选 1，让无向树临时拥有父子关系。
设计向上收集的状态问清一个子树要交给父亲哪些信息，才能算出初始根的答案。
观察根移动一条边把所有节点按影响相同的方式分组，数出每组大小。
写出父到子的转移由父亲的整树答案 O(1) 推出儿子的整树答案。
两次遍历覆盖整棵树第一次儿子到父亲，第二次父亲到儿子，最后每个点都有答案。
answer[1] = inside[1]，再开始第二次 DFS？若边 u-v 的权值为 w，根移过这条边后，v 子树内每个节点的距离减少 w，子树外每个节点的距离增加 w：
第一次 DFS 中，儿子 v 给父亲 u 的贡献也相应变为 inside[v] + size[v] × w。
这个公式依赖“每个节点权重都为 1、目标是距离总和”。如果节点自带权值，就要把 size[v] 换成 v 子树的权值和；如果题目统计的不是距离和，也要重新分析移根后各组贡献。
在五节点示例树上，把根从 1 依次移到 2、4，标出每次变近与变远的节点。
目标：真正理解公式合上完整代码，只保留状态定义，自己完成两次 DFS 并用 n = 1、链和星形树测试。
目标：掌握实现细节每条边有正权，输出每个节点到所有节点的带权距离和；同时修改第一次与第二次 DFS。
目标：从变化量推导转移① 为什么从每个点重新 DFS 是 O(n²)？② inside[u] += inside[v] + size[v] 中为什么要加 size[v]？③ 根从 u 移到 v 后，哪两组节点的距离怎样变化？④ 为什么两次 DFS 就能得到全部答案？都能用自己的话说清楚，才算真正掌握。
第一遍把子树信息收向根，第二遍把整树答案传向叶子。以后遇到“每个节点都要求答案”的树上问题，先研究根只移动一条边时答案怎样变化，而不是先背模板。
把两个下标同时放进状态，从短区间开始组合出长区间答案。
线性 DP 常用一个下标表示“处理到哪里”，区间 DP 则同时记录左右端点，用 dp[l][r] 描述连续区间 [l, r]。它最重要的不是三层循环，而是弄清：一个长区间的最后一步，怎样由更短的区间组成。
长度为 1 的区间是最小问题；长度为 2 的状态依赖长度 1，长度为 3 再依赖更短状态。只要按长度递增，转移需要的答案就已经准备好。
说清 dp[l][r] 对哪个连续区间求什么答案，以及是否必须处理区间内全部元素。
理解为什么必须从短区间到长区间，并写对 len、l、r 的边界。
把 [l,r] 拆成 [l,k] 与 [k+1,r]，覆盖最后一步的所有可能。
根据端点选不选、能否配对，转移到 [l+1,r-1] 等更短区间。
dp[l][r] 到底比 dp[i] 多记录了什么？线性 DPdp[i] 常表示前 i 个元素的答案，左边界通常固定在开头。区间 DPdp[l][r] 同时记录左右端点，能够回答任意连续片段的问题。识别信号题目反复出现“合并相邻部分”“删除两端”“区间配对”“最后切成两段”。长度为 len、左端点为 l 时，右端点不是另一个独立循环变量，而是由区间长度唯一确定：
例如 n = 5、len = 3，合法区间依次是 [1,3]、[2,4]、[3,5]。必须满足 r ≤ n。
for (int len = 1; len <= n; len++) {
for (int l = 1; l + len - 1 <= n; l++) {
int r = l + len - 1;
// 此时计算区间 [l, r]
// 它依赖的更短区间已经算完
}
}这种顺序不能直观看出依赖是否已经完成。例如 dp[1][4] 可能依赖 dp[2][4]，它的左端点反而更大。按长度递增才同时保证 [l,k]、[k+1,r]、[l+1,r-1] 都先被计算。
[ l ... k ] [ k+1 ... r ]思考最后一次合并或最后一次切分发生在哪里。
l [ ............ ] r思考两端能否配对，或者删除、选择哪一个端点。
n 堆石子排成一行，每次只能把相邻两堆合并，代价等于两堆石子的总数。要求把所有石子合成一堆的最小总代价。对于 1、2、10：
dp[l][r]把第 l 堆到第 r 堆全部合并成一堆的最小代价。
dp[i][i] = 0一堆石子本来就是一堆，不需要发生合并。
当 [l,r] 最终合成一堆时，最后一次合并之前一定恰好剩下两堆连续石子。它们可以写成 [l,k] 和 [k+1,r]，其中 k 从 l 枚举到 r-1。
[ l ... k ]+[ k+1 ... r ]前两项分别是把左右两段各自合成一堆的最小代价；最后一项是把这两大堆合起来时必付的代价。
如果每次转移都重新循环求 sum(l,r)，会在三层枚举外又增加一层计算。前缀和让区间代价保持 O(1)。
1、2、10、4 的完整填表dp[i][i]无需合并0dp[1][2] / dp[2][3] / dp[3][4]只有一个分界3 / 12 / 14dp[1][3] / dp[2][4]k = 2 / k = 316 / 28dp[1][4]k = 333计算 dp[1][4] 时，区间总和固定为 17，但最后分成哪两段并不固定。把三个候选方案真正代入：
0 + 28 + 1745[1,1] 与 [2,4]3 + 14 + 1734[1,2] 与 [3,4]16 + 0 + 1733[1,3] 与 [4,4]，最优无论前面怎样合并，最后一刻一定只剩左右相邻的两大堆。它们之间必有且只有一条分界线 k。枚举 l ≤ k < r 就枚举了所有可能的最后一步；左右两段内部的最佳合并方式已经分别保存在两个较短状态中。
4
1 2 10 433前缀和负责区间代价
INF 与对角线负责初值
len 保证先短后长
k 枚举最后一次分界
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
// ① 前缀和：prefix[r] - prefix[l-1] 可 O(1) 求 [l,r] 总石子数。
vector<long long> a(n + 1), prefix(n + 1, 0);
for (int i = 1; i <= n; i++) {
cin >> a[i];
prefix[i] = prefix[i - 1] + a[i];
}
// ② 求最小值：先设为 INF；单堆无需合并，所以 dp[i][i] = 0。
const long long INF = 4'000'000'000'000'000'000LL;
vector<vector<long long>> dp(
n + 1, vector<long long>(n + 1, INF)
);
for (int i = 1; i <= n; i++) dp[i][i] = 0;
// ③ 先枚举区间长度：计算长区间时，所有短区间已经完成。
for (int len = 2; len <= n; len++) {
for (int l = 1; l + len - 1 <= n; l++) {
int r = l + len - 1; // 闭区间长度为 r-l+1
long long intervalSum = prefix[r] - prefix[l - 1];
// ④ 枚举最后一次合并的分界：[l,k] + [k+1,r]。
for (int k = l; k < r; k++) {
dp[l][r] = min(
dp[l][r],
dp[l][k] + dp[k + 1][r] + intervalSum
);
}
}
}
cout << dp[1][n] << '\n'; // 整段 [1,n] 的最小代价
return 0;
}prefix 快速算本次合并代价；dp[i][i] = 0 给出最小问题；len 决定合法计算顺序；k 穷举最后一次合并。其余代码只是输入、存储与输出。
给定只含 ( ) [ ] 的字符串，求最长合法括号子序列长度。子序列允许跳过字符，但不能改变相对顺序。例如 ([)] 不是合法括号串，却能选择 () 或 []，答案为 2。
子串必须连续，子序列可以跳过若干字符。本题的 dp[l][r] 表示在整个区间里“挑选”字符，因此不要求最终选出的字符在原串中连续。
dp[l][r]字符串区间 [l,r] 中能选出的最长合法括号子序列长度。
dp[i][i] = 0单个括号无法组成一对，空区间的答案也视为 0。
(区间 [l+1, r-1] 的最优子序列)+ 2如果 s[l] 与 s[r] 是 () 或 []，可以把它们包在中间最优解两侧：
当区间长度为 2 时，中间是空区间，贡献为 0，所以一对匹配括号得到长度 2。
合法序列还可能像 (())[] 一样由两段组成，因此仍要枚举分界点 k：
k 从 l 到 r-1。这个转移也自然覆盖了“不使用左端点”或“不使用右端点”的情况，因为单字符区间贡献为 0。
[1,2] = "(["端点不配对，切分后仍为 00[1,3] = "([)"外层 () 配对，中间单字符贡献 02[2,4] = "[)]"外层 [] 配对，中间单字符贡献 02[1,4] = "([)]"切分后继承 [1,3] 或 [2,4] 的答案24
([)]2先判断左右端点
能配对就包住中间
再枚举所有切分
始终保留最大长度
#include <bits/stdc++.h>
using namespace std;
// 只有同类型的左括号与右括号才能组成一对。
bool match(char left, char right) {
return (left == '(' && right == ')') ||
(left == '[' && right == ']');
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
string s;
cin >> n >> s;
s = " " + s; // 补一个空格，让字符串下标与 dp 的 1-based 下标一致
// 单字符和空区间都无法形成括号对，初值 0 正好符合定义。
vector<vector<int>> dp(n + 2, vector<int>(n + 2, 0));
// ① 按长度递增，保证 [l+1,r-1] 和切分后的区间都已算好。
for (int len = 2; len <= n; len++) {
for (int l = 1; l + len - 1 <= n; l++) {
int r = l + len - 1;
// ② 来源一：左右端点配对，包住中间的最优子序列。
if (match(s[l], s[r])) {
dp[l][r] = dp[l + 1][r - 1] + 2;
}
// ③ 来源二：枚举 k，把两个合法子序列首尾拼接。
for (int k = l; k < r; k++) {
dp[l][r] = max(
dp[l][r],
dp[l][k] + dp[k + 1][r]
);
}
}
}
cout << dp[1][n] << '\n'; // 整个字符串中的最大合法长度
return 0;
}端点能够配对时也不能跳过 k 循环，因为最优答案可能由两段合法序列拼起来；端点不能配对时，k 循环又会自然保留只出现在某个子区间中的答案。
min(左段 + 右段 + 整段代价)必须处理区间内全部石子；目标是最小值，所以非基础状态先初始化为正无穷。
max(中间 + 2, 左段 + 右段)可以跳过字符；目标是最大长度，所有状态从 0 开始就是合法的下界。
共同状态两个问题都用 dp[l][r] 描述一个连续区间，并依赖更短区间。共同顺序都按照 len 从小到大，再枚举 l 并计算 r。不同决策转移必须来自题目的“最后一步”，不能只看见区间就机械套模板。如果最终操作会把两段连续结果合在一起，尝试枚举 k；如果题目强调两端的选择、删除、配对或回文关系，尝试向 [l+1,r]、[l,r-1]、[l+1,r-1] 转移。有些题像括号序列一样，两类转移都需要。
dp[l][r] = INF先设为不可能的大值，再用每个合法候选不断取 min；基础状态单独赋值。
dp[l][r] = 0只有当“不选任何元素”是合法方案时，0 才能作为所有状态的初始下界。
dp[i][i] = ?把“只剩一个元素”代入定义：石子无需合并为 0，单括号无法配对也为 0。
dp[l][r]？r = l + len - 1？r ≤ n？l ≤ k < r？闭区间 [l,r] 的长度是 r - l + 1，所以 r = l + len - 1。分界成 [l,k] 和 [k+1,r] 时，k 必须严格小于 r。
状态dp[l][r] 表示什么？区间必须全部处理，还是允许选择子序列？
最小问题空区间、单点区间或长度为 2 时，答案能否直接确定？
最后一步最后是把两段合并、让两端配对，还是删除一个端点？
完整性枚举所有 k 或所有端点选择，是否覆盖每一种合法方案？
计算顺序当前状态依赖哪些更短区间？len 应该从几开始？
答案与复杂度最终读 dp[1][n] 还是其他区间？O(n³) 与 O(n²) 是否可接受？
如果每个询问彼此独立，可能更适合前缀和、线段树或双指针。只有当长区间答案会反复依赖较短区间，并且这些子问题可以复用时，区间 DP 才自然。
令 n = 5，按 len 从 1 到 5 写出全部区间，确认每个状态依赖的区间都更短。
目标：掌握边界不看完整代码，先写状态、初值和转移，再用 1 2 10 4 对照填表结果 33。
分别思考最长回文子序列与最长回文子串的状态，说明为什么转移和答案读取不同。
目标：避免机械套模板① dp[l][r] 的两个下标各表示什么？② 为什么必须从短区间到长区间？③ 石子合并为什么枚举的是最后一次分界？④ 括号题为什么既要看端点又要枚举 k？⑤ 求最小值和求最大值的初始化为什么不同？能独立说明，再开始刷题。
先定义连续区间状态，再从最小区间出发，用分界点或左右端点组合更短答案。以后先推导“最后一步”，再写 len、l、r、k 四个变量，代码就会从结论自然长出来。
将从图的存储和遍历开始，再逐步进入最短路、最小生成树、拓扑排序与连通性问题。
将介绍整除、最大公约数、质数筛法、快速幂、同余与组合计数等竞赛常用知识。
不同竞赛在参赛对象、比赛方式和题目难度上各有特点。了解它们不是为了盲目追逐奖项，而是为了给自己的学习找到一个清晰目标。
在有限时间里，将问题转化为算法，再写成正确、高效的程序。
赛事规则每年可能调整，正式报名和参赛资格请始终以当届官方通知为准。
全球高校程序设计竞赛。经典赛制是 3 名学生组成一队，共用一台计算机，在有限时间内解决多道算法题。
面向中国高校学生的高水平程序设计竞赛，强调算法设计、逻辑推理、编程实现和团队合作。
重点考查基础程序设计能力以及数据结构与算法应用能力。选手独立作答，同时通过团体成绩体现学校整体水平。
覆盖软件与电子等多个类别。软件赛中常见 C/C++ 程序设计方向，通常按照不同组别和阶段进行选拔。
由百度发起的程序设计赛事，重视基础算法、数据结构、编程实现以及分析和解决问题的能力。历史赛事多采用在线评测与逐轮晋级形式。
这两项赛事是大学算法竞赛中最具代表性的团队赛。下面用一场比赛从开始到结束的过程，把赛制讲清楚。
面向全球高校的多层级团队程序设计竞赛，强调算法能力、临场决策和三人协作。
三名队员会同时阅读题目，但只有一人能够操作电脑。有人负责推导算法，有人检查边界和样例，有人把已经确认的思路写成代码。角色不是固定职业，而会根据题目和队员特长不断切换。
队伍首先按照通过题目数量排名；解题数相同时，总用时更少的队伍靠前。每道通过题的用时从开赛时刻计算到首次通过，之前未通过的提交通常会增加罚时。
A 题在第 40 分钟通过，之前有 2 次错误提交：
40 + 2 × 20 = 80 分钟未解决的题目通常不计入总用时常见路径是先加入学校集训队，经过校内选拔后代表学校参加相应区域赛事，优秀队伍继续向更高阶段晋级。具体赛区划分、资格和晋级办法应查看当赛季官方规则。
面向中国高校学生的年度性高水平赛事，赛题风格和现场形式与 ICPC 团队赛高度相近。
CCPC 现场赛的典型规则是三名正式队员组成一队，由一名高校教师担任教练。比赛采用上机编程、机器实时评测和实时排名，队伍共同使用一台比赛机器。
总决赛规则示例中，比赛时长为 5 小时，题目通常为英文描述；通过一道题后，赛场会升起对应颜色的气球，这也是现场赛非常有辨识度的传统。
排名首先比较解题数量；数量相同时再比较总用时。每道已通过题目的用时，从比赛开始计算到首次正确提交，之前的错误提交会带来额外罚时。
两者都非常重视算法、数据结构、代码正确性和团队配合，也都常采用三人一机的现场赛形式。主要区别在于赛事组织体系和覆盖范围：ICPC 是国际赛事体系，CCPC 则重点服务中国高校程序设计竞赛。
备赛知识高度互通，因此高校集训队通常会用同一套训练体系准备两项赛事。
与三人共用一台电脑不同，选手独立操作和提交。题目通常具有明显梯度，既考查基础语法和读题速度，也逐步覆盖数据结构与算法。它适合用来检验一所学校不同水平选手的整体程序设计能力。
备赛重点：基础题正确率、分段得分、时间分配软件类竞赛包含 C/C++ 程序设计等方向，并根据参赛对象设置相应组别。相比团队现场赛，个人赛更直接地检验独立读题、实现和调试能力，常被初学者用作阶段性目标。
备赛重点：语法熟练度、模拟枚举、常用算法历史上的程序设计大赛采用在线评测，重点考查基础算法、数据结构和程序实现能力。它为学习者提供了不同于高校系列赛的题目风格；是否举办、参赛资格和晋级方式需要关注当年官方公告。
备赛重点：综合算法能力、代码速度、线上赛经验完成第一章，开启你的算法之旅
每一次回来，都算进步
完成更多题目，冲击排行榜
仅统计协会 OJ 中每道题的首次 AC
冲击历史总榜与周榜，稀有徽章还会解锁专属外观。
今日长缨在手，何时缚住苍龙？毛泽东《清平乐·六盘山》
心有山海，步履不停。
山高路远，见证每一步抵达。
历史总榜累计全部刷题积分，并每日记录前三名与连续占榜荣誉。
协会成员共享的模板、题解与学习笔记。
点击卡片前往原文阅读，新的分享会按发布时间排列。
校验并发布 Hydro 题目、配置积分与训练分类，查看学生最近的真实评测记录。