2022年ACM竞赛技巧 .pdf

《2022年ACM竞赛技巧 .pdf》由会员分享，可在线阅读，更多相关《2022年ACM竞赛技巧 .pdf（4页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、ACM 竞赛技巧drizzlecrj modified 关于调试和测试一、 下面是几种比较常见的错误：1输入输出格式错误( 注意空格，空行多余或者缺少,是否要输出“ case t:”) 2数据类型错误 ( 尽量在不超过内存的情况下用大的类型) 3范围检查错误 ( 可以稍稍加大上下界) 4变量名称错误 (for(int j = 0; j n; i+) 5漏语句 (看事先设计好的变量是否都用上了，再看每个模块是否实现了应有的功能，是否完成了接口) 二、应对于每道题设计充分的测试数据, 并保留那 些比较具 有代表性 的测试数据 , 以便于优化 的时候比 对：1 一定要记住删除屏幕 多于的测试输出！2

2、. 调试的 时候 ，一 定要钻输入 文件 的牛角尖 ，考虑到各种 情况 。3. 调试的 时候 ，常常 可以 编一个 非常非常易编 的程序 ，采用算两次 的方法 ，不过 前提 是必须 保证正确。4. printf, cout是 C/C+ 中最笨但又 是最准确 的调试方法。5. 调试时每发现一个错误，都最好浏览 一下整个程序 ，看是否有类 似错误， 这样非常 有效！6. 程序 出现不 确定性 的问题， 如对于同样 数据，有 时卡住 ，有 时很快 出结果 ，多 半都是 随机 模块有误 ！7. 指针 出错 常常 是 NULL.next 8. 不要 只顾埋头拉车 ，要抬头 看路。当被 一两个莫名其妙 的

3、错误 弄得晕头 转向 的时候 ，记住：很 可能错误在其他地 方。9. 每改完一个错误要 想想 是否 改正确了，是否 改彻底 了。10. 很多题 目最易 忽视 的就是初状态 =末状态 的情况， 还有初状态和末状态 存在可 操作 的决策 。11. 多考虑 一些特例 ，在 这方 面认真 些，全面 些，仔细 些，常比 多考虑些时 空上 限划 算得 多。12. 调试语句一 般和 上下 文保留一空行， 最好加上注 释，并 且一定记住 在最后删除。13. 调试和测试的 时候 一定要充分 考虑到各种 边界和特殊 情况 。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - -

4、- - - - - - 名师精心整理 - - - - - - - 第 1 页，共 4 页 - - - - - - - - - 14. 自测时千万 不要 忘测数据上 限，主要是看是否 会超界 。大半错误 均源 于此！之后仔细察 看 const 中的数。15. 大数 组处理 很容易出错， 所以尽量 避免开 过大的数 组及 其调 试。关于算法1关于复杂度涉及logN 的算法 .logN 常常 是因为 二分 , 树,Heap, 排序等造 成的，而且 有一 点应该注意 到,logN 更接近一个 常数， 而不是 N。2涉及矩阵 的统计问题，通常而言 ，降维策略 是非常 有效的，而且 常常 是在 外层枚举

5、用土方法 ，内层枚举使 用优化 过的 方法。 另外 ，用 O(N*N)枚举 出 Y1,Y2, 然后 考察之间夹 的矩形 是非常常 用的 方法。3涉及 01串的问题，都不要 忘记位运 算和压缩 ，同时 也要小心 。4对于 判重 问题， 关注最小表示。5有序化 的处理 常常比 无序的简单， 所以，对于 想不出 算法 的题 目，先有 序化！6对于 涉及 子序列之和 的问题，如 NOI Sequence ,CEOI Parity,B&W,常常化 为第一位到某一位的和。7大数据量的题 目，有 时候 分多 次读 入数据 会非常 有效8对于一 边明显长 于另外 一边的矩形 问题，常常 是基于短边的指数化或者

6、是 阶乘 算法 ，而基于长边的 O(N) 或者 O(N*N)的算法。9我们 应该注意， 许多求割 点的题目 是求给 定两 点间 的割点，而不是 普遍 意义上的 割点。10 没有回溯 的搜索 是最成功的 搜索。11 如果 你的算法 在最大规模的 时候 要爆，但是最大规模的数据 非常 难设计，那 么就不要 管他，设计一个稍次一点的算法 就行了 。12 尽量 让程序 不做已做 过的事 和显然没有必要的事， 也不要 解决无用的 子问题和对结果 进行无意义的引用。13 A* 算法 的估价函 数一 般而言 要保守 些，不要 为了速度的一 点提升丢失 了最优 解。14 一般情况下， 根据数据 规模猜算法 是

7、非常 有效的。15聚焦 边界！16对于 流量不超过 给定值的最大流问题，注意 取流值 的时候。17注意 qsort和 std:sort的用 法名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 4 页 - - - - - - - - - 18我们 不仅关心算法 的时间复杂度 ，还要关注最内层的循环 到底在干什么 。19在只涉及 乘除的高精 度运 算中 ，按因数存 储的效率远高 于按位存储的效率。20动态规划和 递推 更多应 考虑 本问题由哪 些已解 决子问题构成， 而不是 考

8、虑 本问题对 将来哪 些问 题有贡献 。21深度优先搜索 候（如求割顶 、桥、强连 通分支） ，一 定要记住常常 题中不止一棵搜索 树，也常常 有重边！22 优化 的时候 不要 去考虑最 坏的情况下是否有 太大的意 义， 只要在大多数情况下有比较 明显 的作用就行。23对于大 规模的 Dijkstra算法，如果 数据不 容易出得很 刁的话，用迭代代 替堆 也是不错的 选择 。用可更新队 列实现 也不错 。24很多图论 模型 中都要 考虑到 重边，即使是自己建 的图中也有可能出现 重边（Knights ）。25很多情况下，“不超前”属性的引入可以 使复杂度降 低一个数量 级。26很多时候 ，由于

9、 DP空间开 销很大， 我们 只能保留一个 阶段，这时候 从大到小的规划时常 收效颇佳 。27对于数 学味 较浓的问题，变量的 取值范围 与计算公式同等重要。28博弈 问题从残局 或结局出发分析往往 会有惊人 的发现。29博弈 问题胜负局 面的相加运算符合 Xor（也 就是和 mod 2）关于数据结构1 事实上， 链表的速度并不 比有序数组高多少， 虽然具有 O(1)的插入删除 复杂度 ，但是他的查 找是 O(N)的， 而有序数组虽然插入删除 是 O(N) 的， 但是查 找是 O(logN) 的。而且后 者好 编些。2 多用 int,少用 short 3 传统数据 结构的创新 性珠联璧合 是现

10、 代数据 结构试题的 发展方向。比如 邻接矩阵 +邻接链表。4 Joseph类问题中，如果采 用静态数组，删除 节点可能 导致 指针 错误。5 并查 集 Combine 时切记看两个 Fa是否 相同，否 则可能 引入圈。6 有时候 ，将链表和数组珠联璧合 ，如在大 规模约瑟夫 环中，会受到很好的 效果。7 在处理 小规 模链表的问题中，采用静态指针 （数组）效果比较 理想 ，便 于调试。 （比如 多维背包 ）关于 C/C+及程序实现1 移位有的 时候 能够带 来很大的 方便2 有时与其追求非常 精炼代码，还不如笨 拙的枚举 各种 情况， 只是注意在 Copy&Paste 的时候 不要出错 。3

11、 涉及 坐标 的问题， 常常 要考虑 坐标 的定义是基于最小区间的还是基于点 的。4 对于 涉及 时间的问题， 我们 必须 注意题 目中所说的时间是指时 间段还是 指时间点 。5 凡是分 母为变量的 除法 、除法 和取模都 需要想一想是否要 判 0 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 4 页 - - - - - - - - - 6 双向搜索 与其在精炼的代码上挣扎 ，还不如就两边分别写 过程，只是注意不要 乱 Copy&Paste. 7 链表的实现 常常 可以

12、 采用虚节 点的方法 ，但不要 生搬硬套 ，有 时候采 用 虚节点不一 定更好. 8 浮点数比较记得 使用 eps 9 记住 ，测试数据 只是用 来发现错误， 而不是用 来改正错误的， 依靠测试数据 改正错误， 越改越糊涂 ！10 注意计 算几何 中 Infinite 的引入。11 很多时候 ，输入的 两个数据并 没有说明两者的大 小关系！12 注意 memset一般只能用 来初始化数组为 0 或者 -1 13 编写 DFS 之前一定要先 考虑最 坏的情况下 栈 空间是否 够用。14 优先使用_int64 而不是 long long 16 交互问题一 定要注意接口 。17 开大数 组相当花时间

13、。18 A % 8=A & 7 19 编之前应该想 好需要变的 子程，不要 做无 用功， 同时 也为反复调用提供思 路。20 重要结论：a,b 取值 为0，1，则 a b=(a+b) % 2 21 对于取余输出， 我们 用(a-b+c) % c 而不是 (a-b) % c 22 一定不要 忘记初始化。23 在很多情况下， 异或运算可以 使代码更简洁高效。其它1 在竞赛期 间，参赛 队伍应及时将自己的文件 备份 ，以 便当 出现设 备故障 时迅速恢复文件。2 理解题意的 时候 千万 不要 想当然，只去做题目说的东西 ，不要 假设任何 题目没有提及到的条件。3 表达式处理 中注意 形如(a+b)*

14、(c+d) 的括号 。4 有少数题 目不是 按照先行 后列的方式组织数据的， 这一点要格 外注意。5 要小心 ，108 有 9 位，不是 8 位。9E14 是指 9*1014,不是914 ! 6 Waste memory when it makes your life easier . 7 Keep all working versions! 8 USE Precomputation ! 9 Pay attention to Symmetries! 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 4 页 - - - - - - - - -