FEB
FEB
题目描述 有一个长度为 N的字符串 S，其中的每个字符要么是 B，要么是 E。 我们规定 S的价值等于其中包含的子串 BB 以及子串 EE 的数量之和。 例如，BBBEEE 中包含 2个 BB 以及 2个 EE，所以 BBBEEE 的价值等于 4。 我们想要计算 S的价值，不幸的是，在我们得到 S之 ......
P05527 [Usaco2009 Feb]庙会捷运加强版
庙会捷运Fair Shuttle 公交车一共经过 n 个站点，从站点 1 一直驶到站点 n。k群奶牛希望搭乘这辆公交车。第 ii 群牛一共有 m_i只。他们希望从 s_i到 e_i去。 公交车只能坐 c 只奶牛。而且不走重复路线，请计算这辆车最多能满足多少奶牛的要求。注意：对于每一群奶牛，可以部分满 ......
[USACO23FEB] Equal Sum Subarrays G 题解
[USACO23FEB] Equal Sum Subarrays G 题解 题目链接 \(O(n^5)\) 暴力 显然，如果修改 \(a_i\) 的值，只会影响包含 \(a_i\) 的区间的区间和。于是对于每个 \(a_i\)，可以将所有区间分成两类，即包含 \(a_i\) 的区间和不包含 \(a_ ......
洛谷 P9129 [USACO23FEB] Piling Papers G
第一问是简单的，\(2(n - 1) - [T = 1] \cdot \max\limits_{i = 1}^{n}\{dep_i\}\)。 对于第二问： 设 \(f(u)\) 表示要求起点和终点均为 \(u\) 的情况下从 \(1\) 时刻开始遍历完以 \(u\) 为根的子树的最小花费，\(g(u ......
题解 LOJ3483【[USACO21FEB] Counting Graphs P】
题解 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 ......
P2895 [USACO08FEB] Meteor Shower S
[P2895 [USACO08FEB] Meteor Shower S]([P2895 USACO08FEB] Meteor Shower S - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)) 语言问题引发的惨案 题目本身不难，简单的BFS，但是写出来明明思路感觉没有问题，却不是答 ......
洛谷 P8192 - [USACO22FEB] Paint by Rectangles P
比较抽象的一个题。 首先先考虑 \(T=1\)，如果我们建一张图，将图上所有横线与竖线的交点看作图上的点，相邻的有线段相连的点看作图上的边的话，那么显然会得到一张平面图，而我们要计算的是平面图上面的个数，根据公式 \(F=E-V+C+1\)，其中 \(C\) 为这张图中连通块的个数。设 \(c\) ......
[USACO08FEB]meteor Shower S题解（bfs）
题目描述 贝茜听说一场特别的流星雨即将到来：这些流星会撞向地球，并摧毁它们所撞击的任何东西。她为自己的安全感到焦虑，发誓要找到一个安全的地方（一个永远不会被流星摧毁的地方）。 如果将牧场放入一个直角坐标系中，贝茜现在的位置是原点，并且，贝茜不能踏上一块被流星砸过的土地。 根据预报，一共有 \(M\) ......
[题解]P3656 [USACO17FEB] Why Did the Cow Cross the Road I P
思路 首先，\(A\) 和 \(B\) 只会移动一个，那么，我们分开来算，我们先假定 \(B\) 会动。 不妨令 \(A\) 与 \(b\) 连边的端点为 \(x,y\)。如果有线段 \(pq\) 能与 \(xy\) 相交，一定满足如下其中一条规律： \(p < x \wedge q > y\) \ ......
P4824 [USACO15FEB] Censoring S
P4824 [USACO15FEB] Censoring S KMP+栈 同样的套路，先找B的最长前后缀，然后与A匹配 不同的是要删除A中的B,特殊的是删除之后可能会产生新的B 那我们可以利用栈的思想，利用f数组，记录A每一位置上B的匹配程度，这样删除时，直接回到上一个匹配程度，以防漏掉。 利用栈记 ......
P7414 [USACO21FEB] Modern Art 3 G 题解
## 思路 考虑区间 DP。 设 $f_{i, j}$ 表示要刷到 $[i, j]$ 这一段的目标需要的最小次数。 对于 $f_{i, j}$， 如果 $color_i$ 与 $color_j$ 相等，那么再子区间合并的时候就可以少刷一次，即 $f_{i, j} = \min\limits_{k = ......
P1672 [USACO05FEB] Feed Accounting S 题解
[题目链接](https://www.luogu.com.cn/problem/P1672) ## 思路 一道特别简单的**差分模板题**，其实也有点推理的感觉。 对于每头牛，我们通过两次循环使用差分倒推出在这几天内它对我们饲料消耗的贡献，进而推出每一天的饲料消耗量，从 $D$ 天到现在一共吃掉的饲 ......
做题记录：P3121 [USACO15FEB] Censoring G
题目传送门:[click here](https://www.luogu.com.cn/problem/P3121) 题意简化：给定一个文本串，和n个匹配串，删掉文本串中的匹配串求最后的字符串 做这题之前应该先做简化版：[eazy mode](https://www.luogu.com.cn/pro ......
P4826 [USACO15FEB] Superbull S题解
#Superbull S题解 ###[题目传送门(可点击)](https://www.luogu.com.cn/problem/P4826) #题面 ##题目描述 $Bessie$和她的朋友们正在一年一度的$Superbull$锦标赛中打球，而$Farmer$ $John$负责让比赛尽可能激动人心。 ......
洛谷 P2894 [USACO08FEB] Hotel G 题解
题目链接 P2894 [USACO08FEB] Hotel G - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) 分析 考虑用线段树维护区间信息 维护sum（最大连续空房间数） 如何合并？ sum1为max（sum2，sum3）（1的两个子区间） 但我们发现若区间为100 001（0 ......
USACO23FEB Hungry Cow P
这个涂色很容易让人想到均摊的 set 维护，但是有可能修改同一个位置，不太可做。 同样地，我们考虑只带插入不同位置的情况。 考虑一个线段树做法，直接维护整行格子的权值和以及黑色格子的个数。考虑一个修改 $(i,j)$ 相当于区间覆盖 $[i,k]$ ，其中 $[i,k]$ 中修改前白色格子的数量为 ......
P1672 [USACO05FEB] Feed Accounting S 题解
给 $c$ 个区间表示牛吃草的时间段，每头牛每天吃 $1$ 千克，问距今天（即运来饲料 $f_2$ 千克的时间）最近的送饲料 $f_1$ 千克的时间是什么时候？ ......
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 ......
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 ......
Luogu P6191 [USACO09FEB]Bulls And Cows S （牡牛和牝牛）
# [USACO09FEB]Bulls And Cows S ## 题目背景 一年一度的展会要来临了，Farmer John 想要把 $N$（$1 \leq N \leq 100,000$）只奶牛和公牛安排在单独的一行中。 John 发现最近公牛们非常好斗；假如两只公牛在这一行中靠的太近，他们就会吵 ......
[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不愿让他的奶牛们看到这 ......
[刷题笔记] Luogu P3073 [USACO13FEB]Tractor S
[Problem](https://www.luogu.com.cn/problem/P3073) ### Solution 和[汽车拉力比赛](https://www.cnblogs.com/SXqwq/p/17455232.html)差不多，思路都是二分，二分$d$,但是汽车拉力比赛从一个路标开 ......
P3047 [USACO12FEB]Nearby Cows G 题解
### P3047 [USACO12FEB]Nearby Cows G #### 题目描述  #### 思 ......
Feb 2023-Replay Memory as An Empirical MDP: Combining Conservative Estimation with Experience Replay
将 replay memory视为经验 replay memory MDP (RM-MDP)，并通过求解该经验MDP获得一个保守估计。MDP是非平稳的，可以通过采样有效地更新。基于保守估计设计了价值和策略正则化器，并将其与经验回放(CEER)相结合来正则化DQN的学习。 ......
Stamp Grid（USACO23 FEB Bronze T2）
题目： 这题直接暴力旋转印章再暴力比较是否有多余的黑色，如果没有，进行涂色即可，不需要任何优化。 注意：画布不可以旋转。 肝程序.jpg 程序一会发 注：虽然我喜欢用string但用string一直莫名其妙的错，懒得改了，就换成了char 程序： #include<bits/stdc++.h> us ......
Watching Mooloo（USACO23 FEB Bronze T3）
题目： 题意简洁明了，一边输入一遍判断，如果是第一个就开始第一次的订阅，如果不是，就比较是继续订阅好还是重新订阅好，十分暴力。 程序： #include<bits/stdc++.h> using namespace std; const int N=1e5+10; long long n,k,ans ......
Hungry Cow（USACO23 FEB Bronze T1）
题目： 来写周练了，这道题目开开胃，就只用遍历一遍b数组、d数组再加上一些特判即可 程序： #include<bits/stdc++.h> using namespace std; const int N=1e5+10; long long n,t,d[N],b[N]; int main() { i ......
题解 P9130 【[USACO23FEB] Hungry Cow P】
赛时开始一眼线段树分治，交了几发都 T 了，就意识到事情不对。后来想了想发现势能分析不能带撤销。。。 后来加了一些不能改变复杂度假了的优化，没过之后就自闭跑路了。。。 赛后听别人说了个楼房重建就明白怎么做了。 首先，我们离线下来把 $a$ 排序，去重（这样方便一点，不然权值线段树上的空节点得特判）， ......