USACO比赛题泛刷

时间:2024-01-15 11:29:20

随时可能弃坑。
因为不知道最近要刷啥所以就决定刷下usaco。
优先级排在学习新算法和打比赛之后。
仅有一句话题解。难一点的可能有代码。
优先级是Gold>Silver。Platinum刷不动...(可能有一两道?)

2015 Feb Gold

BZOJ3939. [Usaco2015 Feb]Cow Hopscotch

这题洛谷数据过水,\(O(n^4)\)的dp跑的飞快。。。所以建议在bzoj写。
但是还是要考虑一下4次方的dp的...其实就是强行枚举转移点,我们可以试着维护前缀和,那么只要倒序枚举m,即有\(f[i][j]=sum[i-1][j-1]\)了。
但是注意到\(sum[i-1][j-1]\)包含了不能转移的情况,发现相同情况最多\(750*750\)种,所以可以拿\(750*750\)个线段树动态开点维护一下就完事了。
两者相减即为答案,注意第二层要倒序枚举
当然也是可以cdq分治的。可是我还没学...

2017 Jan Platinum

BZOJ4756. [Usaco2017 Jan]Promotion Counting

想了几种做法...
主席树\(O(nlogn)\),线段树合并\(O(nlogn)\),分块\(O(n\sqrt{n}log(\sqrt{n}))\),然而都懒得写...
然后就写了一个莫队+BIT。\(O(nsqrt{n}logn)\)。离散化一下就行了...
就是把dfs序爬下来,顺便记录一下siz,那么一个节点的子树在dfs上就是\([dfn_x,dfn_x+siz_x-1]\),那就用莫队维护一下,每次移动指针对应的在bit里面操作就好了...
然而在树上直接BIT求逆序对真的没看题解之前不会写(把之前答案删了处理完子树再加上去,这个真的没想到)。

2016 Open Gold

LuoguP3145 [USACO16OPEN]分割田地Splitting the Field

简单套路题...按x值排序之后,枚举分割点求个min就好了,维护y轴坐标的区间max和min,这题可以直接\(O(n)\)处理出来,不过我写了个ST表...
然后再按y轴排序再来一遍。但是这个完全重合有点奇怪...我把判断删掉才过了...也可能是我判断写错了吧...
复杂度是\(O(nlogn)\)的。

BZOJ4579. [Usaco2016 Open]Closing the Farm

并查集。
还是挺套路的吧...就是把删边变成连边就好了。
然后考虑怎么判断。对每个集合维护一个siz,每次合并的时候顺便把siz并起来。
然后每次把相邻节点merge起来(要判断那个相邻节点是不是还没连上去)。然后再遍历一次,如果有一个的siz不等于当前总节点数,显然就不连通。
这样复杂度是\(O(nlogn)\)的(只用路径压缩)

LuoguP3146 [USACO16OPEN]248

写了一个不同于其他题解的dp。
\(f[l,r,k]\)表示区间\([l,r]\)合并出\(k\)是否可行。
注意到直接枚举转移的话是\(O(n^4)\)的。考虑优化一下。
因为这样子的dp值是只有0和1的,所以可以拿一个bitset优化一下,就是&一下左右两个子区间然后右移一位就行了。
至于答案可能不需要把整段并起来这个问题,再开一个bitset,每次对得到的区间或以下就好了。
这样就能\(O(\frac{n^4}{w})\)搞过去了。

2017 Jan Gold

LuoguP3608 [USACO17JAN]Balanced Photo平衡的照片

很显然的一道题了...离散一下之后用值域BIT维护一下就行了...复杂度是\(O(nlogn)\)

LuoguP3609 [USACO17JAN]Hoof, Paper, Scissor蹄子剪刀…

简单dp.设\(f[i,j,k]\)表示前i局,换了j次手势,现在是出第k种手势(0-石头 1-剪刀 2-布)
然后写个check函数应付一下不换手势的做法就好了。
分成这轮换手势,这轮不换手势两种转移。(换手势肯定是要换赢的)。
怎么usaco这么喜欢出dp...

2016 Dec Gold

LuoguP3036 [USACO16DEC]Lasers and Mirrors激光和镜子

搜索。挺好想的,就是不好写...
仔细研究一下题目,就可以发现几个性质:最优情况下,每个点肯定只会被访问一次,每条边(指网格)也仅会被访问一次。
所以这样子写个bfs的话是\(O(n)\)的。
实现方式有很多种...,维护3个vis数组,表示这一行/列有没有访问过,以及这个点有没有被访问过。
因为坐标有点大,然后可以发现的是只要是相同行的就能走到,所以可以先离散一波。
然后建两个图,对于每个点,从横坐标向纵坐标连边(另外一个图反着),边权均为1。
然后从起点开始bfs,对于每个点,拓展没有走过的点(这个点的横/纵坐标之一也必须是没走过的。)
分类讨论转移即可。细节好多...反正我是重构了3,4次...

LuoguP2847 [USACO16DEC]Moocast(gold)奶牛广播-金

同poj2349,改改就好了,跑一遍mst取个最大边权平方即可。

LuoguP2848 [USACO16DEC]Cow Checklist奶牛确认单

