思路

这题其实有很多方法，但是我最先想到的是按照奶牛的高度排序处理。而且这种方法也可以做被困在干草堆（金）。当然按照位置排序也是可以的。

首先按照奶牛的高度降序排序，在处理一只奶牛时，把大于等于它的高度的2倍的奶牛的位置放进set中，再判断一下set中的位置在当前奶牛两边的位置是否小于等于d，计入答案即可。

时间复杂度$O(N\log N)$，与其他方法相同，但常数比单调队列大。因为后者只要用到sort，比set常数小得多。

思路

这题要求的是带负权边的最短路，显然不能直接用Dijkstra。然而Bellman-Ford或SPFA的时间复杂度最坏$O(NM)$，而且众所周知，USACO总是卡SPFA的。尽管这题数据比较老，因此SPFA+SLF可以水过，但是正解并不是如此。

顺便说一下，用优先队列优化SPFA并不有效(来自[模板]单源最短路-题解)，在这题比普通SPFA更慢。然而在某些边权为正的卡SPFA的图中，几乎和Dijkstra不相上下。

可以发现，图有一个很强的性质：对于无向边，边权总是正的，因此每个无向边联通块是强联通的。而可能的负权边保证不能反向联通，因此把无向边联通块缩点后，得到的就是DAG。这样就可以在块内使用Dijkstra，块间利用拓扑排序更新答案。时间复杂度$O(M\log N)$。

题目来源或改编自USACO月赛，顺序与难度无关。

题目概述

注意事项

1. 请注意题目的数据大小，根据情况适当地使用输入/输出优化。
2. 数据范围中，如果没有说明，前面的数据满足后面的要求。
3. 对于有部分分的题目，如果你只做了其中一问，也要按照格式要求输出所有内容；否则无法保证得分。

1.穿越马路

30%

$C,N\le10$

这么小的数据，应该随便怎么搜索都可以吧。我没有写过。

60%

$C,N\le500$

直接二分图最大匹配，用匈牙利算法，应该是提高组要求。输出方案只要输出match[]数组。时间复杂度近似是$N^3$的，应该很容易得到这个分。

1.排序

原题

USACO07MAR Gold T2:Ranking the Cows

原题范围：$n\le1000,m\le10000$

题目 官方题解 数据

题解

应该可以发现，把一对关系转换成一条边后，问题就转换成求出有向图的传递闭包。做完传递闭包后，答案就等于$\frac {n*(n-1)/2}2$-联通的点对数。当有向图中出现环时，即为自相矛盾。

考虑如何计算传递闭包：

Floyd

使用$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分。

题目来源于USACO月赛，数据范围有所加强

题目概述

注意事项

1. 所有题目中程序允许创建临时文件(仅供参考)。在C/C++中建议使用tmpfile函数创建临时文件，在关闭文件后将自动删除。

   1
   2
   3
   4
   5
   6
   #include<stdio.h>
   FILE *tmpfile( void );
   //C
   #include<cstdio>
   std::FILE* std::tmpfile();
   //C++
   

2. 新挑战*为附加题，同时测试交互题的情况。
3. 对于#标的题，请注意常数因子对于程序效率的影响(标程最长运行时间超过时限的一半)。