NanoApe's Blog

既是咸鱼又是辣鸡

【Plan B】#5

NanoApe posted @ 2015年8月13日 00:19 in 蒟蒻不做题提前退役 , 1132 阅读

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的时候更新答案


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter