Gravatar
LikableP
积分:1891
提交:416 / 1100

Pro4276  [THUPC 2025 pre] 检查站

官方题解。来源:清华大学学生算法协会仓库

题目很明显是一个最小割问题。对于题目描述中的“通知一个分部,在其所有下辖的铁路上设立检查站”操作,我们需要对如下问题进行网络流建模:给定网络流图以及对其边的划分,一次可以以 $1$ 的代价割掉一个划分集合中的所有边。特别地,在同一个划分集合中的所有边都与某个点相邻。

考虑某个形如 $A_i \to x_i \to B_i$ 的划分集合,其中 $A_i$ 和 $B_i$ 为任意点集。考虑如下建模:

  • 建立虚点 $p_i, q_i$;
  • 有边 $(p_i,q_i,1)$、$(A_i, p_i, 1)$、$(x_i, p_i, 1)$、$(q_i,x_i,1)$、$(q_i,B_i,1)$。

注意到在这个建模中,若所有边都不被割掉,其连通关系恰好为 $A_i \to x \to B_i$,而割掉 $p_i \to q_i$ 之后这个连通关系就消失了,符合我们的需求。

再注意到网络流图上的所有边边权均为 1,直接运行 dinic 算法求解最大流的复杂度为 $O(n \sqrt{m})$,足以通过本题。


2026-01-30 20:21:23    
我有话要说
Gravatar
LikableP
积分:1891
提交:416 / 1100
123

COGS MathJax 基础教程

MathJax 展示——柯西积分公式
\(\verb|$$f(a) = \frac{1}{2\pi i} \oint_{\gamma} \frac{f(z)}{z-a} \, \mathrm{d}z$$|\)
$$f(a)=\frac{1}{2\pi i}\oint_{\gamma}\frac{f(z)}{z-a}\,\mathrm{d}z$$

前言

由于见到机房有些许同学不会使用 LaTeX 导致出的题题面不规范、无法在题面中输入想要的数学公式等问题频发,特此撰写该教程供大家参考。本人能力不及,写作中难免出现各种问题,若有疏漏,请联系修正!

首先推荐两个识别手写 LaTeX 符号的网站:

  • Symbolizer: LaTeX 字符识别:一个完全离线的手写 LaTeX 符号识别 Demo,推理在浏览器本地完成,模型通过 WASM 加载,无需网络。

    点开试用
  • Detexify:任何使用 LaTeX 的人都知道,在 symbols-a4.pdf 中找到一个你记不住的符号是多么耗费时间。Detexify 旨在简化这一搜索过程。

    点开试用

MathJax 简介

MathJax 是一个基于 JavaScript 的库,可以将 LaTeX、MathML 以及 AsciiMath 渲染成高质量的数学符号。其使用 HTML + CSS 或 SVG 渲染,而非图片,从而保证了公式的清晰度。MathJax 因其安装使用简单,且客户端无需额外操作就可直接显示公式而被广泛使用。

MathJax 目前最新版本为 MathJax v4.1.1,COGS 使用的版本为 MathJax v2.2。但实际上 MathJax v2.2 就能够完成我们的大部分需求。MathJax v2.2 官方文档PDF)。但如果有特殊需求,后文将会介绍如何强制使用 MathJax v4.1.1。

MathJax 基础教程

键入数学公式

数学公式分为两种:行内公式与行间公式。键入行内公式请使用 \(\verb|$ ... $|\) 或 $\verb|\( ... \)|$ 将内容包裹1。键入行间公式请使用 \(\verb|$$ ... $$|\) 或 $\verb|\[ ... \]|$ 将内容包裹。

行内公式
小 A 有一个长度为 \(\verb|$n$|\) 的序列, 其中的最大值为 $\verb|\(max\)|$。
小 A 有一个长度为 $n$ 的序列,其中的最大值为 \(max\)。
行间公式
最终的答案为:\(\verb|$$\max_{i=1}^n f_i$$|\) 即 $\verb|\[\min_{i=1}^n g_i\]|$
最终的答案为:$$\max_{i=1}^n f_i$$ 即 \[\min_{i=1}^n g_i\]

在 COGS 中键入行间公式

在 COGS 中正常使用 \(\verb|$ ... $|\) 和 $\verb|\( ... \)|$ 是完全没有问题的,但如果尝试键入多行的行间公式,例如:

错误使用案例

会导致渲染出错:

错误渲染结果

这是因为 COGS 的编辑器在用户输入换行符的时候会开一个新的段落,MathJax 只会渲染同一个段落的公式。点击“HTML 代码”即可看到原因:

错误渲染原因

解决方法有两种,第一种是把公式写成一行,像这样:

修正方法一

或者直接在 HTML 模式里写公式,亦或是在其他在线编辑器写好 LaTeX 代码之后直接在 HTML 公式里粘贴进去:

修正方法二 1

这时候关闭 HTML 模式回到正常模式会发现换行全部消失,别担心,这是正常情况,如果返回 HTML 模式就能看到换行了:

修正方法二 2

渲染结果:

修正后渲染结果

  1. MathJax 默认无法使用 \(\verb|$ ... $|\) 键入行内公式,原因是美元符号 \(\verb|$|\) 在国外的文章中过于常见。而 COGS 对 MathJax 进行了配置,使得其可以使用 \(\verb|$ ... $|\) 键入行内公式。


2026-03-05 19:56:50