U 群常见问题速查

图灵奖

多项式复杂度

可以除 $w$ 或除 $\log$，很难降次数。$\omega < 2.372$ 为矩阵乘法复杂度指数下界。

——From CommonAnts

参考资料

学会计算模型、复杂性、归约/问题类等计算理论基本思想后，自行搜索精细复杂性理论入门讲解（Fine-grained complexity）。

相关 OI 博客：

• lca 的讲解（bilibili 视频，@蔡德仁）
• lxl/crz 的相关讲解（资料集）
• EI《一些经典问题比暴力快一点点的算法》（博客）
• Ynoi《浅谈归约矩乘》（洛谷博客）
• Futari《归约矩乘》（洛谷博客）
• do-while-true《一小类矩阵乘法相关归约》（博客）
• hqztrue《浅谈矩阵乘法在算法竞赛中的应用》（知乎）
• 杨敏行《浅谈复杂度及其在解决问题方面的应用》
• 闫陈效《计算理论与 OI 中的难解问题》（2024 集训队论文集）

——From CommonAnts

NP-Hard

• Karp's 21 NP-Complete Problems
• $m$ 个大小均为 $c$ 的背包能否装下给定物品（强 NPC，即不存在伪多项式算法）
• 简单环计数
• 二分图完美匹配计数
• 2-SAT 计数
• 拓扑序计数
• 无向图欧拉回路/欧拉路径计数

约数个数/不同质因子个数表

问题与做法

单点修改区间 $\operatorname{mex}$

考虑一个值 $v$，$v$ 没出现说明 $[l,r]$ 夹在 $v$ 的相邻两次出现之间。因此对于每个值 $v$ 的相邻两次出现 $i$ 和 $j$，在数据结构中插入点 $(i,j)$、权值为 $v$；查询为 $i<l\le r<j$ 的点的权值最小值（单点修改，矩形求 $\min$），使用树套树即可。

静态区间 LIS 的 $\operatorname{polylog}$ 做法

参考 Codeforces 博客 或张景行《浅谈一类蒙日矩阵》（2022 集训队论文集）。

网站

• 那个画图的网站？
  • CS Academy Graph Editor
  • 上位替代：Another Graph Editor
• 那个查原题的网站？
  • 原题机
• 那个 AtCoder 评分的网站？
  • AtCoder Problems
• 那个能看 Codeforces 题目整理的网站？
  • CFTracker
• 那个能看所有 OJ 的比赛的网站？
  • Clist
• 那个看编译得到的汇编的网站？
  • Compiler Explorer
• 那个把 C 语言类型转成人话的网站？
  • cdecl
• XXX 用 LaTeX 怎么打？
  • Detexify
  • 许多网站使用 KaTeX 渲染公式，相应文档见 KaTeX Supported Functions
• 现在从哪里下 AtCoder 数据？
  • conlacda/atcoder-testcases

其他

vuqa 是什么意思？

van 能的 UOJ 群啊。

UB（Undefined Behavior，未定义行为）是什么？

参见 cppreference：Undefined behavior。

我的引用怎么失效了（tr[x].ls=insert()）？

在 C++17 之前，这段代码可能的求值顺序是：求出 tr[x] 的位置 → 插入（此时 vector 可能因为扩容而移动 tr 的存储位置）→ 已经求出来的 tr[x] 的位置失效了，但我们要往这个失效的位置写入数据 → 寄了。

扩展阅读：求值顺序（不是运算结合性）。

怎么做 NOI 排版风格的题面？

• 官方工具：TUACK + LaTeX
• Wallbreaker5th/fuzzy-cnoi-statement（Typst）
• Wallbreaker5th/OI-statement-LaTeX（LaTeX）
• cnoi.mrpython.top（Markdown）
• hull.aberter0x3f.top（Typst，但类似 TUACK，面向全出题流程）

GNU/Linux 如何测程序空间？

• RSS：time --format="%MKiB" ./a
• VSZ：程序结尾加 system("cat /proc/$PPID/status | grep VmPeak");
• 静态空间：size ./a

定义两个 bool 并且取地址差以测量静态空间并不靠谱。

来源：Wallbreaker5th/vuqa。