必要知识培训

ACM必要知识培训


作者:老陈

常见的比赛相关常识

CCPC/ICPC

CCPC是国内的,ICPC是国际的(China & International Collegiate Programming Contest)

各种测试结果的简称

Wrong Answer:WA Time Limit Exceeded:TLE/T Memory Limit Exceeded:MLE/M
Accepted:AC Compile Error:CE Runtime Error:RE
Presentation Error:PE ……

OI/NOI/NOIP/CTSC

OI是中学生信息学竞赛,NOI/NOIP/CTSC是省级竞赛、国级竞赛、国家队选拔赛的简称。不做过多介绍

AK

即All Kill,也就是把本场比赛的题目全部AC。

爆零

即0 AC,也就是本场比赛一道题都没有通过。

Tx

第几题的意思。例如T3就是第三题。

还有很多……

关于限时与内存

限时

记住一个点:测评姬1s可以计算$10^8$次!所以你可以通过计算时间复杂度估计出计算次数就可以大致知道会不会超时。

内存

内存比较玄乎。

不过注意:数组开成全局变量!

对于128M的内存限制,能开$3.3 × 10^8$的数组。

常见失误

运算溢出

例:输入a和b,计算a+b。($0 ≤ 𝑎, 𝑏 ≤ 2 × 10^9$)

1
2
3
int a, b; 
scanf("%d%d", &a, &b);
printf("%d", a + b);

很明显,当a和b都为$2 × 10^9$时,结果是超过了int的存储范围的。所以我们需要使用long long才存储结果(输出)。

1
2
3
int a, b; 
scanf("%d%d", &a, &b);
printf(“%lld”, (long long)a + b);

越界

RE的最常见原因,其中一个常见原因就是数组开太小了。

所以养成一个习惯:开的数组比题目要求的大一点点

例:给定一个字符串,将所有小写字母变成大写字母。(字符串长度≤1000)

1
2
3
4
char s[1000]; 
cin >> s;
for (int i = 0; i < strlen(s); i++)
cout << (char)toupper(s[i]);

这份代码会获得RE。(为什么?)

另外,注意不要访问数组外的内容。(例如int a[10]访问a[10])

差一错误

指大体计算方法正确,但是出现多一个或者少一个的现象,从而引发的答案错误(WA)。

例:给定数组,求某一区间[x,y]内所有元素的平均值。

1
2
3
4
int sum = 0;
for (int i = x; i <= y; i++)
sum += num[i];
cout << (double)sum / (y - x);

很明显,这里应该除的是y-x+1,不是y-x

栈溢出

栈溢出常常是由递归调用的嵌套层数过多引发的。

超过$10^4$层的递归就不要写了。

例:计算斐波那契数列第n项的值。($1≤n≤10^6,$ 答案对$10^7 + 7$取模)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#define mod 10000007
typedef long long ll;
ll F(int n)
{
if (n == 1 || n == 2)
return 1;
return (F(n - 1) + F(n - 2)) % mod;

}
int main()
{
cout << F(n) % mod;
return 0;
}

优先级

看书本后面的优先级,不再赘述。

初始化/重置变量

对于多组输入,应该对上一组使用的数组等变量进行清空。

对于程序中的变量,养成习惯进行初始化。

时间复杂度

时间复杂度是衡量一个算法速度的标准。

例1:

1
for (int i = 0; i < n; i++)  num++;

我们会发现,这个循环的计算次数与n的大小有关(n是多少,num++就进行多少次)。所以这个循环的复杂度为O(n)

例2:

1
cout << n << endl;

这个句子只是个简单的输出语句,无论n多大,这个语句都只执行一次。所以这个循环的复杂度为O(1)

例3:

1
2
3
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
num[i][j] = i * j;

这段代码我们发现,当i为某一个值时,第二层循环就会执行n次。而i的范围为0-n-1。即外层循环执行n次,内层循环执行m次。那么我们可以算出这个循环的计算次数为$𝑛 ^2$次,所以这段代码的时间复杂度为$O(𝑛^2)$。

例4:

1
2
for (int i = 1; i <= n; i *= 2)  
res *= i;

这个循环的计算次数是多少呢?我们尝试列个表:

i 1 2 3 4 5 6 7 8 9
n 2 4 8 16 32 64 128 256 512

你会发现:若循环至少执行x次,那么n至少为$2^𝑥$。

那么我们可以得到:这段代码的时间复杂度为$O(log2𝑛)$

特殊的,对于2为底的对数,我们可以省略不写,即$O(log𝑛)$。

很多函数的时间复杂度也需要记忆,做题时最好计算次数以保证不会超时后再提交,避免不必要的罚时。

总结

嵌套的循环总复杂度为各层复杂度相乘。不嵌套的语句复杂度为相加,忽略系数,仅保留最大项。

例如有段代码是这样的:

1
2
3
4
5
6
7
8
9
for (int i = 0; i < n * 2; i++) 
for (int j = 0; j < n; j++)
num[1][j] = i * j;

for (int i = 0; i < n; i++)
sort(vis, vis + n);

cout << res << " ";
cout << num[n-1][n-1];

我们可以看到,一开始有个两层的嵌套循环。第一层复杂度为$O(𝑛) $(注意忽略系数),第二层为$O(n)$。那么这个循环的总复杂度为$O(𝑛^2)$。

接下来一个$O(n)$的循环内调用了sort函数,sort函数的复杂度$O(𝑛logn)$,所以这段代码的复杂度为$O(𝑛^2log𝑛)$。最后两行输出语句复杂度均为O(1)。那么总复杂度相加,为$O(𝑛^2log𝑛+2)$,保留最大项,忽略系数,我们得到了最终的复杂度:$O(𝑛^2log𝑛)​$。

我们看一下下面的代码,计算一下时间复杂度:

最差情况、最优情况、平均与均摊复杂度

最差/最优情况:代码在最糟糕/最理想的情况下的时间复杂度。

以数组查询为例:

1
2
3
4
for (int i = 0; i < arr_len; i++) 
if (num[i] == x)
return i;
return -1;

这段代码最差情况为x不存在与数组num中,此时这段代码的时间复杂度为O(n)

最优情况是第一个数就是x,此时这段代码的时间复杂度为O(1)

平均复杂度:代码在所有情况下的平均时间复杂度。

均摊复杂度:代码在大部分情况下出现的时间复杂度。

例如:我现在有个长度为n的数组,如果数组没满,我就向数组内插入一个数;如果满了,我就计算数组的所有元素的和。

我们可以得到平均复杂度为$O(\frac{n-1+n}{n})=O(n)$,而均摊复杂度是$O(1)$。