知识点文档

经典好书

6 comments

  • @ 2021-10-11 10:50:59

    文件输入输出

    文件输出输出是 NOI 系列赛事常见的一种输入输出模式,题目中会写明输入及输出的文件名。写代码时只需要正常完成后,在 main() 函数的开始加入两行语句即可。

    #include <cstdio>
    ...
    int main(){
        freopen("输入文件名", "r", stdin);
        freopen("输出文件名", "w", stdout);
        
        ......
    
        return 0;
    }
    

    调试时可以先把这两行注释掉,调试成功后提交前取消注释即可。

    如果使用 dev-cpp 等 IDE 编写代码,也可以在源代码文件相同的目录下,创建一个输入文件名的同名文件,用记事本打开后,写上样例输入,这样编译运行程序后,会自动创建一个输出文件名的文件,用记事本打开后就是你的程序的输出。

    • @ 2021-10-11 10:50:49

      时间复杂度与时间限制

      时间限制

      一般会在题目中给出,常见的限制有 1/2/5/20 秒(s),有的时候也会用毫秒(ms)的形式给出。我们一般会粗略估算计算机一秒钟可以执行 10810^8 级别左右的基础运算(加减乘除等)。

      假设一道题目时间限制为 1 秒,现在有两个算法都能实现这道题,根据题目输入的 nn 的不同:

      • 算法 1 要进行 n2n^2 次运算
      • 算法 2 要进行 10×n10\times n 次运算

      那么显然,当 n5000n\le 5000 时,两个算法都绰绰有余,而当 n106n\le 10^6 时,第一个算法就没法在时间限制内得到答案,评测结果就会是超出时间限制

      时间复杂度

      表示方法

      我们一般用时间复杂度这个概念来描述一个算法的耗时,这个概念详细定义比较复杂,可以简单理解为时间复杂度就是基础运算的规模,更准确的定义可以参照下面的扩展阅读部分。

      表示时间复杂度的渐进符号有多种:大 Θ\Theta、大 Ω\Omega、小 ω\omega、大 OO、小 oo 等等,各自有不同的规则。因为大写字母 OO 比较容易打字和书写,所以经常会杂糅这些概念,用大 OO 符号来描述算法的时间复杂度上限,通常只保留多项式的最高次项,并省略系数

      一些例子

      比如上述的算法 1 与算法 2,我们通常会用 O(n2)O(n^2)O(n)O(n) 来描述。

      再比如对于下述代码:

      cin >> n;
      for(int i = 1; i <= n; i++)
          cin >> a[i];
      sum = 0;
      for(int i = 1; i <= n; i++)
          for(int j = i; j <= n; j++)
              sum += a[i] * a[j];
      cout << sum;
      

      cin >> a[i]; 执行了 nn 次,sum += a[i] * a[j]; 执行了 n+(n1)++1=n×(n1)2n+(n-1)+\dots +1 = \frac{n\times(n-1)}{2},总的基础运算次数大概是 12n2+12n\frac{1}{2}n^2+\frac{1}{2}n 次,只保留最高次项并省略常数后就是 O(n2)O(n^2)

      有的时候某个算法在不同情况下时间复杂度不同,比如最坏情况下快速排序算法时间复杂度会很高,因此为了更准确的描述,我们会说快速排序算法的时间复杂度为:最坏情况下 O(n2)O(n^2),随机数据的一般情况下 O(nlogn)O(n\log n)

      logn\log{n} 表示对数,之所以不写底数,是因为我们可以轻松通过换根公式,加一个系数后把底数进行改变,所以 log10n\log_{10}{n}log2n\log_{2}{n}lnn\ln{n} 都可以视作 log2n\log_{2}{n},写作 logn\log{n}

      对数知识是数学中的难点,下面直接给出常见的 nn 对应的 log2n\log_{2}{n},也可以直接通过 <cmath> 库中的 log2() 函数得到。

      nn log2n\log_2{n}
      10001000 10\approx10
      50005000 12\approx12
      10410^4 13\approx13
      10610^6 20\approx20
      10710^7 23\approx23
      • sortO(nlogn)O(n\log{n})
      • lower_bound/upper_bound/binary_searchO(logn)O(\log{n})
      • priority_queue.push() O(logn)O(\log{n}).pop() O(logn)O(\log{n}).top()O(1)O(1)
      • 判断 nn 是否为质数
        • 2n12 \sim n-1 试除:O(n)O(n)
        • 2n2 \sim \sqrt{n} 试除:O(n)O(\sqrt{n})
        • 埃氏筛法:初始化 O(nloglogn)O(n\log{\log{n}}),初始化后每次查询 O(1)O(1)
        • 欧拉筛法/线性筛法:初始化 O(n)O(n),初始化后每次查询 O(1)O(1)
      • 搜索枚举 nn 个数的子集:O(2n)O(2^n)
      • 搜索枚举 nn 的排列:O(n!)O(n!)

      常见时间复杂度能处理的数据规模

      时间复杂度 1 秒时限下能处理的数据规模
      O(1)O(1) \infty
      O(n)O(n) 10710^7(注意输入输出的耗时)
      O(n2)O(n^2) 50005000
      O(n3)O(n^3) 200200
      O(2n)O(2^n) 2020
      O(n!)O(n!) 1111
      O(n)O(\sqrt{n}) 101510^{15}(注意使用合适的数据类型)
      O(nlogn)O(n\log{n}) 2×1062\times 10^{6}

      以上描述的都是常见的保险的数据范围,有时也可以通过题目的部分分数据范围反向推测可能用到的算法。

      扩展阅读

      • @ 2024-1-27 21:16:49

        Thank you very much!

        好东西啊!!!!!

    • @ 2021-10-11 10:50:25

      基础数据类型的大小

      常见数据类型

      数据类型名 内容(一般情况) 占用内存大小 能储存的范围 scanf/printf 标识符(g++)
      int/signed 32 位整数 4 Bytes 2312311-2^{31}\sim 2^{31}-1
      2×1092×109-2\times 10^9\sim 2\times 10^9
      %d/%d
      long long 64 位整数 8 Bytes 2632631-2^{63}\sim 2^{63}-1
      9×10189×1018-9\times 10^{18}\sim 9\times 10^{18}
      %lld/%lld
      char 字符 1 Byte 至少能储存 01270\sim 127
      常见范围为 128127-128\sim 127
      %c/%c
      float 单精度浮点数 4 Bytes 3.4×10383.4×1038-3.4\times 10^{38}\sim 3.4\times 10^{38}
      有效数字 676\sim 7
      %f/%f
      double 双精度浮点数 8 Bytes 1.7×103081.7×10308-1.7\times 10^{308}\sim 1.7\times 10^{308}
      有效数字 151615\sim 16 位$
      %lf/%f

      无符号整型

      数据类型名 内容(一般情况) 占用内存大小 能储存的范围 scanf/printf 标识符(g++)
      unsigned int 无符号 32 位整数 4 Bytes 023210 \sim 2^{32}-1
      04×1090 \sim 4\times 10^9
      %u/%u
      unsigned long long 无符号 64 位整数 8 Bytes 026410 \sim 2^{64}-1
      01.8×10190 \sim 1.8\times 10^{19}
      %llu/%llu

      数组占用内存计算

      数组占用内存 = 数组长度 * 单个元素占用内存

      内存单位换算:

      • 1 Byte = 8 bits
      • 1 KiB = 1024 Bytes
      • 1 MiB = 1024 KiB
      • 1 GiB = 1024 MiB
      • 1 TiB = 1024 GiB
      • 1 PiB = 1024 TiB

      例子:

      • int a[1000000]4×10000001024×1024MiB4MiB\frac{4\times 1000000}{1024\times 1024} \text{MiB}\approx 4 \text{MiB}
      • int a[60000000]4×6×1071024×1024MiB228MiB\frac{4\times 6\times 10^7}{1024\times 1024} \text{MiB}\approx 228 \text{MiB}
      • char a[60000000]1×6×1071024×1024MiB57MiB\frac{1\times 6\times 10^7}{1024\times 1024} \text{MiB}\approx 57 \text{MiB}
      • long long a[60000000]8×6×1071024×1024MiB457MiB\frac{8\times 6\times 10^7}{1024\times 1024} \text{MiB}\approx 457 \text{MiB}
      • @ 2021-10-11 10:49:59

        结果对 x 取余

        很多题目会有:结果对 100007100007 取余,结果对 109+710^9+7 取余,之类的要求。一般都是因为结果可能是一个很大的数,超过了 long long 的范围,要得到精确的值需要使用高精度计算的算法。为了避免高精度计算带来的时间复杂度和冗长的代码,出题人便要求结果对某个值取余,取余后的结果一致就认为算法正确。

        例题 1

        题面

        输出 21002^{100},结果对 109+710^9+7 取余。

        常见错解

        ...
          int ans = 1;
          for(int i = 1; i <= 100; i++)
            ans *= 2;
          cout << ans % 1000000007 << '\n';
        ...
        

        这个做法虽然结果确实取余了,但是在中途计算时就会超过 int 的上限,做完循环后并不是准确的结果,最后再取余必然也不是正确的结果。

        正解

        ...
          int ans = 1;
          for(int i = 1; i <= 100; i++)
            ans = (ans * 2) % 1000000007;
          cout << ans << '\n';
        ...
        

        取余运算规则

        • (a * b * c) % x 等价于 (((a % x) * b) % x) * c) % x
        • (a + b + c) % x 等价于 (((a % x) + b) % x) + c) % x
        • (a - b) % x 等价于 (a % x - b % x + x) % x
        • (a / b) % x 等价于 (a % x) * (b 的乘法逆元) % x

        简单来说,如果要求结果对 x 取余,只需要主要三点:

        • 每次加法与乘法后都要立马做一次取余
        • 减法的结果如果是负数,需要通过 +x 变成正数后取余。
        • 除法运算需要使用乘法逆元进行处理。(一般只有提高组会遇到)

        避免除法取余

        普及组阶段常见的涉及到除法的一般只有排列组合数:

        • A52=5!2!=5×4×3×2×12×1A_5^2 = \frac{5!}{2!} = \frac{5\times 4\times 3\times 2\times 1}{2\times 1}:提前考虑约分,Axy=x×(x1)××(y+1)A_x^y = x\times (x-1) \times \dots \times (y+1)
        • C52=5!2!(52)!=5×4×3×2×1(2×1)×(3×2×1)C_5^2 = \frac{5!}{2!(5-2)!} = \frac{5\times 4\times 3\times 2\times 1}{(2\times 1)\times (3\times 2\times 1)}:使用杨辉三角优化,杨辉三角的计算只需要用加法。

        杨辉三角对应的组合数:

        C00C10,C11C20,C21,C22C30,C31,C32,C33C40,C41,C42,C43,C44C_0^0\\ C_1^0, C_1^1\\ C_2^0, C_2^1, C_2^2\\ C_3^0, C_3^1, C_3^2, C_3^3\\ C_4^0, C_4^1, C_4^2, C_4^3, C_4^4\\

        • @ 2021-10-11 10:49:37

          保留 x 位小数

          方法 1

          • 头文件:#include <cstdio>
          • 语句: printf("%.xf", a);

          方法 2

          • 头文件:#include<iostream>#include<iomanip>
          • 语句:cout << fixed << setprecision(x) << a;

          注意

          如果题目说保留 xx 位小数,那么就按照这种方式输出就可以了。

          但是需要注意的是,这种方式并不是我们直观中的四舍五入。

          对于 44 舍和 66 入的部分是没有问题的,对于舍入位是 55,且后面还有大于 00 的数位时也是没有问题的。但如果舍入位是 55 且后没有其他数了,那么有可能会有两个小问题。

          如果是 double 类型可以精确储存的数,那么会舍入到最接近的偶数数位,比如在保留 00 位小数的情况下:

          • 0.50.5 -> 00
          • 1.51.5 -> 22
          • 2.52.5 -> 22
          • 3.53.5 -> 44

          保留 22 位小数的情况下:

          • 1.1251.125 -> 1.121.12
          • 1.3751.375 -> 1.381.38

          如果是 double 类型无法无法精确储存的数,实际上储存的数可能会有一点点偏差,也会造成和我们所想不同。
          比如如果输入 1.1151.115,那么保留 22 位小数输出的会是 1.111.11,因为保留 2020 位小数输出后,我们会发现实际储存的数大概是 1.114999999999999991121.11499999999999999112,执行的自然是 44 舍操作。

          • @ 2021-10-11 10:49:20

            输入输出加速

            直接使用 cin/cout 进行输入输出时会比较慢,数据量较大时会比较耗时。因此在输入输出数据量特别大时,很多题目需要用更快的输入输出方式。

            方法 1

            头文件加入 #include <cstdio>,然后仅使用 scanfprintf 进行输入输出。

            方法 2

            main() 函数的开始加入两行代码。这两行代码可以关闭输入输出流同步,解除 cincout 绑定。

            ...
            int main(){
                ios::sync_with_stdio(false);
                cin.tie(0);
                ...
            }
            

            然后仅使用cincout进行输入输出,且所有换行使用 '\n' ,不使用 endl 即可。

            如果再搭配上文件输入输出,则 main() 函数的开始可以这样写:

            ...
            int main(){
                freopen("输入文件名", "r", stdin);
                freopen("输出文件名", "w", stdout);
                ios::sync_with_stdio(false);
                cin.tie(0);
                ...
            }
            

            方法 3

            使用 getchar() 自行解析,俗称快读,时间效率与方法 2 类似,不展开说明。

            • 1