考前曾犯错误小结

考场的准则

1.不要老是想着打正解,部分分打满了也是一种成功(特别是要学习@HeliumLN的DFS,打着打着加个记忆化就AC了)

这里提名某期望DP换教室,如果你发现动态规划方程又长又难写,那就先不要写。写个$dfs​$来暴力枚举情况容易多了。同机房的人用$dfs​$直接搜了$60pts​$,某些神仙加了记忆化后更是直接$AC​$了。

2.容易的题一定不能失分,想通过做难题来弥补分数几乎是不可能的。

某蒟蒻参加$noip2018​$时曾经把$day1T1​$贪心炸了,从省二–>省四。这是不可原谅的错误,错简单题的人是最应该被鄙视的。要知道那题简单暴力都有$80pts​$。

3.如果你觉得专注度不够了,上个厕所?

一直$debug​$总会让人精神焦虑,在$OI​$界有句名言就是厕所出正解。还是有一定参考价值的。

考前曾犯错误小结

1.在使用位运算时请务必记得加括号,位运算符的优先级都是比较低的。

在愤怒的小鸟一题中,我曾写了如下代码:

1
2
minn = min(minn, dfs(x|1<<i+1));
//这样子会左移i+1个单位,不仅状态错了,步数也错了

实际上应该是:

1
2
minn = min(minn, dfs(x|(1<<i))+1);
//实际上我想写的是左移i个单位并增加步数1,这才符合原来的想法

2.在倍增中,不要把$2^i$开到第一维,在很多情况下虽然能AC但会慢上许多,在很多评测机上可能就是AC->TLE的悲剧

在货车运输中,我曾这样定义了倍增数组:

1
2
maxw[21][maxn], tree[21][maxn];
//因为数组是线性存储的,所以从pow(2, i)->pow(2, i+1)时需要跨过maxn这么多数

实际上这样定义会更好(因为缓存的原因会快很多):

1
maxw[maxn][21], tree[maxn][21];

PS:树上倍增很有用,特别是维护树上最值的时候,相当于树上ST表

3.如果你要写对拍,千万别把自己的对拍程序命名为fc.exe,这样子他会递归调用自身而不是去调用系统的fc函数去对比文件差异。

4.请务必注意变量的意义和更新顺序,这可能会在统计答案时出很大差错

在货车运输中,处理树上边权极值时,我曾打错了更新位置:

1
2
3
4
5
6
7
8
9
if(tree[i][x] != tree[i][y])
{
//正确的更新位置
ans = min(ans, min(maxw[i][x], maxw[i][y]));
x = tree[i][x];
y = tree[i][y];
//把ans写在这里是错的,因为你在前面已经更新了x。
//ans = min(ans, min(maxw[i][x], maxw[i][y]));
}

在砝码称重中,因为位移了下标但却没有及时更新过来,曾写出这样的错误代码:

1
2
if(x > n)		return;
//因为位移了坐标,枚举到第n-1个砝码就会退出了

实际上,我的x的意义不是搜索到了第$x​$个砝码,而是搜索到了第$x​$个二进制位是否需要被删除(我使用了状态压缩来存储),又因为我喜欢不使用第一位来存放,所以在$n​$个砝码的情况下,我应该要更新到$n+1​$位。

因此写出如下的正确代码:

1
if(x > n+1)		return;

下标位移很多时候都会用到,比如前缀和一类,一定要注意位移前后的差异!

5.int不要随便乘,一定要注意数据范围,算着算着就溢出了。

我曾经这样计算平面上点对的距离($0 \leq |x_i|, y_i| \leq 10^9$):

1
2
3
double calc(int x1, int y1, int x2, int y2){
return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}

但是$WA$了六点,后面想了想,其实应该这样子:

1
2
3
4
double calc(int x1, int y1, int x2, int y2){
return sqrt(1LL*(x1-x2)*(x1-x2)+1LL*(y1-y2)*(y1-y2));
}
//其中1LL的作用是把int转为long long,这样子乘起来就不会溢出了

作者杂谈:

简单的代码里也有很多细节需要处理,平时需要格外留心。

现在想想应该早点写这个错误小结的,这样子大概能找出更多潜在的未注意到的细节吧。


CSP经验杂谈

1.不要贪恋强大的数据结构。

对于绝大多数选手,在考场上难以靠数据结构取胜。一般能够拿全搜索分,就是我们的胜利。请务必注重基础算法,$noip2017_day2t2$和$noip2016_day2t3$都可以通过$dfs$+暴力剪枝来获得满分,不需要去推往往更易出错的状态压缩。

2.请一定要写出正确的暴力,不然优化时间复杂度的时候往往会爆炸。

个人写程序习惯暴力->优化复杂度->AC,因为实际情况中很难有一次通过的情况。

如果你暴力都写炸了,你就会发现对拍时总是过不去过不去过不去,然后就会自闭就会$GG$。

特别要留意各种边界问题和类型溢出!如果是暴力可以不在乎空间全部上$long \ long$!