USACO
P8099 [USACO22JAN] Minimizing Haybales P
> $n$ 个草垛排成一排，第 $i$ 个的高度为 $h_i$，两个草垛 $i, j$ 之间能够交换当且仅当 $|h_i - h_j| \le k$，求交换任意次后字典序最小的草垛排列。 $n, k \le 10^5, h_i \le 10 ^ 9$。 一道古老的湖北省内测试题。 我们注意到对于任意 ......
P4826 [USACO15FEB] Superbull S题解
#Superbull S题解 ###[题目传送门(可点击)](https://www.luogu.com.cn/problem/P4826) #题面 ##题目描述 $Bessie$和她的朋友们正在一年一度的$Superbull$锦标赛中打球，而$Farmer$ $John$负责让比赛尽可能激动人心。 ......
[刷题笔记] Luogu P1466 [USACO2.2] 集合 Subset Sums
[Problem](https://www.luogu.com.cn/problem/P1466) ### Description 有一个长度为$n$的数组为$1-n$,求有多少种选择方案使得选择数之和等于序列和的一半 ### Solution 题面翻译成这样是不是就好做了？ 首先，序列和的一半我们 ......
[刷题笔记] Luogu P2340 [USACO03FALL] Cow Exhibition G
[Problem](https://www.luogu.com.cn/problem/P2340) ### Solution 乍看可能没有思路。我们注意到本题是牵扯到一头奶牛选or不选的问题，非常自然地想到**01背包**。 接下来我们就尝试将本题背景转换成01背包问题。 我们可以将智商转换成容量， ......
【Usaco2014Open银组】坑爹的GPS (gpsdual) 题解
[洛谷传送门](https://www.luogu.com.cn/problem/P3106) ## 1.题意简述 有一张有向图，两种 $GPS$ 的 联通情况相同，但连边的路径长度不同。现在在 $1$ 到 $n$ 中找一条路，使其与两个 $GPS$ 的最短路差异最小。 ## 2.样例解释 ```c ......
我要开始做USACO的DP以对抗智力下降
P6205 [USACO06JAN] Dollar Dayz S - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) 题解：完全背包,__int128，傻逼题 ``` #include using namespace std; __int128 f[10001]; void write ......
[USACO13DEC] The Bessie Shuffle S 洗牌 题解
提供一种思路，可以做到$O(n)$。\ 目前是全`OJ`最优解，跑到了`79ms`。 `update 2023.07.29` 完工，期望无bug（暑假快乐吖o(*￣▽￣*)ブ）\ `update 2023.07.27` ~~（要原题检测了，先占个坑，有时间再补）~~ ## 原题大意 [P3095 [ ......
P9017 [USACO23JAN] Lights Off G 题解
## Description 给定正整数 $N$，和两个长为 $N$ 的 $01$ 序列 $a$ 和 $b$。定义一次操作为： 1. 将 $b$ 序列中的一个值翻转（即 $0$ 变成 $1$，$1$ 变成 $0$，下同）。 2. 对于 $b$ 序列中每个值为 $1$ 的位置，将 $a$ 序列中对应位 ......
[USACO13DEC] The Bessie Shuffle S
# [USACO13DEC] The Bessie Shuffle S [TOC] [P3095 [USACO13DEC\] The Bessie Shuffle S - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)](https://www.luogu.com.cn/problem ......
洛谷 P2894 [USACO08FEB] Hotel G 题解
题目链接 P2894 [USACO08FEB] Hotel G - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) 分析 考虑用线段树维护区间信息 维护sum（最大连续空房间数） 如何合并？ sum1为max（sum2，sum3）（1的两个子区间） 但我们发现若区间为100 001（0 ......
【USACO OPEN12铜组】岛屿
# 【USACO OPEN12铜组】岛屿 [TOC] [2014. 岛 - AcWing题库](https://www.acwing.com/problem/content/description/2016/) ## 题目描述 每当下雨时，农夫约翰的田地总是被洪水淹没。 由于田地不是完全水平的，所以 ......
题解 P2903 【[USACO08MAR]The Loathesome Hay Baler S】
posted on 2021-05-03 20:50:49 | under 题解 | [source](https://www.luogu.com.cn/blog/_post/331434) 首先输入，记录一下哪个齿轮的位置在 $(0,0)$，哪个在 $(x_t,y_t)$。 接着，为了避免多次判断 ......
P5095 [USACO12OPEN] Bookshelf S
# P5095 [USACO12OPEN] Bookshelf S [TOC] ## 题目描述 Farmer John 闲来无事的时候总喜欢坐下来看书。这些年来，他一共收集了 $N$ 本书（$1 \leq N \leq 2000$），他打算搭一共新的书架来装这些书。 每本书都有个宽度 $w_i$ 和 ......
USACO23FEB Hungry Cow P
这个涂色很容易让人想到均摊的 set 维护，但是有可能修改同一个位置，不太可做。 同样地，我们考虑只带插入不同位置的情况。 考虑一个线段树做法，直接维护整行格子的权值和以及黑色格子的个数。考虑一个修改 $(i,j)$ 相当于区间覆盖 $[i,k]$ ，其中 $[i,k]$ 中修改前白色格子的数量为 ......
P2900 [USACO08MAR] Land Acquisition G
# P2900 [USACO08MAR] Land Acquisition G ## 题意 Farmer John 准备扩大他的农场，眼前他正在考虑购买 $N$ 块长方形的土地。 如果 FJ 单买一块土地，价格就是土地的面积。但他可以选择并购一组土地，并购的价格为这些土地中最大的长乘以最大的宽。比如 ......
题解 P4955 【[USACO14JAN]Cross Country Skiing S】
posted on 2021-02-27 10:04:32 | under 题解 | [source](https://www.luogu.com.cn/blog/_post/315696) 这道题其实没有绿这么难，只需要二分+搜索就行了。 1. 读入。注意尽量不要用 `scanf` 读入 `boo ......
洛谷 P9020 - [USACO23JAN] Mana Collection P
显然，每个法力池最终能收集到的法力只与这个法力池最终被收集到的时间有关。 对于一组询问 $(s,e)$，假设我们经过了 $k$ 个法力池，我们钦定最终被收集到的时间从后到前分别是 $e=a_1,a_2,\cdots,a_k$，那么最大法力值为 $\sum\limits_{i=1}^kc_{a_i}· ......
P8271 [USACO22OPEN] COW Operations S 奶牛操作
# P8271 [USACO22OPEN] COW Operations S 奶牛操作 [TOC] [P8271 [USACO22OPEN\] COW Operations S - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)](https://www.luogu.com.cn/pr ......
题解 [USACO18JAN] MooTube G
[题目链接](https://www.luogu.com.cn/problem/P4185) 可以发现，对于一个固定的 $k$，所有边权小于 $k$ 的边对答案是没有贡献的，因为一条边的相关性是最小相关性，这也意味着我们不能从 $ using namespace std; #define PII p ......
P5427 [USACO19OPEN] Left Out S
P5427 [USACO19OPEN] Left Out S - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) 你有个01矩阵，每次可翻转一行或一列，问能否使得最后只有一个0或1。其中翻转指1变0，0变1。 做法基本上都是取第一行第一列给他全部翻成0。这个是一定可以办到的。你只需要找 ......
题解 P4183 [USACO18JAN] Cow at Large P
带有小 trick 的点分治。 建议先做完 [弱化版](https://www.luogu.com.cn/problem/P4186) 再看。 假如奶牛在 $u$，那么所需的最少农夫数为 $\sum\limits_{v\in son(u)}[dis(u,v)\ge g_v][dis(u,fa_v) ......
题解 P5426 [USACO19OPEN]Balancing Inversions G
来一篇简单易懂的良心题解。  由于数值不是 $0$ 就是 $1$，我们可以考虑将逆序对的统计方式化简。 以左区间为例，设 $x$ 为 $1$ 的个数，$p_i$ 为第 $i$ ......
[USACO07OPEN] Kill That Cow S(bushi
FJ 丢失了他的一头牛，他决定追回他的牛。已知 FJ 和牛在一条直线上，初始位置分别为 $x$ 和 $y$，假定牛在原地不动。FJ 的行走方式很特别：他每一次可以前进一步、后退一步或者直接走到 $2\times x$ 的位置。计算他至少需要几步追上他的牛。 ......
洛谷P1219 [USACO1.5] 八皇后 Checker Challenge
# 写在前面 我又回来了！ 偷了几天懒，还认识我吗？甭管认识不认识，还是要自我介绍一番：本人是初学c++的初中生，还是个蒟蒻，~~最要命的是没有脑子~~。今天，还请允许我浪费您一点时间，~~叨叨~~上几句。 本题目来自于洛谷，网址https://www.luogu.com.cn/problem/P1 ......
[USACO23OPEN] Pareidolia S
# [USACO23OPEN] Pareidolia S [USACO23OPEN\] Pareidolia S - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)](https://www.luogu.com.cn/problem/P9188) [TOC] ## 题目背景 **Not ......
[USACO23OPEN] Field Day S 田野日 - 动态规划
提供一个简单的 DP 思路。 ## 0x01 重点信息 可以先找出题目中的一些重点信息。 - 字符串中只有 $G$ 与 $H$。 - $N$ 很大（$2 \leq N \leq 10^5$），但 $C$ 很小（$1 \leq C \leq 18$）。 ## 0x02 思路 既然字符串中只有 $G$ ......
P8095 [USACO22JAN] Cereal 2 S 谷物早餐
# P8095 [USACO22JAN] Cereal 2 S 谷物早餐 [P8095 [USACO22JAN\] Cereal 2 S - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)](https://www.luogu.com.cn/problem/P8095) [TOC] # ......
P1216 [USACO1.5] [IOI1994]数字三角形
自己的思想：要用逆序，但是某个未知的位置可能存在一个非常大的数，因此不知道如何dp 看题解之后：对于倒数第二行的数，可以算出它们的最优解，依次往上推，第一个数就是整体的最优解，其实本质上可以用隔离意识来看，在搞最后一排时，将前面所有排隔离掉，在处理中间的每一排时，又将其他排隔离掉 接下来写一下代码 ......
P1672 [USACO05FEB] Feed Accounting S 题解
给 $c$ 个区间表示牛吃草的时间段，每头牛每天吃 $1$ 千克，问距今天（即运来饲料 $f_2$ 千克的时间）最近的送饲料 $f_1$ 千克的时间是什么时候？ ......