NanoApe's Blog

既是咸鱼又是辣鸡

【Plan B】#4

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

Gold第二波。

现在已完成:

50/50

[BZOJ1232 USACO]Cheer 安慰奶牛

把边权改成边长*2+两端耗时,然后MST,最后再加上耗时最小的点(作为起点

[BZOJ2580 USACO]Video Game

AC自动机上跑DP(Fail边向下传递结尾字符串数

[BZOJ2582 USACO]Bovine Alliance

★每个联通块单独考虑,再用乘法原理;在联通块内,若是E=V则有两种方案,若是E>V则不可能分配,若是E=V-1则有V种方案。可以用并查集实现(然而加完所有点要来次查找根操作)

[BZOJ3048 USACO]Cow Lineup

弄个队列扫描一遍,队列内不能有超过K+1种不同的数,若超过则向右移动左端点,答案容易维护

[BZOJ3074 USACO]The Cow Run

区间来回DP(双倍经验BZOJ1742

[BZOJ2620 USACO]Haybale Restacking

★环状移动石子,假设每个位置的石子都是从左边拿的,求出应拿石子K,ans就是K中每个数与其中位数的绝对值差之和。

[BZOJ3075 USACO]Necklace

DP,F[a,b]表示选到第a个且能匹配b格的最小删除数。每一格决策为选和不选,转移要借助KMP

[BZOJ2621 USACO]Cows in a Skyscraper

给N个数,求最小子集划分,使得每个子集的总和不超过限定。搜索可以玩(最优性剪枝),从大到小选能更快。

[BZOJ3126 USACO]Photo

★一道神题,DP可以弄,关键是决策的范围L(全部扫过的区间的最大左端坐标)和R(扫一半的区间的最小左端坐标-1)

[BZOJ1711 USACO]Dingin 吃饭

★网络流建模:三分图。将牛拆成a和A,然后S连Food连a连A连Drink连T(流量都为1)

[BZOJ1708 USACO]Money 奶牛的硬币

DP

[BZOJ1709 USACO]Super Paintball 超级弹珠

统计一下格子本身和横竖两斜的敌人个数,然后枚举站位,若横竖两斜的敌人个数减去格子本身个数*3=总敌人数就可以(容斥)

[BZOJ1707 USACO]Tanning 分配防晒霜

贪心,防晒霜从小到大分,优先分给右端最小的奶牛(网络流可做

[BZOJ1712 USACO]Summing Sums 加密

★矩阵快速幂,可以N^2的矩阵(TLE)正解是2*2的矩阵然后每个数对于得到的矩阵进行计算

[BZOJ1698 USACO]Lilypad Pond 荷叶池塘

类似最短路,先处理每个0能到达其他哪些0(默认起点和终点为0,答案减一下就行)然后就直接求BFS+最短路+方案数

[BZOJ1699 USACO]Balanced Lineup 排队

裸线段树

[BZOJ1700 USACO]Problem Solving 解题

DP,F[i,j]表示第i月解完前j道题后剩余的最多金钱

[BZOJ1696 USACO]Building A New Barn 新牛舍

可以知道中位数满足曼哈顿距离最短要求,然后就按照【不能与现有点重合】【保证现有点不相邻】做就行

[BZOJ1726 USACO]Roadblocks 第二短路

处理出最短路树,可以知道第二短路只经过一条非树边

[BZOJ1717 USACO]Milk Patterns 产奶的模式

正解用后缀数组+分组讨论,要简单的话二分答案+Hash解决

[BZOJ1724 USACO]Fence Repair 切割木板

反过来就是合并果子

[BZOJ1727 USACO]The Milk Queue 挤奶队列

★DP,保证相邻两数min(A1, B2)<min(A2, B1)(A在前B在后),排序后模拟

[BZOJ1702 USACO]Gold Balanced Lineup 平衡的队列

★F[i,j]表示前j牛中特色i的个数比特色i+1多多少,然后就可以Hash大法了

[BZOJ1703 USACO]Ranking the Cows 奶牛排名

★答案就是传递闭包中未确认点对数,然后由于是DAG就可以DFS求传递闭包了(Bitset优化)

[BZOJ1704 USACO]Face The Right Way 自动转身机

O(n)枚举转身长度,从左到右若需转身就转身,O(1)判定前k-1格的转身次数和需不需要转身,O(n^2)复杂度

[BZOJ1663 USACO]赶集

多加个0点表示起点,可拿奖品的边就连,求个最长路

[BZOJ1740 USACO]Yogurt factory 奶酪工厂

傻叉贪心

[BZOJ1742 USACO]Grazing on the Run 边跑边吃草

双倍经验题(区间来回DP

[BZOJ1741 USACO]Asteroids 穿越小行星群

转成二分图求最小覆盖

[BZOJ1739 USACO]Space Elevator 太空电梯

按限制高度从低到高做多次背包,Bitset优化

[BZOJ1738 USACO]Ombrophobic Bovines 发抖的牛

首先用Flody求任意两点最短路,然后二分答案

[BZOJ1737 USACO]Naptime 午睡时间

★环形DP神题,分两种情况DP两次(未越界和越界)

[BZOJ1736 USACO]The Wedding Juicer 婚宴的榨汁机

MC更新方块思想

[BZOJ1735 USACO]Muddy Fields 泥泞的牧场

★进化二分图匹配,把木板作点,泥地作边

[BZOJ1734 USACO]Aggressive cows 愤怒的牛

二分答案+贪心选

[BZOJ1733 USACO]Secret Milking Machine 神秘的挤奶机

二分答案+网络流

[BZOJ1731 USACO]Layout 排队布局

▲差分约束系统

[BZOJ1730 USACO]Barn Expansion 牛棚扩张

★扫描法,判断相同方向的边与边是否有交集

[BZOJ1666 USACO]Another Cow Number Game 奶牛的数字游戏

。。。

[BZOJ1668 USACO]Cow Pie Treasures 馅饼里的财富

裸DP,边界问题要处理好

[BZOJ1669 USACO]Hungry Cows 饥饿的奶牛

裸最长上升子序列

[BZOJ1715 USACO]Wormholes 虫洞

裸判负环(一开始想到要是负环不经过起点呢,后来看到了双向边。。。)

[BZOJ3445 USACO]Roadblock

最短路后每条位于最短路网上面的边都加倍玩一下

[BZOJ1755 USACO]Bank Interest

Gold画风不对系列

[BZOJ1754 USACO]Bull Math

Gold画风不对系列*2

[BZOJ1753 USACO]Who's in the Middle

Gold画风不对系列*3

[BZOJ1752 USACO]Til the Cows Come Home

Gold画风不对系列*4(裸最短路)

[BZOJ1751 USACO]Lake Counting

Gold画风不对系列*5(裸FloodFill)

[BZOJ1750 USACO]Apple Catching

Gold画风不对系列……嗯这个还不会(一眼DP)

[BZOJ1642 USACO]Milking Time 挤奶时间

区段才 $1000$,那么以区段作为点DP,而不是以时间作为点DP(当然要是离散化也是可以的)


登录 *


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