Gold第一波。

现在已完成：

50/50

[BZOJ1776 USACO]Cowpol 奶牛政坛

一棵树，每个结点有颜色，求同种颜色中相距最远的点对的距离。

相距最远的其中一个肯定是最深的，设为x，然后就枚举其他同颜色的点和x的距离，取最大值。

[BZOJ1777 USACO]Rocks 石头木头

树上移子问题。

距离根为偶数的不用理（Nim阶梯），距离为奇数的求Sg函数（其实就是\(\%(L+1)\)），然后xor一遍，修改也是。

[BZOJ1778 USACO]Dotp 驱逐猪猡

有一幅无向图，炸弹有\(P/Q\)的几率爆炸，其余就会随机地移动至其他点（概率平均）。求每个点的期望爆炸概率。

设\(S=[1,0,0,0...]\)，T为转移概率矩阵，则第一秒的爆炸概率为\(\frac PQS\)，第二秒爆炸概率为\(\frac PQST\)，第三秒爆炸概率为\(\frac PQST^2\)……同类项合并得到\(\frac PQS[I+T+T^2+T^3+...]=\frac PQS{I-T^∞\over I-T}=\frac PQS{I \over I-T}\)，其中I是单位矩阵。后面我们直接求出就是I-T的转置矩阵的第一行然后乘上\(\frac PQS\)就是答案了。（转置矩阵求法：左边原矩阵，右边单位矩阵，通过行与行的相加相减使得左边的矩阵变成单位矩阵，右边就是转置矩阵了）

[BZOJ1782 USACO]Slowdown 慢慢游

裸链剖

[BZOJ2060 USACO]Visiting Cows 拜访奶牛

简单·树DP

[BZOJ1914 USACO]Triangle Counting 数三角形

有\(n\)的点，求其构成的三角形中有多少个包含原点

用总三角形数减去不包含原点的三角形。极角排序后扫一圈

[BZOJ1827 USACO]Gather 奶牛大集会

一般·树DP

[BZOJ2501 USACO]Soda Machine

从左到右扫一遍，区间可以看成两种事件（进入和退出），然后就坐标排序扫

[BZOJ3409 USACO]Barn Echoes 牛棚回声

两个字符串，各自在对方的KMP中走一遍

[BZOJ2058 USACO]Cow Photographs

★先求逆序对对数，然后把1改成n+1，2改成n+2……改的时候维护逆序对对数

[BZOJ3407 USACO]Bessie's Weight Problem 贝茜的体重问题

背包DP

[BZOJ3406 USACO]Invasion of the Milkweed 乳草的入侵

BFS

[BZOJ1783 USACO]Taking Turns

★博弈论，每个位置设先手能得最大分数和后手能得最大分数两个状态进行转移。

[BZOJ1828 USACO]Balloc 农场分配

★区间覆盖加强版，同样也是右端点从小到大排序，一个个判断可不可以放置（判断用线段树）

[BZOJ1780 USACO]Corral 覆盖牛棚

★总的是环状，求最少需要几个区间能覆盖全部。

首先，贪心可得我们要使下一个区间的右端越远越好。预处理出每个区间的下一个衔接区间，然后预处理出每个区间不断衔接第一次到达环的末端（也就是N）的区间，然后扫一遍（扫的时候具体看代码）

[BZOJ1916 USACO]冲浪

★设状态F(x,y)表示在x点且还有可能有y次失去控制的情况下的最大值，然后结合博弈论的最大最小，在dfs的时候统计。

[BZOJ1785 USACO]Telephone

贪心可得我们子树假如有超过一个点未配对的话就在满足限制的情况下配对，然后剩余的可配对点（有限制）就转移到父亲。一个dfs

[BZOJ1915 USACO]奶牛的跳格子游戏

★一个跳回去的和一个跳过去的可以组成一个组织，然后相邻的组织之间有正权的就跳。接着DP+单调优化。

[BZOJ2099 USACO]Letter 恐吓信

报纸弄个SA，然后二分查找最长前缀匹配长度（贪心可得）

[BZOJ2097 USACO]Exercise 奶牛健美操

二分答案，然后dfs的时候判断+删边

[BZOJ2059 USACO]Buying Feed 购买饲料

设F(x,y)表示在第x个商店共买了y件的最小费用，然后DP+单调优化

[BZOJ2442 USACO]修剪草坪

转化成使不选的点的价值最小，然后就一边扫一边堆优化

[BZOJ2274 USACO]Generic Cow Protests

求出前缀和后求不下降子序列个数，然后就一边扫一边BIT优化

[BZOJ2272 USACO]Cowlphabet 奶牛文字

