[CSP冲刺]代码常见错误总结_csp next,max,min等 可能出错的变量名

CSP快要来了…总结一些常见错误
事实上这个博客在2020年也在不断的完善。

---

1 常见暴毙错误

• 开 O2 时写没有返回值的非 void 函数，直接 RE 暴毙。
• long long ans=1;printf("%d",ans); 类型不一致在 Linux 环境下直接暴毙。(可以尝试使用输出优化解决这个问题)
• 写带下划线开头的函数，如：__gcd(a,b)。
• 开 $10^6$ 个空的 set\map ，MLE/TLE。
• 以为某次计算不用取模结果直接溢出暴毙；忽视了循环变量/函数传参变量/pair内部包含的两个变量等变量是否需要开 long long 的问题。
• 交题之前没有检查数组空间大小，RE 。常见检查对象：与边数有关的数组（注意前向星要开两倍）；tire树，线段树等空间复杂度为 $O(n\log n)$ 的数组；高维dp数组是否存在范围开反的情况等等。
• 读题不仔细，爆零两行泪。
• 多组数据，一要注意每个有改变的数组都已经清空，二要注意多组数组用 memset 的时候一定要谨慎。
• freopen 不仔细检查，直接暴毙。
• 动态规划/递推时访问 -1 下标元素——这个看人品，有时候不会WA，有时候可以逃过一劫。
• 常见不加会暴毙的头文件：

#include<cstdio>
#include<cmath>
#include<algorithm>
#include<vector>
#include<cstring>
1
2
3
4
5

• 常见C++关键字：

hash,time,next,x0,y0,x1,y1,...
1

• 必杀技：文件没有保存在指定的位置。（相信大家都知道具体的例子是什么…）
• [UPD 2020.11.06] 数数题用错模数，直接爆零退役。

---

2 有关 long long/取模 运算的建议

打完代码一定要考虑long long问题，该开的一定要开!

取模

取模三件套

int add(int a,int b){
	return (a+b)%MOD;
}
int mul(int a,int b){
	return 1LL*a*b%MOD;
}
int sub(int a,int b){
	return (a-b+MOD)%MOD;
}
1
2
3
4
5
6
7
8
9

快速乘

LL mul(LL x,LL y,LL MOD){
    LL res=(x*y-(LL)((double)x*y/MOD+0.1)*MOD)%MOD;
    if(res<0)res+=MOD;
    return res;
}
1
2
3
4
5

long long

#define int_ long long
1

很浪费空间\时间，不建议…
最好的方法就是不断提醒自己标注数据范围，相关变量是否都开上 long long。

---

3 空间消耗问题

老问题…空间限制也是OI中不可忽视的部分…毕竟一挂就是直接爆零…
$10^8$的总空间就已经很紧张了（256MB）。例如，$n\le 10^6$是就不能够将trie树开成$26\times 10^6$了…
当然…要注意数据范围…不要老是开long long…

---

4 栈空间问题

关于爆栈:
两种情况，递归层数太多(RE)，递归时传了一个数组[还包括STL(set,bitset,map…)]（RE或MLE）
解决方案:

5A

测大样例时-O2 -Wl,--stack=2000000000（我记得有一次模拟赛我为了测大样例调了1h30min…）

5B

评测时加上inline，效果显著:)

---

5 重载运算符的运用

bool operator <(const state &b)const{//STL习惯用<符号
	return step>b.step;
}
1
2
3

听说这东西有些常见 bug，之后记录一下。

---

6 STL

用STL的时候要小心边界，很容易崩溃

6.1 set/multiset

s.lower_bound(val)——寻找第一个大于等于$val$的$s$中的元素（被坑过两次，一次是某次Atcoder 还有一次是NOIP 开车旅行）
s.upper_bound(val)——set用这东西好像没用
s.find(val)——找到当前$=val$的迭代器。
s.erase(*it)——一定注意里面是迭代器，如果要删val的话需要先s.find(val)。
s.count(val)——multiset才用的着，元素中$=val$的个数。

6.2 string

C++的string真的很好用…虽然很慢…但在模拟题中是很实用的(CSP能用)。
s.substr(l,len)取以l开始的后面len个字符，len如果省去的话就默认直到结尾。
s.substr(l,len)删除l开始的后面len个字符，len如果省去的话就默认直到结尾，与上一个(大概是)反函数。
s.find(string)找string是否存在,存在返回第一个出现的第一个字符所在位置，否则返回string::npos。

6.3 vector

不建议用…因为有些操作是可以被卡到$O(n)$的。
G.resize(siz)预留siz的空间，[siz,end)的全部删掉。

6.4 bitset

S.set(idx,val)将idx位置置为val，val省略是默认为1。
S.count()数bitset中1的个数。
S.size()bitset的大小。
S.test(idx)查询当前下标是否为1。
S.any()查询bitset中是否有1。
S.all()查询bitset中是否全部都是1。
eg.biset Floyd 闭包

for(register int i=1;i<=n;i++)//相当于之前的k，要放在外面
        for(register int j=1;j<=n;j++)
        if(d[j][i])d[j]|=d[i];
