C++避坑小知识&&错题笔记

C++避坑小知识&&错题笔记

前言

我在参加算法竞赛和刷题时，记录和整理了一些C++避坑小知识和错题笔记，在这里分享给大家，希望对大家有帮助。：）
作者： Frank_Star

---

通用问题和常见错误:

1. 找错处的方法-对拍:
   比赛时，可以用暴力代码和优化的代码跑对拍。比赛结束后/刷题时，可以找一份AC代码跑对拍(随机数生成样例的程序，标程，自己的程序三个一起跑，进行debug)

2. 使用数组时，一般开在main()外面；如果开在main()里，最开始要初始化。
   多组样例时，记得初始化全局变量。比如各种全局数组，比如每次使用vector之前用clear()初始化，比如用来存图的g[]。

3. 注意区分 = (赋值)和 == (相等)!! 一般只有在if或while的小括号里面才用==，剩下的都是用=。不要用错!!

4. inf一定要设足够大!! long long可以开到1e18+10，int建议开到1e9+10(相加不爆int)

5. 读题要仔细，尤其是英语题面，要好好翻译，把题目读懂再做题

6. 注意区分整型的数字和字符串的数字!
   如 5=‘5’－‘0’

7. 记得开long long “十年OI一场空，不开long long见祖宗”
   注意运算顺序，避免爆long long。打表时，注意i也有可能爆long long。
   必要的时候可以开ull(unsigned long long)或者__int128
   更大的时候可以换python写或者写高精度。

8. 先考虑复杂度可以过，再考虑算法。(尤其是acm赛制)

9. 注意区分数字1、小写字母l(L)和大写字母I(i)

图论:

1. 图论题目一定要排除重边的情况!(用一个min(G[u][v],w)进行判断)

数论:

1. 欧拉降幂:
   指数取模的时候，指数部分一般要模mod-1。(而不是直接取模)
   参考文献：详解欧拉降幂

2. 快速幂求乘法逆元：
   d 的逆元相当于 pow(d,mod-2) // pow是快速幂
   参考文献：快速幂求逆元模板题

dp(动态规划):

1. 注意dp的转移，从前往后还是从后往前的效果不一样，要具体情况具体分析。

2. dp写滚动数组的时候，注意把每个要改偏移量的地方都改了。

浮点数:

1. 浮点数注意避免输出-0(特判成0就行)
2. 浮点数比较时，equal函数的使用。当equal(a*a,b) wa掉的时候，可以尝试使用equal(a,sqrt(b))(两者的精度有细微的差别，和出题人写法不同的时候可能会wa)。

RE(段错误/运行错误)解决:

1. 开数组时maxn不要开太大，二维数组一般不要超过5010。开太大会报运行错误(RE)或内存超限(MLE)。
2. 使用数组时要随时关注下标，不要越界。判断下标越界时要仔细。
3. 段错误可能是数组越界，检查数组是不是开小了。
4. 注意边界情况的特判(如答案为0，如第一次循环)
5. 使用双指针时注意控制一下边界，指向数组前确保下标在数组范围内，避免数组越界。

TLE(超时)解决(卡常技巧):

1. 计算时能用乘法就不要用加法，减少算法的时间复杂度。
2. 使用memset时只清空掉必要的部分，可以降低时间复杂度
3. 用register int替代int
4. O(3)优化：

#pragma GCC optimize(3)
1

5. 优化cin和cout（优化后不要混用cout和printf、puts等）：

ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
1

6. 快读和快写：

// 快读
int read(int &n){
	char ch=' '; int q=0,w=1;
	for(;(ch!='-')&&((ch<'0')||(ch>'9'));ch=getchar());
	if(ch=='-')w=-1,ch=getchar();
	for(;ch>='0'&&ch<='9';ch=getchar())q=q*10+ch-48;
	n=q*w; return n;
} 
ll read(ll &n){
	char ch=' '; ll q=0,w=1;
	for(;(ch!='-')&&((ch<'0')||(ch>'9'));ch=getchar());
	if(ch=='-')w=-1,ch=getchar();
	for(;ch>='0'&&ch<='9';ch=getchar())q=q*10+ch-48;
	n=q*w; return n;
}

// 快写
inline void write(ll x){
	if(x < 0){
		putchar('-'); x = -x;
	}
	if(x > 9){
		write(x/10);//上一位
	}
	putchar(x % 10 + '0');//取出来这一位然后putchar
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

7. unordered_map 和 map 都可以试一试，一般情况下unordered_map会更快($O(n)$复杂度)，不过有的时候特殊数据可以卡unordered_map

更多卡常技巧推荐阅读：浅论 OI 中的卡常技巧

输入输出:

1. cin可以设置取消兼容优化速度（参见上一条的第5点），但是优化后不要混用cout和printf、puts等。
2. 使用scanf时一定要记得取址符&
   但是printf一般不要加取址符(否则会输出变量地址)
   dev环境下，
   scanf输入double类型，无精度要求时用%lf
   printf输出double类型，有精度要求时用%f(如%.2f)
3. string头文件下的getline(cin,str);可以读取一行含空格的字符串

各oj相关:

1. 行末不要输出多余空格，某些oj行末输出空格会判wa(如浙工大oj)或者格式错误(如杭电oj)
2. poj不支持万能头
3. 据说hduOJ的long double只能用cout输出(不能用printf)
4. codeforces感觉没问题但是 wa样例1 的时候，可以换一个编译环境(如clang++17)试试。

编译环境相关:

1. dev新建源文件(ctrl+N)就能编译运行，不需要建整个项目。

2. 用dev c++时，文件名不要带空格。否则会被识别成空格前的那个文件。

3. 同一份代码在不同编译器下跑出来的结果可能是不一样的。(所以代码规范很重要)

某题:

1. (2023ICPC西安邀请赛) O(n)递推求1－n的逆元
   我们设f[i]表示i的逆元，
   则 f[i]=(-y/i*f[y%i])%y
   按照这个式子递推下去就可以得到1~n的逆元了。
   参考文献：线性O(n)求1~n逆元
   （虽然这道题当时被我们O(nlogn)+卡常卡过去了2333）

2. (蓝桥杯-k倍区间，acwing3574 乘积数量)
   巧妙利用组合数公式C(n，2)可以代替两层for循环，降低时间复杂度

3. (某年ICPC网络赛第一场i题) 不确定整数的个数时，可以尝试全部读进来再处理，避免行末脏空格。

小结

以上就是今天要讲的内容啦，谢谢你的阅读！

如果你觉得对你有帮助，可以点赞和关注支持一下博主，你的关注和支持就是我进步的动力~
也可以点个收藏，需要用的时候查阅本文即可！

后续我会继续分享一些有用的知识给大家哦~ 大家下期再见！：）