论蒟蒻是怎样作死的(noip模拟赛心得&易错总结)

时间:2022-06-17 14:20:33

作为一名蒟蒻oier……

蒟蒻,俗称魔芋,全株有毒,以块茎为最,不可生吃,需加工后方可食用。 (手动滑稽)

sort() 从不写 #include<algorithm>
memset() 从不写#include<cstring>
从不关心是否 爆 int,从不开 long long
双向边 和 线段树 从来只开一倍大小
求 Lcm 总是先乘后除爆 long long 导致 RE
DP 和 递推 从不赋初值
求 Lca 和 并查集 同样从不赋初值
模拟向来复杂度高
经常看不到 时空限制,各种 TLE/MLE/RE
min/max 的初值总是搞反 (又是初值)
深搜从未一次写对,广搜从未写对
从来不 取模%%%
从不看 数据范围 是否包含 负数
经常把 循环变量名 重复使用/打错
经常写错 循环边界 0/1/N/M
提交代码的时候,从不建子文件夹
读入优化 int 改 LL 从来改不全


除此之外还应注意……

细节的地方一定要处理好。细节决定成败,点滴造就未来。

不能忘记删调试
不能写错 读入优化
不能忘记加 freopen(),fclose()
Linux 系统下全局变量可能没有初始化,最好初始化一下
调试刷屏的时候可以用 system(“pause”) 解决(头文件 #include<cstdlib>
指针用完后不能忘记 clear()
long long 可能会 MLE
注意运算的优先级
写 Dfs/递归的时候记得检查 递归层数(一般是10000层)
输出不能打错(如 “Yes”/”No”/”Impossible”)
心态要好,累了 去个厕所/洗把脸/吃块巧克力 (然而本人不爱吃巧克力因为太干2333)
听说程序最好要放在虚拟机里编译一下(本人并不知道怎么搞)
调试完以后要自测小数据和大数据


一些小技巧……

会写暴力先写大暴力。毕竟,骗分过样例,暴力出奇迹。

字符串复制可以用 strncpy(ans, A, num)
数组复制可以用 memcpy(ans, A, num)
(以上两个都是复制A中的num个给ans)
字符串字典序排序:bool cmp(string a, string b){return a+b<b+a;}
最大值最小/最小值最大 想想二分
贪心的证明:易证
有些 DP 的状态可以转换成最短路去做
遇到树,一般不是 图论 就是 树形DP
求和什么的题不会用 数据结构 就想想 前缀和 什么的
一个 hash 可能会重的话就 双hash 吧(不过犯懒的话可以用map)
手算数列查看是否为著名数列
有时间不能闲着,要对拍 (但是最可怕的是,只会写大暴力)
必要时,可以 打表找规律,可以写 无解/样例
考前先读题,读题后要将题目归入几个框架:模拟、枚举、搜索、贪心、DP、图论、分治

如果你发现你旁边的人写得很快,请你放心,他的算法十有八九是错的

所占内存 = 数组大小 * 类型长度 / 1024 / 1024(MB)
记得在编译器里打开警告 -Wall-Wshadow


关于考试的数据范围与算法的关系……

1e6 = 1000^2 = 100^3 = 2^20
n<=20: O(2^n) 搜索(瞎搜)、DP、暴力
n<=100: O(n^4) 搜索、DP、Floyd、暴力
n<=1000: O(n^2) DP、图论、暴力优化
n<=100000: O(nlogn) 二分答案、二分查找、分治
n<=1000000: O(n) 贪心、数学、构造、思维 (瞎写、卡常)


一些 zz 错误……

  1. for(int i = 20; i <= 0; i++){}
  2. for(int i = d; i <= d-k; i++){}
  3. for(int i = end; i <= start; i++){}
  4. dis[i] == 0;
  5. for(int i = 0; i < N; i++)for(int j = 0; j < i; i++){}
  6. dfs(){ ... dfs();... }复制一下 rdfs(){ ... dfs();... }

最后,预祝包括我在内的 全体oier 2017光棍节 不!退!役!!!