数据结构

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

时间复杂度与空间复杂度

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}$ 有着更高算法复杂度。

参考学习：力扣

其他知识补盲

三元运算符

条件表达式 ? 表达式1 : 表达式2

意思是：

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

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

printf 控制小数输出

printf("%.nf", x);

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

double x = 3.14159;
printf("%.2f\n", x);  // 输出：3.14
printf("%.3f\n", x);  // 输出：3.142
printf("%8.2f\n", x); // 输出：   3.14 （总宽8位，右对齐）

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

cout 控制小数输出

#include <iomanip>

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

double x = 3.14159;
cout << setprecision(3) << x;  // 输出：3.14（有效数字3位）

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

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

cout << fixed << setprecision(3) << x;  // 输出：3.142

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

例 3：科学计数法

cout << scientific << setprecision(2) << x;
// 输出：3.14e+00

例 4：组合使用

cout << setw(8) << setfill('*') << fixed << setprecision(2) << x;
// 输出：***3.14

比较：printf vs. cout

ACM数据类型选择

一、整型类型选择

注意乘法溢出

如果题中：

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

大整数取模

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

二、浮点类型选择

浮点类型选取规则

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

if (fabs(a - b) < 1e-9)

三、实际题目举例

四、__int128 的应用

当题中要求：

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

可以使用：

__int128 mul(__int128 a, __int128 b, long long mod) {
    return (a * b) % mod;
}

输出时要手动转换：

void print(__int128 x) {
    if (x == 0) return;
    print(x / 10);
    putchar(x % 10 + '0');
}

读入速度相关

快读板子

#define rd read()
inline long long read()
{
    long long x = 0, y = 1;
    char c = getchar();
    while (c > '9' || c < '0')
    {
        if (c == '-')
            y = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9')
        x = x * 10 + c - '0', c = getchar();
    return x * y;
}

//使用long long n = rd;

字符处理相关

字符与整数的相互转换

string s = "abc";
int num[26] = {0};
for (char c : s)
    num[c - 'a']++; // 统计字母出现次数
int cnt[256] = {0};
for (unsigned char c : s)
    cnt[c]++; // 统计所有 ASCII 字符出现次数

字符串输入相关语法

注意 cin 和 getline 混用问题

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

所以需要：

cin >> n;
getchar(); // 或 cin.ignore();
getline(cin, s); // 现在才能正确读入整行

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

常见字符串处理操作