Gold第三波。1A率捉鸡。

现在已完成：

50/50

[BZOJ1749 USACO]Landscaping 地形改造

★移走土块，剩下K个山顶，求最小代价。

每次可以扫一遍求出所有山坡（所有方向折返往上的点和末尾都是山坡的末端）然后寻找去除哪个的费用最小（需注意边界问题），每次都贪心选代价最小的删去就行（吐槽：求山坡可真难啊（是用折返点求的

[BZOJ1748 USACO]Around the world 环球飞行

★求每个点环绕至少一个圈回到原点的最短距离。

BFS搜索，每个点弄个map记录曾经到达的坐标（因为点的坐标有可能会重复），然后坐标就顺+逆-

[BZOJ1747 USACO]Expedition 探险

★贪心，在不能走的时候选经过的含油量最大的油站加油

[BZOJ1746 USACO]Lazy Cows

B*2的地图，用K块布盖住所有点，求盖住总面积最小。

一眼看过去状压DP，转移恶心。

[BZOJ1745 USACO]Flying Right 飞行航班

区间覆盖变种

[BZOJ1744 USACO]Skiing 奶牛滑雪

★逆向思维，倒过来做最短路

[BZOJ1729 USACO]Cow Patterns 牛的模式匹配

★★KMP神题，一边匹配一边生成数字定位。数字定位就是满足（小于x中最大的且离x最近的，等于x且离x最近的，大于x中最小的且离x最近的）

[BZOJ1732 USACO]Jersey Politics 牛的政治

★▲排个序，最小的k个为一组，然后剩余的随机化调整（此题BZOJ没SPJ，POJ已过）

[BZOJ1670 USACO]Building the Moat 护城河的挖掘

▲裸凸包

[BZOJ1716 USACO]The Fewest Coins 找零钱

★多重背包（学到了单调队列的做法）+无限背包，然后就是确定DP范围了（可以证明是不超过T+v_now^2）（然而写成T+v_now并不会WA）

[BZOJ1718 USACO]Redundant Paths 分离的路径

★▲边双联通缩点——Tarjan，答案就是(度数为1的点+1)/2

[BZOJ1720 USACO]Corral the Cows 奶牛围栏

★二分答案，然后枚举y，对于在y上且r距离内的点扫一遍x

[BZOJ1725 USACO]Corn Fields 牧场的安排

裸状压DP

[BZOJ1728 USACO]Two-Headed Cows 双头牛

★贪心的思想就是从左到右能不矛盾就选，然后就是判断不矛盾的实现了。。。个人是用类似【并查集+路径压缩+维护点至根长度】的做法

[BZOJ1706 USACO]Relays 奶牛接力跑

★倍增Floyd

[BZOJ1710 USACO]Cheappal 廉价回文

可以知道，添加和删除可以互相替换，然后就是\(O(n^2)\)的DP了

[BZOJ1690 USACO]奶牛的旅行

▲最优比率环

[BZOJ1692 USACO]队列变换

某道题的加强版，用SA加速判断子串哪个大哪个小，然后左右端点哪个小选哪个

[BZOJ1693 USACO]Asteroids

裸匈牙利，最小点覆盖=最大匹配

[BZOJ1697 USACO]Cow Sorting 牛排序

居然是置换。。。一个置换内可以那最小的数于其他数交换，也可以把外界最小的一个数拿进来然后换一圈然后在换出去

[BZOJ1231 USACO]Mixup2 混乱的奶牛

状压DP，用个二进制数保存未使用数情况，再加上最末的数，弄个状态转移

[BZOJ1593 USACO]Hotel 旅馆

线段树，每个节点保存左端连续可用房间数、右端连续可用房间数、最大连续可用房间数

[BZOJ1594 USACO]猜数游戏

★首先二分答案，变成判定性问题；然后对于一段需求，先按所猜数从大到小排，对于相同的所猜数，先判定其交集是否被染色，然后把它的并集染色（用线段树）

[BZOJ1595 USACO]人工湖

找个最低处，然后灌水，然后再从两旁找最低处，灌水，重复多次

[BZOJ1597 USACO]土地购买

