Mathjax是一种方便的数学公式渲染工具，能接受多种输入和输出要求：
Mathjax推荐通过cdn.mathjax.org使用，但由于经费问题，CDN服务器将于4月30日关闭。当我得到这条消息时，又想起了曾经被否定的计划。
USACO07MAR Gold T2:Ranking the Cows
原题范围：$n\le1000,m\le10000$
应该可以发现，把一对关系转换成一条边后，问题就转换成求出有向图的传递闭包。做完传递闭包后，答案就等于$\frac {n*(n-1)/2}2$-联通的点对数。当有向图中出现环时，即为自相矛盾。
考虑如何计算传递闭包：
使用$f_{i,j}=f_{i,j}\lor(f_{i,k}\land f_{k,j})$，其中$k,i,j\in 1\ldots n$计算。当然，初始值为$f_{i,j}=\begin{cases}true&i=j\ false &i\ne j\end{cases}$。
最后统计答案时注意减去自环，同时判断是否有环。
这样时间复杂度时$O(n^3)$的，可以得到30分。
$C,N\le10$
这么小的数据，应该随便怎么搜索都可以吧。我没有写过。
$C,N\le500$
直接二分图最大匹配，用匈牙利算法，应该是提高组要求。输出方案只要输出match[]数组。时间复杂度近似是$N^3$的，应该很容易得到这个分。
题目来源或改编自USACO月赛，顺序与难度无关。
| 项目名称 | 穿越马路 | 2048 | 瓶颈 | GPS的决斗 |
|---|---|---|---|---|
| 文件名 | helpcross.* | 2048.* | bottleneck.* | gpsduel.* |
| 时间限制 | 1s | 2s | 1s | 3s |
| 空间限制 | 512MB | 512MB | 512MB | 512MB |
| 优化选项 | 无 | 无 | 无 | -O2 |
| 测试点数量 | 10 | 20 | 10 | 10 |
| 测试点分数 | 10 | 5 | 10 | 10 |
| 比较方式 | SPJ | 全文 | 全文 | SPJ |
| 部分分 | 有 | 无 | 无 | 有 |
这题要求的是带负权边的最短路，显然不能直接用Dijkstra。然而Bellman-Ford或SPFA的时间复杂度最坏$O(NM)$，而且众所周知，USACO总是卡SPFA的。尽管这题数据比较老，因此SPFA+SLF可以水过，但是正解并不是如此。
顺便说一下，用优先队列优化SPFA并不有效(来自[模板]单源最短路-题解)，在这题比普通SPFA更慢。然而在某些边权为正的卡SPFA的图中，几乎和Dijkstra不相上下。
可以发现，图有一个很强的性质：对于无向边，边权总是正的，因此每个无向边联通块是强联通的。而可能的负权边保证不能反向联通，因此把无向边联通块缩点后，得到的就是DAG。这样就可以在块内使用Dijkstra，块间利用拓扑排序更新答案。时间复杂度$O(M\log N)$。
这题其实有很多方法，但是我最先想到的是按照奶牛的高度排序处理。而且这种方法也可以做被困在干草堆（金）。当然按照位置排序也是可以的。
首先按照奶牛的高度降序排序，在处理一只奶牛时，把大于等于它的高度的2倍的奶牛的位置放进set中，再判断一下set中的位置在当前奶牛两边的位置是否小于等于d，计入答案即可。
时间复杂度$O(N\log N)$，与其他方法相同，但常数比单调队列大。因为后者只要用到sort，比set常数小得多。
应该可以发现，这题可以用贪心。有两个值需要满足比较麻烦，我们考虑对询问和牧草按照口感（绿色值）排序。这样，对于一个询问(Ai,Bi)，只要从口感大于等于Bi的牧草中选出价格最小的且大于等于Ai的牧草，这样可以证明是最优的。如果没有符合条件的牧草，就是无解。
用multiset来维护牧草的价格很方便，支持所有操作，当然价格可以重复。时间复杂度$O(N\log N)$
在算法竞赛中，I/O有时是影响效率的瓶颈。I/O优化可以被模板化，与具体问题无关，是常数优化的重要方式之一。看到网上有很多关于这方面的文章，我也想来自己研究一下。
NOI系列目前支持的语言有C，C++和Pascal，其中C++可以直接使用C的绝大多数功能（但也有例外），因此下面只考虑C++和Pascal两种语言。通常，每种语言都提供了几种平台无关的I/O方式，如C++中的scanf/printf，cin/cout，fread/fwrite，Pascal中的read/write，blockread/blockwrite。也有一些低级的平台有关的I/O方式，Windows和Linux(Unix)都提供了内存映射文件，效率更加高。
在算法竞赛中，I/O通常用文本文件，而数据只有整数、浮点数和字符串三种。把十进制的字符串转换成整数或浮点数需要一定的时间，而分离出字符串也需要一定的时间，这就是I/O优化的方向。我们通常优化了时间，但是也降低了通用性。
这题也有很多方法，其实并不用可并堆。类似于上一种方法，计算出dfs序和每个点的深度，然后按深度降序排序。对于每个点，需要删除深度相差超过L的点，并加入当前点，在子树中统计答案。而这些用树状数组就可以了（单点修改+区间查询）。时间复杂度$O(N\log N)$
当然，还有一种更加巧妙的方法。用倍增求出$2^i$步祖先，然后就可以找到第一个距离超过L的祖先，用差分区间加，最后就能算出答案。时间复杂度也是$O(N\log N)$，下面提供了官方题解中的这种方法的代码供参考。
有时我们需要出题，用什么好呢？
当然，缺点也很多：
如果你喜欢WYSIWYG，但又需要$\LaTeX{}$中的数学公式，可以试一下LyX。