1
2
3

6.5 常见 STL

lower_bound
upper_bound
stable_sort
next_permutation

6 CE/文件操作相关

众所周知CE和MLE是OI中最可怕的两种错误
注意一些变量名在NOI Linux下是禁用的!
最可怕的就是x1,y1这种东西…还有一些常见的英文单词，因此拼写的时候尽量在英文单词中删几个字母（不过像slove这样的单词就没必要了，今年我还是别用process了）。

#include<cstdio>
#include<iostream>
1
2

头文件一定要加!虽然可能能够通过编译!
还有要注意莫名其妙的多余隐藏字符（当然这个比较玄学）。
freopen("road.in","r",stdin);
freopen("road.out","w",stdout);
必须一个单词不多不少!空格也不行!!

7 对拍相关

考试的时候肯定是首先测大样例，输出多的时候要用fc A.out B.out。
然后自己出几组小数据，如果行的话构造一些大数据。
如果考试时间十分充足，一定要进行对拍
以下是对拍的程序:

#include<iostream>
#include<windows.h>
using namespace std;
int main()
{
    int testdata=100;
    while(1)
    {
        testdata--;
        system("makedata_plus.exe %random% > data.in");//%random%是随机参数，可加可不加
        system("cheat.exe < data.in > cheat.out");//< 就是读入 > 就是输出
        system("bf.exe < data.in > bf.out");
        if(system("fc cheat.out bf.out"))break;
    }
    if(testdata==0) cout<<"no error"<<endl;
    else cout<<"error"<<endl;
    system("pause");
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

随机生成数据(仅供参考):

#include <bits/stdc++.h>
#define LL long long
#define MAXN 200000
#define RANGE 100000
using namespace std;
stringstream ss;

int n,fa[MAXN+5],p[MAXN+5];
int get_num(){
	return 1LL*rand()*rand()%(RANGE*2)-RANGE;
}
int xfind(int x){
	return (fa[x]==x)?x:fa[x]=xfind(fa[x]);
}
int main(int argc, char *argv[])
{
	int i=10,kd=0;
	if(argc){
		ss.clear();
        ss<<argv[1];
        ss>>i;
		//kd=(i/20)%2;
		i%=20;
	}
	int data[21][3]={
		{1,1,1},
		{10,2,6},
		{17,4,10},
		{35,5,8},
		{70,3,14},
		{200,5,18},
		{200,6,37},
		{500,20,868},
		{500,20,742},
		{1000,100,998},
		{1000,100,997},
		{1000,99,996},
		{1000,99,995},
		{1000,100,994},
		{1000,100,993},
		{1000,99,992},
		{1000,99,991},
		{1000,100,990},
		{1000,100,989},
		{1000,99,988},
		{1000,99,987}};
	static char buf[1000];
	srand(time(NULL));
	n=data[i][0];
	printf("%d\n",n);
	p[1]=1;
	for(int j=2;j<=n;j++)
	fa[j]=1LL*rand()*rand()%(j-1)+1,p[j]=j;
	for(int j=1;j<=n;j++)
		printf("%d ",get_num());
	printf("\n");
	for(int j=1;j<=n;j++)
		printf("%d ",get_num());
	printf("\n");
	if(kd){
		for(int j=2;j<=n;j++)printf("%d %d\n",j-1,j);
		return 0;
	}else{
		random_shuffle(p+1,p+n+1);
		for(int j=2;j<=n;j++)
		printf("%d %d\n",p[fa[j]],p[j]);
	}
	return 0;
}
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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69

---

8 一些小细节

1. 倍增:注意先枚举k再枚举i。
2. 线段树如果有负下标应将mid设为(l+r)>>1，不能用(l+r)/2，因为C++除法向0取整。
3. 多关键字更新答案一定要注意顺序。
   example：

if(maxh==h&&mxa>a)mxa=a;
if(maxh<h)maxh=h,mxa=a;//不能够交换顺序
1
2

4.以后检查代码的时重点还是应该在检查是否手残上:)因为我经常手残：)
5.多组数据一定要清空！！清空！！清空！！

数据千万条，清空第一条。
多测不清空，爆零两行泪。

---

10 考试策略相关

拿到题目首先看第一页的时空限制以及文件及题目名(感受出题人的毒瘤)。
然后看题面，最好把三道题目都读完，预估一下总体难度如何，最好心里排个序，但在NOIP这种情况还是很少见（除了NOIP2016 day1）。
然后开始做题，建议从子任务一步一步做着走，这在NOIP中是十分有用的，因为出题人会给你很多提示，但平时的考试就很难说了…
通过的测试点可以在上面打个标记，可以让你有一种成就感。
选择打正解还是打暴力一直是我很头疼的事情。按理来说NOIP的部分分大多是思维型的，不会浪费太多时间。
做完一道难题可以去上上厕所，实测很实用。

---

最后，无论最终是失败还是成功：
CSP 2019 RP ++

UPD：没想到还是遇到了不可抗因素…