一些卖淫卡常技巧

· 2024-06-19 · # 笔记

在数学和物理里，常数是指在一定语境下不变的量。万有引力常数（记作G）是一个包含在对有质量的物体间的万有引力的计算中的实验物理常数。而在我们数学课堂上讲多项式的时候，一般情况下一个项的系数（或零次项）就是常数。

而在评价一个算法好坏时，通常用其大 $O$ 来衡量其上界。有一种算法的时间复杂度是另一种的大 $Θ$ ，但是其在具体实现时可能稍慢于另一种。而在 $n \to \infty$ 时，其他的项都很小可以忽略不计，两者之间只有常数差距。

在 OI 中，常数是指用渐进学算出来一样的情况下，用来衡量一个算法速度快慢的概念。由此看来，我们口中的常数是个相对的概念。我们只会说这种算法的常数小于另外一种，也不会像数学里那样具体求出这个数的值。

数据范围较大时，快速读入一个十进制整数是个令人抓耳挠腮的问题。就比如使用下面的代码输入 $10^6$ 的整数个时，我们很有可能会出现 TLE。

int main(){
    std::cin>>n;
    for(int i=1;i<=n;i++) std::cin>>a[i];
    return 0;
}

我们平常用 std::cin 时，会发现非常慢，比几乎所有 C 元老都慢。因为有很多码农喜欢把 cin、cout 和 scanf、printf 一起混用，所以人们将流与 stdio 捆绑在了一起缓存用了很多时间。

所以我们可以使用 ios::sync_with_stdio(false) 让 cin 与 printf 使用不同的缓冲区，也就是让两者使用不同的缓冲区。但是这样后 cin 和 cout 还是默认被绑定的，cout 在每次输入前要 flush（同步 streambuf 和 cout 记住的输出）。cin.tie(nullptr) 可以关闭这个特性，再一次提速。同理，把 endl 替换为 \n 也能通过减少 flush 加速。

通过会议中考题目 $\overline{abc}=100a+10b+c$ ，而 getchar() 是从 stdin 读取下一个字符（也就是从左往右看你的输入）。所以每当读入下一个字符就要执行一遍类似于秦九韶算法的过程，即 $a=10a+c-48$ 。在读入这个数之前，可能有一些别的符号。有些数前面有负号，因此
要跳过除了负号以外的字符，在有负号时做好判断即可。

经测试把 isdigit 拆成两个比较会变快。
你可以把 c-48 换成 c&15。
但是不要把 10a 换成 (a<<3)+(a<<1) ，因为编译器会自动优化。
如果题目的数据范围是非负整数的话，可以去掉读入非字符时判断之前的符号的代码。

我们一般使用 getchar() 读入一个字符。有没有更快的方法？

fread() 可以一次读入 SIZE 个字符到缓冲数组内，用法：fread(ibuf,1,SIZE,stdin)。
读入时遇到 EOF 或读完才会执行后续代码。
可以用这个方法直接代替：

#define getchar() (p1==p2&&(p2=(p1=inf)+fread(ibuf,1,1<<15,stdin),p1==p2)?EOF:*p1++)
char ibuf[1<<15],*p1,*p2;

我们的 putchar() 是只能一个一个地输出，而 printf 可输整数但很慢。可把原数拆成十进制位，再从高到低依次输出。优化方式同快读，不过这样做还是较慢，甚至有时比 printf 还慢。同快读，可以用 fwrite 优化，好像用 puts() 或者 fputs() 也较快。

streambuf 就是 cin 、cout 内部那个缓冲区。快读前加上 static streambuf*isbuf = cin.rdbuf()，快写类似。fread(ibuf,1,SIZE,stdin) 变成 isbuf->sgetn(ibuf, SIZE)。putchar(C) 变成 osbuf->sputc(C)，其他写法和 fread/fwrite 光速 IO 写法一样。

用了 fwrite 等不要在程序结束前 fclose(stdout)。

取消同步后千万不要混用 C 和 C++ 输入和输出，也不要先写取消同步再 freopen。
最好也不要混用 scanf。
在输入输出交互题里面，用了 cin.tie(nullptr) 你需要手动 flush。
在使用 fread 系列 /streambuf 时,你需要多按几下 ctrl+z，而且有的机器不支持控制台
输入。
写文件快输要考虑到 $0$ 和 INT_MIN。
注意快读会从 stdin 中抽掉数字后的一个字符，所以读入一些像 2+3i 之类的只能特判。

有符号类型的整数的范围是 $[−2^{\text{位数}−1}, 2^{位数−1}−1]$ 。而我们在读入一个整数时，是先记录前面有没有负号，再计算其绝对值的，这样就会导致他们在读入 $−2^{\text{位数−1}}$ 时，会导致其绝对值溢出。而有符号数的溢出是未定义的，在正式比赛时用了可能造成意想不到的后果，可以通过特判负号或开 unsigned 来解决这个问题。

当你定义一个整型变量时：

如果它是有符号的的话，会留出一位作为符号位，但有些时候我们只有非负值。
并且，使用无符号类型比有符号类型更快。
因此，我们可以使用无符号整数。

