USACO
P3047 [USACO12FEB] Nearby Cows G
```cpp #include #include using namespace std; const int N = 100010,M = 30; int n,m; int w[N]; vector g[N]; int f[N][M],ans[N][M]; void DP1 (int u,int ......
P3134 [USACO16JAN] Lights Out G 关灯
# P3134 [USACO16JAN] Lights Out G 关灯 [TOC] [题目传送门洛谷链接](https://www.luogu.com.cn/problem/P3134) # [USACO16JAN] Lights Out G ## 题面翻译 ### 题目描述 Farmer Joh ......
P8903 [USACO22DEC] Bribing Friends G 看电影
# P8903 [USACO22DEC] Bribing Friends G 看电影 [TOC] [题目传送门](https://www.luogu.com.cn/problem/P8903) ## 题目描述 Bessie 想要观看纪录片:奶牛基因组学,但她不想一个人去。不幸的是,她的朋友们没有足够 ......
P3133 [USACO16JAN] Radio Contact G 无线电通话
# P3133 [USACO16JAN] Radio Contact G 无线电通话 [TOC] [题目传送门](https://www.luogu.com.cn/problem/P3133) ## [USACO16JAN] Radio Contact G ### 题目描述 Farmer John ......
【题解】#105. 「USACO1.3」Ski Course Design 题解(2023-07-01更新)
# #105. 「USACO1.3」Ski Course Design 题解 ## **[题目传送门](https://qoj.fzoi.top/problem/105)** **欢迎大家指出错误并联系这个蒟蒻** ## 更新日志 - **2023-02-01 17:20 文章完成** - **20 ......
【题解】#373. 「USACO1.1」Friday the Thirteenth 题解(2023-07-01更新)
# #373. 「USACO1.1」Friday the Thirteenth 题解 ## **[题目传送门](https://qoj.fzoi.top/problem/373)** **欢迎大家指出错误并联系这个蒟蒻** ## 更新日志 - **2023-02-01 17:20 文章完成** - ......
动态规划之 附录一:USACO中的背包问题
USACO是USA Computing Olympiad的简称,它组织了很多面向全球的计算机竞赛活动。 USACO Trainng是一个很适合初学者的题库,我认为它的特色是题目质量高,循序渐进,还配有不错的课文和题目分析。其中关于背包问题的那篇课文 (TEXT Knapsack Problems) ......
NC24727 [USACO 2010 Feb G]Slowing down
[题目链接](https://ac.nowcoder.com/acm/problem/24727) # 题目 **题目描述** Every day each of Farmer John's N (1 using namespace std; using ll = long long; templa ......
NC24141 [USACO 2011 Dec G]Grass Planting
[题目链接](https://ac.nowcoder.com/acm/problem/24141) # 题目 **题目描述** Farmer John has N barren pastures (2 using namespace std; using ll = long long; struct ......
NC24048 [USACO 2017 Jan P]Promotion Counting
[题目链接](https://ac.nowcoder.com/acm/problem/24048) # 题目 **题目描述** The cows have once again tried to form a startup company, failing to remember from pas ......
[USACO18DEC]Balance Beam P
# [USACO18DEC]Balance Beam P 热爱卡精度的你,为什么分数不取模? 既然不去模,那么拿到这个题先想想能不能乱搞过去。 设 $f_{i,j}$ 表示 $i$ 点出发至多走 $j$ 次的最优期望报酬。当 $j \rightarrow +\infty$ 时视为答案。转移为 $$ ......
[USACO1.3]混合牛奶 Mixing Milk
# [[USACO1.3]混合牛奶 Mixing Milk](https://www.luogu.com.cn/problem/P1208 "[USACO1.3]混合牛奶 Mixing Milk") ## 题目描述 由于乳制品产业利润很低,所以降低原材料(牛奶)价格就变得十分重要。帮助 Marry ......
Luogu P6191 [USACO09FEB]Bulls And Cows S (牡牛和牝牛)
# [USACO09FEB]Bulls And Cows S ## 题目背景 一年一度的展会要来临了,Farmer John 想要把 $N$($1 \leq N \leq 100,000$)只奶牛和公牛安排在单独的一行中。 John 发现最近公牛们非常好斗;假如两只公牛在这一行中靠的太近,他们就会吵 ......
P2860 [USACO06JAN]Redundant Paths G 题解 ratjan边双连通分量
题目链接:[https://www.luogu.com.cn/problem/P2860](https://www.luogu.com.cn/problem/P2860) 题目大意: 给定一个无向连通图,求至少加几条边,能使其变成一个边双连通图。 解题思路: 边双连通分量缩点后计算度数为 $1$ 的 ......
[USACO06FEB]Treats for the Cows G/S
# [[USACO06FEB]Treats for the Cows G/S](https://www.luogu.com.cn/problem/P2858 "[USACO06FEB]Treats for the Cows G/S") ## 题目描述 FJ has purchased N (1 us ......
Luogu P4824 [USACO15FEB] Censoring S
# [USACO15FEB] Censoring S ## 题面翻译 Farmer John为他的奶牛们订阅了Good Hooveskeeping杂志,因此他们在谷仓等待挤奶期间,可以有足够的文章可供阅读。不幸的是,最新一期的文章包含一篇关于如何烹制完美牛排的不恰当的文章,FJ不愿让他的奶牛们看到这 ......
Bull in a China Shop USACO - 640
题目链接:http://www.usaco.org/index.php?page=viewproblem2&cpid=640&lang=en 题意:有一个完整的图形被切分成k个碎片。在k个碎片中,一定有2个碎片可以正好拼成完整的图形。拼接时只能横向竖向移动碎片,并且碎片不能重叠。按顺序输出可以拼出完 ......
算法刷题记录:P1518 [USACO2.4]两只塔姆沃斯牛 The Tamworth Two
###题目链接: https://www.luogu.com.cn/problem/P1518 ###题目分析 这道模拟题很典型了,给定了一个**固定的移动方式,去模拟即可**, 该题说:如果牛和农夫永远不会相遇输出0,我没想到很好的方法,不推荐我这样的写法。 算勉强AC吧。 ###AC代码 ``` ......
Field Reduction USACO - 641
题目链接:http://www.usaco.org/index.php?page=viewproblem2&cpid=641&lang=en 题意:有n (3<n<50000) 头牛 你需要给这n头牛建造围栏。坐标范围1-40,000。围栏的面积越小越好。你需要删除1头牛来减小围栏面积 思路:1. ......
[刷题笔记] Luogu P3073 [USACO13FEB]Tractor S
[Problem](https://www.luogu.com.cn/problem/P3073) ### Solution 和[汽车拉力比赛](https://www.cnblogs.com/SXqwq/p/17455232.html)差不多,思路都是二分,二分$d$,但是汽车拉力比赛从一个路标开 ......
Luogu P3605 [USACO17JAN]Promotion Counting P
# [USACO17JAN]Promotion Counting P ## 题目描述 The cows have once again tried to form a startup company, failing to remember from past experience that cow ......
P2973 [USACO10HOL] Driving Out the Piggies G 臭气弹
[题目链接](https://www.luogu.com.cn/problem/P2973 "题目链接") 题目: 奶牛们建立了一个随机化的臭气炸弹来驱逐猪猡。猪猡的文明包含1到N (2 using namespace std; const int maxn=350; const int eps=1 ......
P3087 [USACO13NOV]Farmer John has no Large Brown Cow S
正解像是康托展开之类的?但是蒟蒻不会,所以用了一堆 STL。 对于每一列的字符串,按照字典序给它们编号。这样每一行的形容词串就变成了一堆数字。 设共有 $s$ 列,第 $i$ 列共有 $b_i$ 个不同的形容词,那么实际上每一行就是一个“第 $i$ 位是 $b_i$ 进制”的数。设第 $j$ 行的第 ......
[USACO07JAN] Balanced Lineup G(树状数组)
### 题目大意: 给出长度为n的数组和q个询问,每次问(x,y)区间内最大值和最小值的差是多少 ### 思路: 1.适合用树状数组做此区间求值,首先要明白普通的树状数组的tree[x]表示区间(x-(x&-x),x]的区间和,现在改为求最值,则tree[x]表示为区间(x-(x&-x),x]的最值 ......
P3047 [USACO12FEB]Nearby Cows G 题解
### P3047 [USACO12FEB]Nearby Cows G #### 题目描述 ![image](https://img2023.cnblogs.com/blog/2940791/202306/2940791-20230604112054638-377143904.png) #### 思 ......
(输出路径搜索)[USACO06OCT] Cows on Skates G
题目描述 本题使用 Special Judge。 Farmer John 把农场划分为了一个 r 行 c 列的矩阵,并发现奶牛们无法通过其中一些区域。此刻,Bessie 位于坐标为 (1,1)(1,1) 的区域,并想到坐标为 (,)(r,c) 的牛棚享用晚餐。她知道,以她所在的区域为起点,每次移动至 ......
P1545 [USACO04DEC] Dividing the Path G 题解
丢一发好理解又好写的线段树优化dp。 [题目传送门](https://www.luogu.com.cn/problem/P1545 "题目传送门") ### 简要题意 给定一个长为 $l$ 的线段,求出尽量少的不相交区间覆盖整段线段,要求题目给的所有子区间只被 $1$ 个区间覆盖。 ### 分析 显 ......
[USACO09MAR]Cow Frisbee Team S
# [[USACO09MAR]Cow Frisbee Team S](https://www.luogu.com.cn/problem/P2946 "[USACO09MAR]Cow Frisbee Team S") ## 题目描述 老唐最近迷上了飞盘,约翰想和他一起玩,于是打算从他家的 $N$ 头奶 ......
[USACO08NOV]Buying Hay S
# [[USACO08NOV]Buying Hay S](https://www.luogu.com.cn/problem/P2918 "[USACO08NOV]Buying Hay S") ## 题目描述 Farmer John is running out of supplies and nee ......