数据结构

在解决问题的时候，我们通常不是一下子把数据处理完，更多的时候需要先把它们放在一个容器里，等到一定的时刻再把它们拿出来。使用「数据结构」是一种「空间换时间」思想的体现，

时间复杂度与空间复杂度

g(N) 关于规模 N 的表达式

O(g(N)) 表达考虑最坏情况

时间复杂度的计算（估算）只有在输入规模特别大的时候才有意义。「输入规模特别大」往往是我们初学的时候不可感知的。大 𝑂表示法是一种事前估计法，得到一个函数表达式，它表示了：随着输入规模的扩大，程序的执行消耗会扩大的程度。这个程度不是直接从表达式上直接看出来的，需要在一个动态增加的过程中去理解程序的执行消耗会扩大的程度。

$y=\log_{10}{n}$ 这个函数的图形随着 𝑛的成倍增长，纵轴数值的增长较缓慢（这已经是一种很好的时间复杂度了），到了 100000这个数量级，函数值也才到 5，「二分查找」就具有这样的时间复杂度：随着输入数据规模的增加，函数的执行次数增长较缓慢

$y=1$ 的函数图像表示了程序的运行时间与输入数据的规模无关；

$y=\frac{1}{10000} n^{2}$ 随着的成倍增长，函数值也成比例地增长，这样的时间复杂度是性能相对较差的，这样的算法常常是「朴素解法」和「暴力解法」

在 50000 以后 $y=\frac{1}{10000} n^{2}$ 有着更高算法复杂度。

参考学习：力扣

其他知识补盲

三元运算符

意思是：

• 如果 条件表达式为真（即非 0），结果就是 表达式1；
• 否则，结果就是 表达式2。

它相当于一个简写版的 if...else...。

printf 控制小数输出

• %f：输出浮点数（float / double）
• %.n：表示保留 n 位小数，会四舍五入
• 输出宽度（可选）：%m.nf → 总宽度 m，小数 n

• 只显示指定的小数位（四舍五入）
• 不自动切换科学计数法
• 精确控制格式，非常适合输出表格或文件格式数据

cout 控制小数输出

例 1：默认行为（有效数字）

解释：默认模式下，setprecision 控制有效数字，而不是小数点后几位。

例 2：保留小数位数（配合 fixed）

解释：fixed 改变了 setprecision 的含义，使它控制“小数点后几位”。

例 3：科学计数法

例 4：组合使用

比较：printf vs. cout

ACM数据类型选择

一、整型类型选择

注意乘法溢出

如果题中：

• a、b 都 ≤ 10⁹
• 但出现 a * b 那么 a * b 可能达 10¹⁸，要 提前转 long long。

大整数取模

使用unsigned long long刚好多那一点就能确保long long数据能被取模了

二、浮点类型选择

浮点类型选取规则

浮点比较时不要用 ==，而是：

三、实际题目举例

四、__int128 的应用

当题中要求：

• 计算 a*b，而 a,b 都可能到 1e18；
• 或 (a*b)%mod 中 a*b 可能溢出 long long;

可以使用：

输出时要手动转换：

读入速度相关

快读板子

字符处理相关

字符与整数的相互转换

字符串输入相关语法

注意 cin 和 getline 混用问题

当用过 cin >> n; 之后，缓冲区里 还残留一个换行符 '\n'。 如果立刻用 getline(cin, s)，那它会把这个换行符当作空行。

所以需要：

C 风格输入输出（scanf / printf）

常见字符串处理操作