Skip to main content

__debug's Home Keep it simple, stupid

NOIP2016 之前

这里只写一些非常容易犯的错误或是非常坑的错误.

  • 取模
  • 看错题 (如: 子串 -> 子序列)
  • int 乘法溢出
  • double 炸精度 (double 只有大概 15 位的精度, 如果一个 long long 范围的数保留 6 位小数就炸飞了)
  • a << b 即使 blong long 但只要 a 不是就会炸
  • std::multisetcount 复杂度是 "logarithmic in size and linear in the number of matches" 的

Ideas

这里只写一下最近看到的.

  • 如果是要求全局答案最优, 单调性也可以是答案的单调性
  • long long 范围内的数的约数个数都在 \(x^{1/3}\) 左右
  • 对一个竞赛图拓扑排序, 每一层的点一起组成了一个强连通分量
  • 任意模数高斯消元: 在矩阵的行与行之间做辗转相除即可
  • 用矩阵乘法优化特殊 DP: 只需证明 DP 转移方式有结合性即可
  • 边权可能为 \(0\) 的 BFS: 用边权为 \(0\) 的边扩展出来的节点放入队首即可
  • 二进制问题的一种思路: 在每个 \(\pmod{2^k}\) 意义下考虑, 而非仅仅单独考虑每一位
  • 类似 ST 表分解区间的方式: 相比线段树而言, 这样做的好处是只要长度相同, 区间的构成就是相同的
  • 一类通过 +1/-1 将序列变为单调递增的问题: 这类题目有一个经典转化: 将 \(A_i\) 变为 \(A_i - i\), 问题转化为让所有数单调不降
  • 一类带有周期性的可达性问题: 当能凑出 \(x\) 就能凑出 \(x + p\) 时, 只要对于每个 \(y \in [0, p)\), 求出能凑出的最小的 \(x\) 且 \(x \bmod p = y\) 即可
  • 启发式分治: 如果可以通过某种方法 (比如说两端往中间扫) 使得这一层的复杂度仅与分出来的较小的区间长度相关, 那么复杂度是对的, 类似反过来的启发式合并
  • LCT 上缩点: 主要是如何处理虚边. 其实与维护序虚边信息类似, access 的时候在并查集里查一下就可以了 (不同于普通的 access, 这里的 fa[v] 也要改)
  • Kruskal 重构树: 做 Kruskal 时将边也视为点, 合并两个连通块就相当于将这两个连通块的根连向这个边对应的点. 这样有些本来在图上的操作可以转化为子树(也就是区间)操作
  • 有多个源点(起始距离不同)的 BFS: 用两个队列维护距离, \(q_1\) 存下所有的源点并按距离排序, 新扩展的点都放在 \(q_2\) 中. 每次取出 \(q_1, q_2\) 队首较小的那个点就可以了
  • 后缀数组求子串字典序: 先求出 \(sa, height\), 然后定义 \(lexisum(i)\) 为后缀数组中第 \(i\) 个后缀的字典序, 那么有 \(lexisum(i) = lexisum(i - 1) + n - sa(i) + 1 - height(i)\). 子串的字典序也比较显然了

翻车

其实说了这么多, 最重要的就一句话:

一定要冷静.

看错题了/算法错了

  • 一定要冷静
  • 不要局限在原来的思路中
  • 算法的错误容易随机/构造出来吗? 如果并不容易, 可以考虑先放一放, 或是打打补丁
  • (认真看题, 提高严谨性)

死也想不出来

  • 一定要冷静
  • 再看一遍题
  • 用力想 (二分答案? 容斥? 单调性? 猜结论?, etc.)
  • 想特殊的部分分
  • 先去做其他题, 或是先拿尽可能多的部分分
  • 想不正确(或是不会证明)但是不容易被卡的方法 (骗分 QAQ)
  • (提高智商)

死也调不出来/拍出错了

  • 一定要冷静
  • 不要只对着最容易出错的地方调
  • 检查题意有没有搞错, 数据有没有错
  • 检查算法的正确性
  • 如果是很难打的题, 实在调不出来, 可以先打个暴力
  • (仔细打代码 + 适当静态差错)

注意事项

  • 一定要检查数组大小 (过大/过小)
  • 即使不打对拍, 一定要记得造极限数据
  • 对拍时造数据不能只造大数据 (比如说权值范围过大可能某些错误拍不出来)
  • 根据题目类型不同, 有些题即使过了大样例还是得对拍, 有些题只用造一下极限数据就稳了
  • 遇到奇怪的事情可以仔细思考一下, 说不定可以挖掘出什么性质来
  • 猜结论的时候一定要意识到自己是在猜
  • 及时备份代码, 特别是在一些较大的修改之前
  • 最后几分钟, 检查文件名, 数组大小, 各种常数, 然后编译一下

环境配置

首先执行 setxkbmap -option ctrl:swapcaps. 然后记得把输入法关了.

Emacs 配置: (记得在 .out 里面开 auto-revert-mode)

(load-theme 'tsdh-dark)
(menu-bar-mode 0)
(tool-bar-mode 0)
(scroll-bar-mode 0)

(ido-mode 1)
(winner-mode 1)
(show-paren-mode 1)

(setq auto-revert-interval 0.5)
(fset 'yes-or-no-p 'y-or-n-p)

(define-key key-translation-map (kbd "C-h") (kbd "DEL"))
(global-set-key (kbd "RET") 'newline-and-indent)
(global-set-key (kbd "M-h") 'backward-kill-word)

(defun myc++ ()
  (linum-mode t)
  (c-set-style "stroustrup")
  (c-toggle-hungry-state 1)
  (defun compile-and-run ()
    (interactive)
    (setq file-name (file-name-sans-extension (file-name-nondirectory buffer-file-name)))
    (compile
     (format "g++ %s.cpp -o %s -Wall -Wextra -Wshadow -g && echo \"Compilation finished\" && time ./%s"
	     file-name file-name file-name)))
  (local-set-key (kbd "C-c C-c") 'compile-and-run)
  (local-set-key (kbd "C-c C-k") 'kill-compilation))
(add-hook 'c++-mode-hook 'myc++)

打模板: (记得测试一下读入优化的负数与 chkmin / chkmax)

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cmath>
#include <climits>
#include <cassert>
#include <ctime>
#include <algorithm>
#include <functional>

#define x first
#define y second
#define MP std::make_pair
#define DEBUG(...) fprintf(stderr, __VA_ARGS__)

typedef long long LL;
typedef std::pair<int, int> Pii;

template<typename T> inline bool chkmax(T &a, T b) { return a < b ? a = b, true : false; }
template<typename T> inline bool chkmin(T &a, T b) { return a > b ? a = b, true : false; }
template<typename T> void read(T &x)
{
    int f = 1;
    char ch;
    for (ch = getchar(); !isdigit(ch); ch = getchar()) {
	if (ch == '-')
	    f = -1;
    }
    for (x = 0; isdigit(ch); ch = getchar()) {
	x = x * 10 + ch - '0';
    }
    x *= f;
}

Comments

Comments powered by Disqus