kactl

韩国航空运输协会

此存储库托管 KACTL、KTH 的 ICPC 团队参考文档。它由 25 页可复制粘贴的 C++ 代码组成，用于 ICPC 风格的编程竞赛。

有关最终的可浏览版本，请参阅 kactl.pdf，有关原始源代码，请参阅 content/。

愿望

KACTL 算法应该：有用、简短、足够快、经过充分测试，并且如果相关、可读且易于修改。它们不应该过于通用，因为代码是手动输入的，这只会增加开销。由于空间问题，我们还排除了非常常见/简单的算法（例如 Dijkstra）或非常不常见的算法（一般加权匹配）。

如果您觉得缺少某些内容、可以清理或发现错误，请提出问题或发送拉取请求！

定制KACTL

虽然 KACTL 可以按原样使用，但如果您想创建个性化副本，也可以轻松修改。特别是，您可能想要更改封面页，或者自行选择要包含的算法 - 由于空间问题，并非存储库中的所有算法都包含在 pdf 中。您可能还想启用彩色语法突出显示。

content/kactl.tex是KACTL的主文件，可以编辑以更改团队名称、徽标、语法突出显示等。它从每个content/子目录导入chapter.tex文件，该文件定义了每个章节的内容。其中包括 LaTeX 形式的源代码、文本和数学。要在章节中添加/删除代码，请从chapter.tex文件中添加/删除相应的kactlimport行。为了更好地对齐，您可能需要插入hardcolumnbreak 、 columnbreak或newpage命令，尽管这通常只在重要比赛之前完成，而不是在主分支上完成。 pdf 中未包含的算法在chapter.tex中被注释掉。

要构建 KACTL，请在 *nix 机器上输入make kactl （或make fast ）——这将更新kactl.pdf 。 （Windows 也可能工作，但未经测试。） doc/README还有一些关于此的注释。

尖端：

1. 通过运行make showexcluded查看默认排除的内容。选择默认配置是为了初学者和高级团队的合理平衡。
2. 输入这些算法时请利用散列。每个算法的右上角都有一个 6 字符的 MD5 哈希值。该哈希值可以通过使用hash.sh或.vimrc中的:Hash命令生成。散列忽略空格和注释。

编码风格

KACTL 使用相对简洁的编码风格，在模板中定义了一些宏/typedef，有助于缩短代码。行宽为 63 个字符，带有用于缩进的制表符（制表符 = pdf 中的 2 个空格）。

每个算法都包含一个标头，其中包含代码的作者、添加日期、算法的描述、其测试状态，最好还包含源、许可证和时间复杂度。

kactl.pdf 的长度为 25 页 + 封面页。有时为了方便起见，生成的 kactl.pdf 会提交到存储库，但不会太频繁，因为它会使 git 操作变慢。

测试

KACTL 的目标是对算法的正确性具有高度的信心。测试是在在线法官和（对于较新的算法）上进行的，压力测试将输出与大量随机生成的案例的更简单的算法进行比较。这些测试位于stress-tests目录中，并在每次提交时使用 CI 运行。 CI 还会验证所有标头是否已编译（除了docs/scripts/skip_headers中的排除列表）以及 Latex 是否已编译。

old-unit-tests包含一些损坏的单元测试，上次触及大约十年前。

执照

与竞争性节目一样，许可情况有点不清楚。许多源文件都标有许可证（我们尝试使用 CC0），但也有许多没有。不过，假定其他作者有良好意愿，并且在许多情况下不需要许可，因为代码没有分发。为了帮助追溯，源文件中注明了来源和作者。

除了来自互联网的参考实现之外stress-tests中的所有内容都隐式地采用 CC0。