USACO

按 \(v\) 从小到大排序，这样可以转化为 \(v_j\times|x_i-x_j|(i<j)\)。 CDQ 分治，返回时按照 \(x\) 从小到大排序。考虑如何计算前一段区间对后一段区间的贡献。假设前一段区间当前扫到 \(i\)，后一段区间当前扫到 \(j\)。 每次拿出最小的计算贡献。如果 \ ......

P1518 [USACO2.4] 两只塔姆沃斯牛 The Tamworth Two 初始思路 利用数字1~4代表方向； 利用两个循环来实现两个角色的行为，通过每一步break实现两个角色的同步。 由于题目本意是同步，而我这实质上是分步（牛在前Farmer John在后），所以用Farmer John ......

[USACO23FEB] Equal Sum Subarrays G 题解 题目链接 \(O(n^5)\) 暴力 显然，如果修改 \(a_i\) 的值，只会影响包含 \(a_i\) 的区间的区间和。于是对于每个 \(a_i\)，可以将所有区间分成两类，即包含 \(a_i\) 的区间和不包含 \(a_ ......

第一问是简单的，\(2(n - 1) - [T = 1] \cdot \max\limits_{i = 1}^{n}\{dep_i\}\)。 对于第二问： 设 \(f(u)\) 表示要求起点和终点均为 \(u\) 的情况下从 \(1\) 时刻开始遍历完以 \(u\) 为根的子树的最小花费，\(g(u ......

双倍经验 分析 这是一道求最长下降子序列的题目，且要统计方案，但是会有重复情况，例如以下的的数据， 4 4 2 2 3 我们可以选择 \(1, 2\), \(1, 2\), \(1, 4\) 这几天来购买，但是 \(1, 2\) 和 \(1, 3\) 本质上是一样的，所以只算一种。 根据上面的说明， ......

还是选与不选的问题，但是每个背包可以无限次选，所以这是个完全背包！ #include<bits/stdc++.h> using namespace std; const int N=2e4+10; int f[N],w[N],t[N]; int main(){ int n,m; cin>>n>>m; ......

题目与P2639十分相似 #include<bits/stdc++.h> using namespace std; const int N=5e4+10; int f[N],t[5010]; int main(){ int T,n; cin>>T>>n; for(int i=1;i<=n;i++){ ......

大概就是在不超过容量的情况下，问你最多能吃多少 是吃与不吃，选与不选的问题，所以是01背包，但是是变式 #include<bits/stdc++.h> using namespace std; const int N=5e4; int f[N],t[1000]; int main(){ int T, ......

所以这是一个01背包的裸题，每个物品选与不选 dp[i][j] 在前面i个物品选择，在不超过j的前提先所能选到的最大价值 公式就出来了 dp[i][j] = max(dp[i-1][j],dp[i-1][j-t[i]]+w[i]) 这是01背包的递推公式 注意的是，该公式还可以优化，因为第i个是从第 ......

更好的访问 [[2023年11月10日总结]] 这一天的题目。 [USACO22OPEN] Alchemy B link。 二分答案。倒着建图，是一个 dag。验证的方法感觉类似 [NOIP2020] 排水系统。但是要注意中间判断一下往下传的多余量有没有超过总金属数。不然容易指数级增长爆掉。这道题写 ......

[USACO22OPEN] Apple Catching G 题目描述 天上下苹果了！在某些时刻，一定数量的苹果会落到数轴上。在某些时刻，Farmer John 的一些奶牛将到达数轴并开始接苹果。 如果一个苹果在没有奶牛接住的情况下落到数轴上，它就会永远消失。如果一头奶牛和一个苹果同时到达，奶牛就会 ......

Description 给定一棵初始有 \(n\) 个点的树。 在第 \(i\) 天，这棵树的第 \(i\) 个点会被删除，所有与点 \(i\) 直接相连的点之间都会两两连上一条边。你需要在每次删点发生前，求出满足 \((a,b)\) 之间有边，\((b,c)\) 之间有边且 \(a\not=c\) ......

题解 P7418【[USACO21FEB] Counting Graphs P】 problem Bessie 有一个连通无向图 \(G\)。\(G\) 有 \(N\) 个编号为 \(1\ldots N\) 的结点，以及 \(M\) 条边（\(1\le N\le 10^2, N-1\le M\le ......

USACO 铂金题解 USACO 2018 Platium B. Sort It Out 很巧妙的转换 注意到操作并不会影响没有被选中的牛的相对顺序 所以没有被选中的一定单调递增 要使得选中的尽可能少，就要选尽可能长的没有被选中的序列，即原序列的 \(LIS\) 所以原题等价于求原序列第 \(k\) ......

P1466 USACO2.2 集合 Subset Sums 毫无思路 如果不告诉我这题是DP题，我一定会爆搜。 看了题解，很妙。 居然也能套背包板子。 定义F[i][j]为在前\(i\)个数中选择一些数其和为\(j\)的方案总数。 显然转移方程F[i][j] = F[i - 1][j] + F[i ......

题解：USACO23OPEN-Silver T1 Milk Sum 给定一个长度为 \(N\) 的序列 \(a_1,a_2,...,a_n\)，现在给出 \(Q\) 次操作每次将 \(a_x\) 修改为 \(y\) ， 每次修改后，求将序列重排后的 \(T\) 的最大值，定义 \(T=\sum_{i ......

P6009 Non-Decreasing Subsequences P 由于值域很小，dp 的转移不难想到写成矩阵的形式。 考虑维护矩阵的前缀积和逆前缀积。 然而单次的矩阵乘已经达到 \(O(k^3)\) 超时了，但是我们发现其实矩阵非 \(0\) 的位置是 \(O(k)\) 个的，所以复杂度降到了 ......

USACO 2020 January Contest, Platinum Problem 2. Non-Decreasing Subsequences 原题网址 这个题目有两种做法，一种是矩阵，一种是 CDQ 分治。矩阵我只大概口胡了一下，没仔细想，这里主要介绍一下 CDQ 分治的做法。 CDQ 分 ......

[P2895 [USACO08FEB] Meteor Shower S]([P2895 USACO08FEB] Meteor Shower S - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)) 语言问题引发的惨案 题目本身不难，简单的BFS，但是写出来明明思路感觉没有问题，却不是答 ......

题目链接 赛时只打了暴力。 Part1 我们考虑在什么情况下要放一个村民，我们设根节点的深度为 \(0\), 那么对于一个节点 \(u\) ,如果在其子树内有一个叶子结点 \(v\), 满足 \(dis_{u, v} \leqslant dep_u\), 那么只要在这个节点放一个村民，就可以把 \( ......

P4182 [USACO18JAN] Lifeguards P 更好的阅读体验 提供一个比较优秀大常数的时间 \(\mathcal O(nm)\)，空间线性的做法。由于变量名冲突，本文中 \(m\) 均指题目中的 \(k\)。 推推性质，发现若区间包含了另一个区间，则一定删掉被包含的区间，正确性显然 ......

前言： 教练给我们做铂金组的题目真的抬举我们了…… [USACO18OPEN] Disruption P 题目描述： 你有一棵节点数为 \(n\)，边数为 \(n-1\) 的树。然后你会给这棵树新增加 \(m\) 条边，对于每条边，有 \(u,v,w\) 分别表示边连接的两个节点分别为 \(u\) ......

题目 link 要求得到平均产奶量的最小值，想到二分答案。 emm...但是我在如何判断当前 \(mid\) 是否能成立上卡了好久，这里就需要思维了。 还是要想到本质上，可以试着用数学式子表达当前 \(mid\) 的合法条件， 若当前要删除 \([l,r]\) 的数，则有：（这里又可以想到用 前缀和 ......

分析 大概是强连通分量里面最水的一道紫题，不过细节挺多的，做题的时候给蒟蒻震惊到了。 题目要求是从 \(1\) 走到某个点，然后再走回 \(1\) 号点，中途可逆行一次，问最多能经过几个点。 有一个明显的思路是存两个图，一个正图一个反图，正图是为了求 \(1\) 到各个点的距离，反图是为了求各个点到 ......

题目背景 Farmer John has MM cows, conveniently labeled 1…M1…M, who enjoy the occasional change of pace from eating grass. As a treat for the cows, Farmer ......

洛谷传送门 LOJ 传送门 hot tea. 一次删点操作的影响太大了，考虑添加虚点以减小影响（相同的套路在 CF1882E2 Two Permutations (Hard Version) 也出现过）。 具体而言，我们把第 \(i\) 条边 \((u, v)\) 变成 \((u, n + i), ......

洛谷传送门 LOJ 传送门 考虑剥路径最大值 dp，设 \(f_{k, i, j}\) 为 \(i \to j\) 中按的最大的按钮 \(\le k\) 的方案数。转移枚举按下最大值按钮的点 \(w\)，有： \[f_{k, i, j} = \sum\limits_{(u, w), (w, v) \ ......

洛谷传送门 LOJ 传送门 如果 \(T = 1\)，可以把重量全部取相反数转化成 \(T = 2\)。接下来只考虑 \(T = 2\) 的情况。 下文的 \(m\) 代表原题中的 \(K\)。 设第 \(i\) 个 G 牛的位置和重量分别为 \(a_{0, i}, b_{0, i}\)，第 \(i ......

[USACO] Piggy Back 题目大概意思是一个无向图，Bessie 从 1 号仓库走到 n 号（每次花费 x）， Elsie 从 2 号仓库走到 n 号（每次花费 y），如果两个人走同一条路花费 z，求总花费最小。 跑三遍最短路,别得到 Bessie 从 1 号仓库出发的最短路,Elsie ......

比较抽象的一个题。 首先先考虑 \(T=1\)，如果我们建一张图，将图上所有横线与竖线的交点看作图上的点，相邻的有线段相连的点看作图上的边的话，那么显然会得到一张平面图，而我们要计算的是平面图上面的个数，根据公式 \(F=E-V+C+1\)，其中 \(C\) 为这张图中连通块的个数。设 \(c\) ......