▲先横纵坐标排下序，排除掉那些被包含的矩阵，然后斜率优化

[BZOJ1604 USACO]Cow Neighborhoods 奶牛的邻居

★▲首先曼哈顿距离转化成max形式，然后横纵坐标排序，横坐标弄个大小为C的区间扫一遍，新加点就在区间中找纵坐标绝对之差最小的两个凑成一团（需要用到STL的multiset

[BZOJ1605 USACO]Crisis on the Farm 牧场危机

弄成DP，状态F(x,y,c)表示移动c次时横纵坐标变化量的最优值（顺便储存转移方向

[BZOJ1581 USACO]Transmission Delay 传输谍延时

★DP，状态F(x,y)表示还有x个1和y个0没用，转移的时候判断是否合法，要求第K大串所以要保存转移方向

[BZOJ1229 USACO]Toy 玩具

▲★小数据可以网络流，然后我们会发现假如设F(x)为只买x条毛巾后的花费，我们会发现F(x)事实上是个凹函数，所以三分找最低点。对于单个F(x)的计算，先找慢洗的，没就找快洗用，没就找新的用，再找不到就不合法了。

[BZOJ2198 USACO]瓶颈

★★首先每个点的存储量是一个凸函数，然后求出哪些点哪个时候下降为0（会下降的点满足入不敷出）然后就把这个点删去。

[BZOJ3826 USACO]Cow Jog

★尝试把题目看成最长上升子序列

[BZOJ2679 USACO]Balanced Cow Subsets

★★把所有数分成两坨，然后求出这两坨数的所有子集以及偏差值，然后在合到一起计算答案。

[BZOJ2590 USACO]Cow Coupons

★贪心，先用优惠劵买，然后有两种操作：不用优惠劵买 and 把用优惠劵买了的东西补钱退回一张优惠劵再拿去用掉，怎么买便宜就怎么买

[BZOJ3050 USACO]Seating

线段树裸题

[BZOJ3049 USACO]Island Travels

首先求联通块，然后求联通块之间的距离，然后求哈弗曼路

[BZOJ3061 USACO]Partitioning the Farm

★先求出横向划分方案，然后纵向弄DP

[BZOJ3310 USACO]Empty Stalls

可以弄个类似并查集的东西加速找0，或者先叠成一堆，然后不断往右扔，扫个两遍就没问题了

[BZOJ3940 USACO]Censoring

建AC自动机，然后把原串扔上去跑，遇到串就删，保留自动机上的历史当前指针，顺便除了Fail边还要加个移动方向记录（数据比较神

[BZOJ4098 USACO]Palindromic Paths

就是DP，从左上和右下朝中间走，然后滚动数组维护

[BZOJ3312 USACO]No Change

状压DP，状态定义成F[S]，表示使用了S状态的硬币最多能买的物品件数

[BZOJ3446 USACO]Cow Decathlon

按技能顺序安排，设S为已学习技能奶牛集合，F[S]表示最多得分

[BZOJ4094 USACO]Optimal Milking

★线段树维护每个区间的四个值（两段随意，左端不取，右端不取，左右不取）

[BZOJ3887 USACO]Grass Cownoisseur

★Tarjan缩点后，从点1正向反向dfs后每条边都取反看看最长环

[BZOJ4095 USACO]The Bessie Shuffle

可以发现前面M个是不固定的，后面M个也是，然而中间都是连续递增的，就变成找循环节+模拟的题了

[BZOJ3477 USACO]Sabotage

二分答案，judge函数就每个数减去平均数，然后看一下有没有前缀+后缀>=0

[BZOJ3886 USACO]Moovie Mooving

状压，然后贪心选取能看的最后一场电影

[BZOJ1743 USACO]Walk the Talk

对官方List打表，然后先预处理出以每个点为起点能走出来的长度1、2的串的方案数，然后枚举两个点作为第一次和第二次走的地方，然后找

[BZOJ1695 USACO]Walk the Talk

双倍经验

[BZOJ1694 USACO]Grazing on the Run

双倍经验*2

[BZOJ3430 USACO]Ski Course Rating

★像MST那样用并查集维护，当大小不小于T的时候更新答案