Gold第二波。

现在已完成：

50/50

[BZOJ1232 USACO]Cheer 安慰奶牛

把边权改成边长*2+两端耗时，然后MST，最后再加上耗时最小的点（作为起点

[BZOJ2580 USACO]Video Game

AC自动机上跑DP（Fail边向下传递结尾字符串数

[BZOJ2582 USACO]Bovine Alliance

★每个联通块单独考虑，再用乘法原理；在联通块内，若是E=V则有两种方案，若是E>V则不可能分配，若是E=V-1则有V种方案。可以用并查集实现（然而加完所有点要来次查找根操作）

[BZOJ3048 USACO]Cow Lineup

弄个队列扫描一遍，队列内不能有超过K+1种不同的数，若超过则向右移动左端点，答案容易维护

[BZOJ3074 USACO]The Cow Run

区间来回DP（双倍经验BZOJ1742

[BZOJ2620 USACO]Haybale Restacking

★环状移动石子，假设每个位置的石子都是从左边拿的，求出应拿石子K，ans就是K中每个数与其中位数的绝对值差之和。

[BZOJ3075 USACO]Necklace

DP，F[a,b]表示选到第a个且能匹配b格的最小删除数。每一格决策为选和不选，转移要借助KMP

[BZOJ2621 USACO]Cows in a Skyscraper

给N个数，求最小子集划分，使得每个子集的总和不超过限定。搜索可以玩（最优性剪枝），从大到小选能更快。

[BZOJ3126 USACO]Photo

★一道神题，DP可以弄，关键是决策的范围L（全部扫过的区间的最大左端坐标）和R（扫一半的区间的最小左端坐标-1）

[BZOJ1711 USACO]Dingin 吃饭

★网络流建模：三分图。将牛拆成a和A，然后S连Food连a连A连Drink连T（流量都为1）

[BZOJ1708 USACO]Money 奶牛的硬币

DP

[BZOJ1709 USACO]Super Paintball 超级弹珠

统计一下格子本身和横竖两斜的敌人个数，然后枚举站位，若横竖两斜的敌人个数减去格子本身个数*3=总敌人数就可以（容斥）

[BZOJ1707 USACO]Tanning 分配防晒霜

贪心，防晒霜从小到大分，优先分给右端最小的奶牛（网络流可做

[BZOJ1712 USACO]Summing Sums 加密

★矩阵快速幂，可以N^2的矩阵（TLE）正解是2*2的矩阵然后每个数对于得到的矩阵进行计算

[BZOJ1698 USACO]Lilypad Pond 荷叶池塘

类似最短路，先处理每个0能到达其他哪些0（默认起点和终点为0，答案减一下就行）然后就直接求BFS+最短路+方案数

[BZOJ1699 USACO]Balanced Lineup 排队

裸线段树

[BZOJ1700 USACO]Problem Solving 解题

DP，F[i,j]表示第i月解完前j道题后剩余的最多金钱

[BZOJ1696 USACO]Building A New Barn 新牛舍

可以知道中位数满足曼哈顿距离最短要求，然后就按照【不能与现有点重合】【保证现有点不相邻】做就行

[BZOJ1726 USACO]Roadblocks 第二短路

处理出最短路树，可以知道第二短路只经过一条非树边

[BZOJ1717 USACO]Milk Patterns 产奶的模式

正解用后缀数组+分组讨论，要简单的话二分答案+Hash解决

[BZOJ1724 USACO]Fence Repair 切割木板

反过来就是合并果子

[BZOJ1727 USACO]The Milk Queue 挤奶队列

★DP，保证相邻两数min(A1, B2)<min(A2, B1)（A在前B在后），排序后模拟

[BZOJ1702 USACO]Gold Balanced Lineup 平衡的队列

★F[i,j]表示前j牛中特色i的个数比特色i+1多多少，然后就可以Hash大法了

[BZOJ1703 USACO]Ranking the Cows 奶牛排名

★答案就是传递闭包中未确认点对数，然后由于是DAG就可以DFS求传递闭包了（Bitset优化）

[BZOJ1704 USACO]Face The Right Way 自动转身机

O(n)枚举转身长度，从左到右若需转身就转身，O(1)判定前k-1格的转身次数和需不需要转身，O(n^2)复杂度

[BZOJ1663 USACO]赶集

多加个0点表示起点，可拿奖品的边就连，求个最长路

[BZOJ1740 USACO]Yogurt factory 奶酪工厂

傻叉贪心

[BZOJ1742 USACO]Grazing on the Run 边跑边吃草

双倍经验题（区间来回DP

[BZOJ1741 USACO]Asteroids 穿越小行星群

转成二分图求最小覆盖

[BZOJ1739 USACO]Space Elevator 太空电梯

按限制高度从低到高做多次背包，Bitset优化

[BZOJ1738 USACO]Ombrophobic Bovines 发抖的牛

首先用Flody求任意两点最短路，然后二分答案

[BZOJ1737 USACO]Naptime 午睡时间

★环形DP神题，分两种情况DP两次（未越界和越界）

[BZOJ1736 USACO]The Wedding Juicer 婚宴的榨汁机

MC更新方块思想

[BZOJ1735 USACO]Muddy Fields 泥泞的牧场

★进化二分图匹配，把木板作点，泥地作边

[BZOJ1734 USACO]Aggressive cows 愤怒的牛

二分答案+贪心选

[BZOJ1733 USACO]Secret Milking Machine 神秘的挤奶机

二分答案+网络流

[BZOJ1731 USACO]Layout 排队布局

▲差分约束系统

[BZOJ1730 USACO]Barn Expansion 牛棚扩张

★扫描法，判断相同方向的边与边是否有交集

[BZOJ1666 USACO]Another Cow Number Game 奶牛的数字游戏

。。。

[BZOJ1668 USACO]Cow Pie Treasures 馅饼里的财富

裸DP，边界问题要处理好

[BZOJ1669 USACO]Hungry Cows 饥饿的奶牛

裸最长上升子序列

[BZOJ1715 USACO]Wormholes 虫洞

裸判负环（一开始想到要是负环不经过起点呢，后来看到了双向边。。。）

[BZOJ3445 USACO]Roadblock

最短路后每条位于最短路网上面的边都加倍玩一下

[BZOJ1755 USACO]Bank Interest

Gold画风不对系列

[BZOJ1754 USACO]Bull Math

Gold画风不对系列*2

[BZOJ1753 USACO]Who's in the Middle

Gold画风不对系列*3

[BZOJ1752 USACO]Til the Cows Come Home

Gold画风不对系列*4（裸最短路）

[BZOJ1751 USACO]Lake Counting

Gold画风不对系列*5（裸FloodFill）

[BZOJ1750 USACO]Apple Catching

Gold画风不对系列……嗯这个还不会（一眼DP）

[BZOJ1642 USACO]Milking Time 挤奶时间

区段才 $1000$，那么以区段作为点DP，而不是以时间作为点DP（当然要是离散化也是可以的）