【Plan B】#5
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的时候更新答案