可以看出来词素是一条路，连接两个字母，然后就记忆化搜索

[BZOJ2197 USACO]Tree Decoration

dfs，假如当前根未满足要求，就另其子树的最小花费的点买

[BZOJ2196 USACO]Brownie Slicing

二分答案，然后行的贪心（能满足就割行）和列的贪心（能满足就割列），每次\(O(n*m)\)扫一遍

[BZOJ3408 USACO]Heat Wave 热浪

妈呀Gold都有裸SPFA

[BZOJ1774 USACO]Toll 过路费

★建两个距离数组，一个不考虑点过路费，一个考虑。Floyd中要先枚举中间点k，我们可以先按照点权从小到大排序，那么在计算最大点权的时候只要考虑i,j,k三者中点权的最大值即可。

[BZOJ1772 USACO]Rescue 拯救奶牛贝希

简单·数学推导题

[BZOJ1775 USACO]Vidgame 电视游戏问题

附带产品背包DP

[BZOJ1770 USACO]Lights 灯

▲高斯消元解xor方程组（高斯消元少写，这题的代码应该是高斯消元的正确姿势）

[BZOJ1584 USACO]Cleaning Up 打扫卫生

★可以看出每段的不同个数不能超过\(\sqrt{n}\)，然后扫一遍的时候维护B[i]（表示B[i]至now的不同个数为i，B[i]要尽量小）（像一个游标卡尺右移）

[BZOJ1583 USACO]Moon Mooing 哞哞叫

★可以看出这是个递增函数，所以不排序。设当前以找到\(A\)个答案，则保存\(F1(A[])\)和\(F2(A[])\)，然后从其中找到第一个最小没出现过的数加入A，重复N次（具体细节看代码）

[BZOJ1585 USACO]Earthquake Damage 2 地震伤害

▲最小割（Sap为常用算法，标注）

[BZOJ1582 USACO]Holiday Painting 节日画画

用个线段树维护一下，先求出每个区间的0和1的个数，然后区间修改就可以用了（Bitset不支持整数操作QAQ例如减法加法）（稍微有点卡空间）

[BZOJ1577 USACO]Fair Shuttle 庙会捷运

其实又是区间覆盖的变种，右端点从左到右排序（贪心）然后用线段树判断能放多少个人下去

[BZOJ1576 USACO]Travel 安全路经

★求出最短路树之后，对于非树边(x,y,D)，我们可以更新\(x-y\)的路径上的所有点（除了\(Lca(x,y)\)），点a有可能被更新成\(d[x]+D+d[y]-d[a]\)，然后就链剖+线段树维护每个点的最小值最后减去d[]就是每个点的答案了

[BZOJ1579 USACO]Revamping Trails 道路升级

分层图最短路。题目卡SPFA，加了SLF优化也没用，乖乖写Dij+Heap才能过

[BZOJ1571 USACO]Ski 滑雪课

★首先，对于每次滑雪，能越短越好（在能力范围内），然后每个时间点都有三种决策（不做，培训班，滑雪），然后DP

[BZOJ1572 USACO]Job 工作安排

时间倒序排序，然后在一个时间点上选择价值最大的事去做

[BZOJ1574 USACO]Damage 地震损坏

贪心，与报告的点相连的点都计为损坏，然后看点1不能到达哪些点

[BZOJ1233 USACO]Tower 干草堆

★倒序DP，贪心可知一层能尽量小就小（这DP挺神的）

[BZOJ1575 USACO]Baric 气象牛

DP，\(F[i,j]\)表示前i个数且i有被选中且选了j个的最小误差

[BZOJ1578 USACO]Stock Market 股票市场

★有这样一个事实：一天买入+三天卖出=一天买入+二天卖出+二天买入+三天卖出，所以就相当与每天都在做背包DP了

[BZOJ1598 USACO]牛跑步

类似第K短路的做法

[BZOJ1596 USACO]电话网络

★经典的树贪心问题，具体看代码，Nod4C是加强版

[BZOJ1592 USACO]Making the Grade 路面修整

★可以知道最优方案中的每个数都是原数列出现过的数，设S[i]是原数列（排序过的），F[i,j]表示Ai为Sj时A[1..i]不下降的最小代价。

[BZOJ1590 USACO]Secret Message 秘密信息

要多裸有多裸的Trie

[BZOJ1589 USACO]Trick or Treat on the Farm 采集糖果

基环树大法！

[BZOJ1230 USACO]Lites 开关灯

区间修改线段树

Updata 9.4 00:18

屯题完成！

Updata 9.4 00:41

提交完成！

三图流

Month版（其实整个月才过去了4天

Year版（顺利杀进前30！

总排名（顺利杀进前四页！

突破400道！