欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

犯错集合&个人缺陷&好想法

程序员文章站 2022-05-09 15:14:15
...

犯错集合

  1. 善用CtrlCV,加快打字速度。

  2. 认真训练,不要CB!

  3. 调试用代码要注释于旁边 比如/*调试*/

  4. 不吝啬于打注释 尤其是思路不清晰时(当然最好还是想得很清楚了再开始)

  5. 边集数组2 线段树数组4 etc.
    至少判断每个数组的空间是否够 打代码时也要考虑越界问题
    原因: C++ 本身不可能报数组越界 只知道把指针瞎指

  6. 不要随意全开 ll 平时偷个懒问题不大

  7. 比赛前一天晚上好好睡觉! 早起床,吃好早餐,别碰咖啡

  8. Ctime 中的 clock() 可以用于算运行时间 time(0) 用于 srand()

  9. (tmp)等价于 (tmp!=0) 而非 (tmp>0)

  10. 比赛里的题目顺序不要管!血淋淋的例子GDKOI2018Day1

  11. O2要求十分严格 可能导致RE 所以不必要就别开

  12. 函数不要作为循环范围(如ve[].size()) 建议记下来再用

  13. vector 可能导致空间&时间二倍 也可以通过提前reserve防止其按二进制分配空间

  14. 当题目复杂时,确立单一观察对象思考 例:各类hanoi

  15. double 不能用memset赋极值(清空海星) 看上去值没问题 比大小时会出锅

  16. struct 的 memset 需要使用 memset(&t,value,(sizeof t)或(sizeof(struct_name)));

  17. 某种情况计算多次时 记得先考虑情况数是否整除 则考虑算完总数后作除法

  18. 搜索顺序对时间影响巨大 不确定时可以对拍寻找较快顺序(反正只用改一点点)

  19. 如果搜索题目剪枝编程复杂度较高 建议先打基本版 然后去做其他题 最后当提答题玩一玩差不多了

  20. Hall定理:存在从V1到V2的完全匹配 当且仅当V1中任意k个顶点至少与V2中k个顶点是相连的

  21. __Int128的输出要判断正负数

  22. 对于大部分关于集合{x|x=f(y),y属于S}

  23. 三维问题都可以采用 枚举(排序)一维+分治一维+数据结构一维

  24. 可以认为T(动态开点)=3*T(离线离散化) 所以不要轻易作死!!!

  25. LL比INT慢一倍!!!!

  26. cmd的fc是不忽略行末空格&(\r\n)的

  27. 打表拆系数是个好方法嘤嘤嘤

  28. 如果不知道怎么做就尝试重新描述题目吧!

  29. 有时在dfn很难线性实现时 不如改成类记忆化搜索吧!

  30. 当复杂度涉及已删除点时 要考虑被删除者是否被扫描 当复杂度涉及已删除点时 要考虑被删除者是否被扫描

  31. 不要轻易推翻原有的结论 很可能是极端条件杂糅(某些极端不共存)
    况且脑子还是新鲜的好用[吓]

  32. 对拍时 请再三检查随机数据的一般性和暴力的正确性

  33. 变元矩阵树定理:
    令A[i,i]=\sum e[i][j],A[i][j]=-e[i][j];注意负号!
    删去第r行第r列(1<=r<=n) 后,det(A’)就是各个生成树的边权积的总和

  34. 求行列式的N^3做法:高斯消元(行列加减)成上三角 此时答案就是对角线上(n-1)个量的乘积

  35. 稳定的排序算法:(带序号)相同元素结果稳定 而非时间

  36. 大部分C++程序数组下标从0开始(记得因为初赛挂过&看标慢)

  37. 有这样一类题目:边权=两点点权异或/gcd/… 求最小生成树 一般可以先把一些点(如点权相等)并在一起简化题目

  38. 然后!如果需要求方案数,需要算上最开始合并那些点的方案贡献(n^(n-2))

  39. 各类DP都可以考虑打成记忆化 好用范围:冗余状态多

  40. n个点n条边是环套树!为什么我以前一直不知道[捂脸emoij]

  41. 康托展开:一个排列的排名为 \sum [a_i为左的逆序对个数]*((i-1)!)
    逆康托展开 从第一个填什么或者从最小值位置开始考虑

  42. 考前三日 辛辣是禁忌 没有为什么!!!

  43. sort区间左闭右开

  44. 简记tarjan 边双:去掉割边 再给每个联通块染色 割边(x,y)满足low[y]>dfn[x]
    点双:当dfn[x]==low[x]时 当前点为割点 所以 比它dfn大&&没有被其他割点隔开的部分都属于这个点双 具体说来 开一个栈保存当前遍历到的部分 跑完子树后判x是否为最高点 (因为手推出锅太多次所以废话嘤嘤嘤)

  45. 多次提醒:请勿在意比赛题目顺序!

  46. 注意思维和代码的统一,不要出现多种贪心/博弈/DP/…策略杂糅的情况
    阿我知道只有我才会人格分裂式想题

  47. 树状数组:单点修改&前缀查询 套各种差分可以完成各种区间操作

  48. 根据期望可加性 可以把期望理解作转移时的权 仅对本次转移产生直接影响

  49. 数据范围最好再三看看 养成先检查常量定义和数组大小的习惯

  50. 对修改二进制分组:用于处理“(强制在线&)各个修改独立贡献”的一类问题
    原理:把修改按时间顺序分组 询问时在每组分开处理分开贡献 通过合并末尾相邻两组 把每组大小控制为2^i形式

  51. 树的哈希:对于无根树 取其重心为根;有两个重心时 规定hash值小的为根;
    (点有序)有根树和括号序一一对应 计算其括号序的哈希值即可
    具体说来 记f(x)为x的子树的hash 那么f(x)=v(x)+(f(son)异或和) 异或是为了防止子树遍历顺序影响哈希值
    重点注意:不要对中途异或值取模!不要对中途异或值取模!
    至于v(x) 我是随便取了 dep_x*du_x 反正只要是有根树上点的稳定性质应该都是可以的

  52. 如果想到的可优化部分既不是瓶颈又很难实现的话…那就别实现了呗[吐舌]

  53. 求环时一般是点双 因为边双的八字形特例 一个点可以存在于多个点双

  54. 慢慢地你会发现 一些经典问题的推法只需要看思路 因为别人的推法可能绕很多圈子

  55. 其实多个splay是可以共用 0 为根的 仅当你不需要0的son信息

  56. 齐肯多夫定理:任意正整数n都可以被唯一表示为若干个不连续的斐波那契数的和
    证明:考虑贪心构造解 注意到f_i+1=前i-1项不连续的斐波那契数的最大和 每次取p使得 f_p≤n<f_{p+1} 若不取f_p 前p-
    项显然无法出解

  57. 斐波那契博弈:先手必败当且仅当石子数n属于斐波那契数列
    证明:设n为第一个不满足结论的数
    当n=f_p
    ①考虑先手第一次取x,则x<n/3<f_{p-2} 故石子可以看作两堆f_{p-2}和f_{p-1} (因为先手无法一次取完第一堆) 由设可知后手总有方案取得第一堆最后一个石子
    ②又设此时后手最后一次取了q个石子 显然q≤f_{p-2}/3 又易证f_{p-2}/3<f_{p-1}/2 可知在第二堆先手也无法一次取完
    当n≠f_p 根据齐肯多夫定理 设n=\sum f_{a_i} a为有序数列,且不连续
    自此断言 先手可以取完f_{a_1} 此时剩下的f_{a_i}可视为互相独立的子游戏 每个都是后手必胜局面 得证

  58. bitset 是个好东西 对空间也有Ω(一般考虑为1/32)的优化 e.g.JZOJ5932 所以有些空间好像爆炸的做法也可以考虑

  59. O(n)求1~n逆元 inv_i=(-mo/i) * inv_{mo%i} 证明:设mo=ip+qmo=i*p+q 则 模意义下ip=qi*p=-q 同时除以iq得证

  60. 可以给予参数默认值(e.g:max(int a, int b=10))由于实参和形参是从左到右对应匹配的,所以带默认值的参数必须要在所有参数列表的右边

  61. 竞赛是中学生活的附加,是一份bouns,所以没有所谓辛苦!

  62. 伯努利数求自然数幂和
    犯错集合&个人缺陷&好想法

  63. 神秘滑稽小质数(cc)1109 (infleaking)727 (ilnil)311 神秘滑稽小质数(cc)1109 (infleaking)727 (ilnil)311

  64. 考场Debuff很正常,如果出现了 不要慌张。对自己要有自信!场上用平时双倍时间写出代码和对拍。参考PION7102和JZOJ5938两次经历 本以为需要一个小时实现的东西20min就打完了

  65. 时间复杂度如果比较卡最好测测极限数据,出题人常常在此设置30左右的区分点

  66. 竞赛图中,胜者向败者连边,将出度排序后得到序列s,其为合法比分序列当且仅当\forall k<=n,\sum_{i=1}^{k} s_i >= C(k,2)

  67. 图上应用根号思想:m*sqrt n求(无向图)三元环 考虑按度数将点分类 将边定向作度数大连向度数小 此时枚举点x每条出边 打上标记 再枚举(x,y)中y的每条出边(y,z) 若z被标记 则(x,y,z)合法 根据构图 一条边作为度数大点时出边被枚举一次 作为度数小点出边时被枚举至多sqrt n次 而度数大的点至多sqrt n个 最坏情况总复杂度O((m+n)*sqrt n)

  68. 对于可以离线的撤销操作 可以理解为把一个操作作用于一个时间区间

  69. 别太自信了…有时候你调试了一个小时只是因为某一次你手抖把L打成R之类的 所以半小时时候就可以静态查错

  70. 能不用实数就不用实数!@SjJ 100p->0p

  71. 猜到了结论一定要证明,如果没有证明头绪就拍!有些看上去很假的结论实际是真的QAQ 参见JZOJ5950

  72. 点积=投影模长=a.xb.x+a.yb.y,叉积=a顺时针扫到b的有向面积=a.xb.y-a.y*b.x

  73. 负数取模不稳定!所以如果需要取模要转绝对值

  74. 你以为你的树套树真的答案正确么?!比赛打树套树我就是狗!!

  75. 两个组合数式子的本质都是从一个C(m,n)=C(m-1,n-1)+C(m-1,n)起点 考虑两种情况 C(m-1,n)空缺或者C(m-1,n-1)空缺 犯错集合&个人缺陷&好想法

个人缺陷

  1. 数据结构,字符串练习少
  2. 容易开小差
  3. 脑子里汪洋大海
  4. 代码调试不熟悉 几乎没有技巧性可言
  5. 对睡眠和食物需求量极大

好想法

  1. 非递归求 dfs 序(szisz_i和根已知)
考虑每个点x
{
   找重儿子s
   dfn[s]=dfn[x]+1;
   求剩下儿子dfn(和sz有关)
}
  1. 二分答案求前k大 (例3329树上的路径)