【算法竞赛】错误&技巧

Livinfly

发布于 2023-01-10 15:03:17

4210

发布于 2023-01-10 15:03:17

文章被收录于专栏：Livinfly

邻接表，h[]忘记初始化。多组数据时，idx未初始化（会造成数组越界）
当使用并查集时，注意自己写的并查集是不是fa[x]随时都是x的祖宗，若不是，记得要用GetFa(x)
变量名有冲突y1, next, prev, has ...
在特别情况下.size()和int整型变量比较时会出错，所以尽量保证式子的运算结果是正数，因为如果是负数，unsigned int类型的变量会变成超大的正数。
priority_queue 默认是大根堆 < Type,vector,greater >是小根堆
图论采用虚拟源点时，注意点和边数组的大小
double类型存在精度误差，尽量不用==判断
在函数中引用数组时，用memset() sizeof 传入的数组是不对的。
线段树要开4倍N
二分注意二分的数值的大小可能要开LL， mid同理
dfs or ... if 先判断数组的下标会不会越界再判数组的值
字符串不要memset
&的优先级比==高
尽量不要相似的代码复制粘贴，很容易出错然后又不知道错在哪
map类型, 直接用mp[str], 它自动就插入里面了, 也就是说判里面没有这个元素必须要用mp.count(str) == 0!!!
static 慎用!!! static cnt = 0; 这里赋值只会在第一次有效
字串一般是连续的, 子序列一般是不连续的
DP的最终答案, 要看状态表示是什么, 题目要求是什么, 不总在最后一行, 如这题这种找到一个区域, 最大值可能出现在中间, 枚举答案要全部枚举一遍或者, 边...边更新!!!
强制转类型(LL)a*b+c*d会存在问题, 类型强制转换貌似是还是先按照运算顺序进行, 然后LL和int操作结果是LL,这个写法只转了a的类型.(LL)(a*b+c...)这样只是改变了括号里一坨的计算完的数据的类型.
答案确定了，但是数据没有读完，直接solve函数return;了。（POJ2492）
自己分类，情况都要走的话，不要if里面直接continue;（HD1198）
读入int，LL = int*int，还是会溢出的。CF1720A
^的优先级比<高。（没事多加括号（（
树状数组配上离散化，离散化下标要从1开始...不然死循环
c++20好像不能cin >> str+1; (char*)可能还是要用scanf("%s",str+1);
cout << fixed << x <<'\n'; (不加fix会存在科学计数法, xls血的教训)
rbegin()是完全反的迭代器，也是用++ 正常遍历（反向）的。
sqrt在自动下取整时候，因为是浮点数有误差，建议如果要求下取整等整数情况，自己手搓二分求解！！悲惨的fst
- upd，可以sqrt(n)+0.1或者先求sqrt() 然后while来做偏移
换LL的时候for循环的变量也看看
对有除法的式子取模，最好先找到逆元，不然转__int128。例子
需要对分别找多个数的因子进行计算，可以用线性筛的方式，找到每个数的最小的质因子，然后通过，边求因子，边除掉对应的最小质因子。例子
正确答案在int范围，但可能答案在LL范围，取最小值时由于爆int而变为负数，错误。
- ICPC济南2022 A. Tower
- Submission #188485811 - Codeforces Line 41