简单dp。设\(f[i][j][0/1]\)表示目前访问了i头H牛,j头G牛,现在在H牛/G牛处。因为只能顺序访问,所以转移是\(O(nm)\)的,分类讨论一下即可。
答案是\(f[n][m][0]\)。注意初始化为\(f[1][0][0]=0\)

2019 Jan Platinum

LuoguP5202 [USACO19JAN]Redistricting

将\(H\)设为1,\(G\)设为-1,维护一个前缀和。
显而易见的可以设一个\(O(nk)\)的方程:\(f[i] = min\{f[i-j]+[s[i]-s[i-j]<=0]\}(i-j\leq k)\)
考虑优化,用个单调队列或者优先队列其实都可以维护。
单调队列复杂度更优但是难写所以因为太懒我就写了优先队列优化
对堆中每个点储存两个值,dp值和位置。
按dp值升序排序,dp值相同按s[i]升序排序。(因为要求min,把那个式子移项一下就可以知道为什么要按s[i]升序了)。
每次转移时先把距离大于k的点都弹掉(单调性),然后取堆顶(但是不弹出)转移。
这样就可以\(O(nlogk)\)转移了。

2019 Jan Gold

LuoguP5196 [USACO19JAN]Cow Poetry

需要一点思维(套路)的计数dp以及阅读理解能力。
反正我是看了很久的题才看懂题意...
考虑\(f[k][j]\)表示一个长度为k的句子以韵部j结尾。
显然有转移方程\[f[k][c[i]]=\sum{f[k-s[i]][j]}\]
优化一下就是设\[g[k]=\sum{f[k][i]}\]
然后就可以\(f[k][c[i]]=\sum{g[k-s[i]]}\)愉快的\(O(nk)\)转移了。
然后需要一点计数套路...考虑那些需要押韵的行数对答案贡献。
\[ans=\sum{f[K][j]^{cnt[i]}}\](\(cnt[i]\)为需要压这种韵的行数)
其实就是必须放一样的,那么就用排列算一下就可以知道是这个东西(但是没规定要放哪种,所以取个\(\sum\))。
乘法原理把每个ans乘起来就好。
(我感觉这个T1其实是三题里面最难的..?)

LuoguP5200 [USACO19JAN]Sleepy Cow Sorting

想出来一个结论的话就可以挺顺理成章地把后面想出来了。
每头牛最多被移动一次
其实也挺显然的,因为每次只能移动队头。
考虑什么牛不会被移动,其实就是最后面那段递增序列不用移动。从后往前数第一个不递增的数,1~它全都得移动(因为要把前面的移动了才能移动它)。
而又由上面那个结论可以知道,我们可以在移动的过程中顺便维护出它应该在的位置。这个可以用bit解决。
首先对于每个\(j(1\leq i \leq x)\)(x为从后往前数第一个不递增的数),它至少要往后\(x-i\)头牛(这样才能把x扔到前面),然后考虑把它插入到后面那个递增序列的合适位置,即比它小的数有多少个(这个东西用bit可以很方便的维护)。
那这样的效率就是\(O(nlogn)\)的了。

LuoguP5201 [USACO19JAN]Shortcut

因为完全忘记了有最短路树这种东西,对这题一脸懵逼,所以看了一下题解之后赶紧滚回去看了czl的课件...
先跑一遍Dijkstra。
因为题目要求字典序最小,那么枚举起点从小的开始枚举,如果枚举到的这条边的两个端点都没连过,那么就可以扔进最短路树里面(因为枚举顺序,如果连过肯定是被更小点连过了,那么字典序会更小)。
然后思路就很显然了。因为是一棵树,加了一条非树边之后显然子树里面都可以不走中间那段了,维护子树的奶牛数量,答案即为:
\(ans=max\{siz[u]*(edge-T)\}\)

2019 Jan Silver

LuoguP5199 [USACO19JAN]Mountain View

偏思维一点的题。
考虑到是等腰直角三角形,所以下面的左端点就是\(x-y\),右端点就是\(x+y\)。
然后按第一关键字左端点升序排序,第二关键字右端点降序排序求解即可。如果右端点大于之前的所有右端点就累加进答案。
至于为什么我觉得有个题解讲的挺好的。
USACO比赛题泛刷

LuoguP5198 [USACO19JAN]Icy Perimeter

简单爆搜。将联通块划分出来,那么面积就是最大联通块,然后对每个最大联通块取个周长min就好了。

LuoguP5197 [USACO19JAN]Grass Planting

显然答案是max(度数+1)

2017 Dec Gold

BZOJ5140: [Usaco2017 Dec]A Pie for a Pie

最短路+set。
这个显然是个最短路问题...,把每个A中B值为0的作为起点往回跑,B中A值为0的作为起点往回跑。每个\(a_i\)的答案即为它的dis值。
发现边权只有1,所以bfs处理即可。还有一个问题是,边数最大可以到\(n^2\),于是我就不会做了。去看了题解的神仙操作:用两个set来维护。
(尽管数据很水,强行连边也跑的飞快。当然这是后面才知道的不然也不会写set做法了...)
首先将每个可能的终点塞进去队列里面,不可能作为终点的就塞进对应的set里面。
每次在set里面二分出来所有可以走的点松弛,松弛完直接删掉(bfs的最优性。)。
所以答案1~n的dis。无解情况将dis初值赋值为-1即可。
这样复杂度是\(O(nlogn)\)的。