一般情况下，位运算很快，因为是计算机所擅长的。加法很快，乘法较快，除法和取模一般较慢，因此在保证不溢出的情况下尽量少用取模。因为运算结果的范围，加减法的取模可以判断是否在 $[0,\text{模数})$ 之中，若出范围则进行加减调整。&& 和 || 是短路运算符（如果左值已经可以确定表达式的值就不用计算右值），而 &、| 不是。

不过，编译器不是蒟蒻，它也会自己优化你写的代码。比如，在你打出 n<<1、n*2 时，编译器可能会自动帮你优化成一样的。因此，写 n*10（快读）时不需要画蛇添足地写成 (n<<3)+(n<<1)。对于大多数整数运算，即使不开 O2 优化编译器也会给你优化，比如 /2。但是浮点数不一样，如 /2 最好写成 *0.5。不过，当运算符两端都是变量时，编译器一般会不知所。

永远不要用 bool！！！状压时我们经常用整数来与集合在一定范围内一一映射，因为方便用数组下标访问。但这样没有充分利用每一位，bitset 可以把 $8$ 二进制位的信息压进一个字节里，还支持位运，因此其常数极小（约为 $1$ /整型位数）。

将一个循环中的语句展开成多条，提高代码的并行性，其原理是 CPU的乱序执行。注意各平行语句不能互相影响，否则虽然会快一点，但是没有真正展开那么快。一般来讲循环展开6~8层效果最佳，否则会让寄存器溢出，但是循环展开的缺陷就在于破坏了代码结构。

举一个例子：

#include<iostream>
int n,ans;
int main(){
	std::cin>>n;
    for(int i=1;i<=n;i++){
    	ans+=i;
	}
	std::cout<<ans<<'\n';
    return 0;
}

在展开时候就是这样的：

#include<iostream>
int n,ans;
int main(){
	std::cin>>n;
    for(int i=1;i<=n;i+=4){
    	ans+=i;
    	if(i+1<=n) ans+=i+1;
    	if(i+2<=n) ans+=i+2;
    	if(i+3<=n) ans+=i+3;
	}
	std::cout<<ans<<'\n';
    return 0;
}

缓存存了下一级存储器的部分内容。我们要提高其命中（在这一级缓存内能找到）率，因为许多码农的程序都喜欢访问已访问位置附近的值。因此，存储器更乐意服务有时间局部性、空间局部性的访问。所以，我们访问数组尽量使得步⻓为 $\dfrac{1}{\text{先枚举的较大维度}}$ 、尽可能多地开能挤得进的数组（有时间局部性），就可以让卡进一级缓存。

然而，内存并不会随机化，它是根据内存的后几位确定编号的。所以，我们要避免使⽤步⻓为较⼤的 $2$ 的幂的访问模式，否则容易引起缓存冲突。在状态压缩动态规划、使⽤⾼维数组时很重要解决⽅法：把数组稍
微开⼤⼀些。

递归要存储当前状态，因此就要花很长时间，而且可能莫名因爆栈而运行错误。如果要用，尽量不要传太多参，用全局变量。

关于一些其他的情况，register 和 inline 就不要使用了，因为新版会被编译器忽略。听说三目运算符、switch case 比 if else 分支快，但好像有的编译器会把~~二郎神~~三目运算符和 if else 优化成一样的。

一般为了方便，常用快速幂来求逆元。然而因为指数常为 $998244353$ ，其满足 $199\times 2^{23}+1$ 的形式，因此 $998244351$ 二进制表示低位很多 $1$ ，意味着需要乘很多次。可以换用扩欧（一般跑不满，但用斐波那契数列相邻两项作为 $a,b$ 能卡满，不过一般情况下模数不会是斐波那契数列的一项（ $233$ 等例外））。

$C_{i,j}=\sum_{k=1}^m A_{i,k}\times B_{k,j}$ 。按我们平常的思维，显然会枚举矩阵 $C$ 的每一个 $i,j$ 的位置，再枚举 $k$ 。可是我们这样的话，对矩阵 $B$ （二位数组）的空间访问就不连续。我们可以用一次枚举 $i,k,j$ ，这样每个矩阵都可以利用空间访问的局部性。

前置的 ++ 即先 +1，在返回值，后置的 ++ 即变量 +1 但返回原来的值（-- 同理）。因此，如果使用后置 ++，每次都要储存之前的值再返回。所以，我们就可以用前置的 ++，加快访问的速度。然而，有的时候如果没有用返回值时，整型变量会被编译器直接给你优化成一样的。但是，stl 里面容器的迭代器不是编译器内置的，因此后置 ++ 还是会计算出一个返回值（即使不必要），所以前置 ++ 优化得很大。

关于 SPFA，他（避讳）了。不过，你如果不担心你写哈希被卡的话，你也可以写 SPFA。可以加些优化，如酸辣粉（SLF）优化（如果新点距离小于队头距离就插入队首，否则插入队尾）等等。注意：如果不是队列或者dijkstra那种一出队就决定的话可以把时间复杂度卡成指数。不过，判负环、差分约束时应该没人敢卡。SPFA 判负环时可以记录每个点的入队次数或最短路的边数来加快判负环的速度；也可以把 SPFA 的队列换成栈等等。