刷题小贴士

📚 目的：写题、锻炼思想、提高把想法转换成代码的速度、多掌握技巧。 三篇小帖合成一篇：常用工具、提速技巧、撸码习惯、实战小技巧，外加 memset 与无穷大两个专题。

工具

算法图解（可视化）：https://algorithm-visualizer.org/
算法书及代码：https://www.hello-algo.com/
绘图工具：https://excalidraw.com/

提运行速度

scanf / printf

输入输出方面 scanf/printf 要比 cin/cout 快很多，建议用 scanf/printf。ios::sync_with_stdio(false); cin.tie(0); 可以使 cin 变快——scanf 比 cin 快 10 倍，比优化后的 cin 快一点点。

输入大于 \(10^5\) 一定用 s/p，小于的话无所谓。 但 cin/cout 比较方便，所以我一般是用关流的 cin/cout，只有要求格式化输入输出时才用 scanf/printf。

#define

endl 很浪费时间，用 #define 把 '\n' 替换 endl：

#define endl '\n'

提撸码速度

巧用 typedef

一些 for 循环很长又经常要用，可以使用宏替换（见到大佬用了，但是目前还没意识到有多好，以后再看吧）。long long 这种也可以使用 typedef 去改别名为 LL 节省时间；pair<int,int> typedef 成 PII。

万能头文件

#include <bits/stdc++.h>——其实算是个坏习惯，到时候单词都记不到，对以后写工程不利。但算法方面，咱能参加的比赛基本上是允许万能头的，确实省时间。

小技巧

用字符串数组读入单字符

读入一个字符时，最好使用 op[2] 配 scanf("%s", op)。%c 的话会读入一些奇怪字符导致结果错误，而用字符串的形式则可以减少很多细节上的没必要的点（有些数据会加额外的空格埋坑，使用 %s 读入就能解决这个问题）。

0x3f3f3f3f 无穷大

用 0x3f3f3f3f 表示无穷大，用 memset 给容器各值初始化为无穷大（原理见下文 memset 专题）。

对于 int 的数组 a，如果只要用 n 个数，可以只初始化前（n+1）个数：memset(a, 0, (n+1)*4)。

输出过多时如何查看

终端不会显示全部的输出（当输出过多时），可以用下列命令将输出放入 txt 文件进行检查：

C:\code\c++\lanqiao>7th.exe > output.txt

2-Learning/02-算法/01-入门与备赛/assets/image-e7ce63c5

思路技巧

平均数技巧

对于平均数的题，如果有个原数组，可以把里面每个元素都减去平均数，之后构得的新数组更方便计算。

向下取整

用 int()。

整除性质

看数据范围定算法

等各种算法熟练后，看题先看数据范围——相当于是一个提示。根据数据范围推出可用的算法，再看题干大概是什么题，就基本能锁定一题的做法了。这个东西一定要背下来，一开始不熟练可以先对表找（表见 03-时空复杂度）：

memset 专题

按字节赋值：void memset(void *str, int ch, size_t n)——将 str 中当前位置后面的 n 个字节用 ch 替换。也就是说这个函数的作用是将数字以单个字节逐个拷贝的方式放到指定的内存中。

memset(a, 127, sizeof(a))：127 的二进制是 01111111，数组里存的就是四个 01111111，十进制是 2139062143（小于 int 范围）
128 的二进制是 10000000，四个 10000000 就是 -2139062144，即初始化为一个很小的数
memset 是按字节赋值的，因此 char 类型的数组可以赋任意值；正规用法是初始化 char 数组，只接受 0x00-0xFF
0 的二进制是 32 个 0，-1 的二进制是 32 个 1，所以 memset 可以直接初始化 0 和 -1
要初始最大化：第一位符号位 0、剩下为 1，01111111 化十六进制正好为 0x7f，即 memset(arr, 0x7f, sizeof(arr))。但这个数不满足"无穷大加无穷大依然是无穷大"的性质，相加后会变成很小的负数

所以一般无穷大常量取 0x3f3f3f3f：

十进制 1061109567，是 \(10^9\) 级别
0x3f3f3f3f + 0x3f3f3f3f = 2122219134，没超 32 位 int 范围，相加仍满足"无穷大加无穷大还是无穷大"
每个字节都是 0x3f，memset(arr, 0x3f, sizeof(arr)) 即可整段置为无穷大

其他 memset 赋值参考：

memset(arr, 0x80, sizeof(arr)); // set int to -2139062144
memset(arr, 0x7F, sizeof(arr)); // set double to 1.38242e+306
memset(arr, 0xFE, sizeof(arr)); // set double to -5.31401e+303

无穷大专题

在算法竞赛中，常常需要用一个常量代表"无穷大"。比如对 int 来说，有人用 INT_MAX（0x7fffffff），但以 INT_MAX 为无穷大常常面临一个问题：加一个其他的数会溢出——这种情况在动态规划或其他递推算法中常常出现，很可能导致算法出问题。

所以竞赛中常采用 0x3f3f3f3f，它主要有如下好处：

十进制为 1061109567，和 INT_MAX 一个数量级（\(10^9\)），而一般场合下的数据都小于 \(10^9\)
0x3f3f3f3f × 2 = 2122219134，无穷大相加依然不会溢出
可以用 memset(array, 0x3f, sizeof(array)) 直接设初值，因为这个数每个字节都是 0x3f

⬅️ 03-时空复杂度 🏠 00-算法 ➡️ 00-听课板子

04-刷题小贴士