这套其他两题以前做过了。

2018 Feb Gold

BZOJ5195: [Usaco2018 Feb]Directory Traversal

换根dp。
一开始看到这题差点以为是大模拟然后直接跑路了。
现在仔细研究了一下其实就是个板子题。
虽然这题题意也有点奇怪就是了:给一棵树,边权是子节点的字符串的长度+1(对于叶子结点的父亲,没有+1)
然后求以某个点为根的每个叶子结点的路径最小和(根自己选)。
那显然就是个换根dp了。
先一次dfs求出以1为根的情况。
然后转移有点特殊:
\[f[son]=f[fa]-(siz[son]*(len[son]+1))+(tot_{leaf}-siz[son])*3\]
考虑这个式子的意义:以son节点为根,那对于以son的父亲为根来说,肯定就少了到父亲那一段的引用距离。所以减掉,然后以son为根,那么除了son子树内的叶子结点,其他的叶子结点的路径肯定多了一段:"../",所以*3.(siz指该子树内叶子结点的数量)。
复杂度\(O(n)\)

BZOJ5196: [Usaco2018 Feb]Taming the Herd

dp。一开始没想到能dp...搜了题解看到dp两字滚回去思考了一发差不多就想出来了。
因为n<=100所以考虑一个\(O(n^3)\)的dp。
设\(f[i,j,k]\)表示前i头牛 出走了j次 当日的真实天数为k。
那么分类今天有没有出走转移即可。
\[
f[i][j][k] = min\{f[i-1][j][k-1] + (a[i] != k)\}(今天没出走)\\
f[i][j][0] = min\{f[i-1][j-1][k] + (a[i] != 0)\}(今天出走了)
\]

2018Dec Gold

BZOJ5488: [Usaco2018 Dec]Teamwork

简单dp。一开始看错题意了...以为分成k组,每组不超过k,然后写了个\(O(nk)\)的单调队列优化dp...
实际上组数没限制...
所以可以设\(f[i]\)表示到i的最大价值和。用刷表法转移。
\(f[j]=max(f[j],f[i-1]+(j-i+1)*mx)(r-l+1<=k)\)
mx为区间\([i,j]\)的最大值。
复杂度是\(O(nk)\)的。

BZOJ5486: [Usaco2018 Dec]Fine Dining

分层图啥都能干.jpg
考虑设\(d[i][0]\)表示从n开始走到i的最短路,\(d[i][1]\)表示从n开始走到i经过一个草堆的最短路。
那么Dijkstra跑一发分层图就好了。也没啥细节。注意分层图分类别分少了就好。

BZOJ5487: [Usaco2018 Dec]Cowpatibility

正解是容斥(然而我并不会,只会bitset优化暴力,去找题解学习了一下容斥做法)。
不过bzoj好像调了时限,然后我现在网上找到的所有容斥题解都TLE了(因为网上的题解都用了string,换成hash才能过)。
容斥做法:
显然转化为\(n(n-1)/2-\)和谐对数。
然后和谐对数就5种情况:1个一样的,2个一样的,3个一样的,4个一样的,5个一样的。
用经典的容斥式子:
\[
ans=\sum_{i=1}^5f(i)*(-1)^i
\]
\(f(i)\)为一样的对数的个数。
那么\(2^5\)枚举所有取法,容斥一遍即可。
用bitset优化一下暴力也跑的飞快,就慢了几百ms。复杂度是小常数的\(O(\frac{n^2logn}{w})\)(要开map不然存不下,或者可以分块求答案就不用开map)。
代码的话戳这里

2017Open Gold

BZOJ4779 [Usaco2017 Open]Bovine Genomics

https://www.cnblogs.com/henry-1202/p/10631415.html

BZOJ4780 [Usaco2017 Open]Modern Art 2

这题看了题解...
考虑什么情况会是无解?显然就是两条线段不包含而又相交。
用栈来维护。每次遇到一个新的颜色(这种颜色第一次出现)就入栈。如果到了最后一次出现的地方就弹出。
那么如果中间有一次遇到一个top和当前颜色不同的,肯定就无解了(如果是包含的,它就会入栈了,没入栈说明一定是相交且不包含。)。
答案就是top的最大值。(因为每次涂色区域不能相交)
注意0是不涂色。所以不用管它。

2017Open Silver

BZOJ4781 [Usaco2017 Open]Paired Up

模拟。两个指针扫一扫即可。

BZOJ4782 [Usaco2017 Open]Bovine Genomics

枚举三元组。用个桶判三元组在A出现过没有即可。一开始看错题意了...

BZOJ4783 [Usaco2017 Open]Where

爆搜。调了1h多调到心态有点炸...
\(O(n^4)\)枚举矩形。dfs判定。可以先不管覆盖条件,把所有符合条件的矩形找出来,最后\(O(n^2)\)去个重。
大概80多行...