Cow
借shared_ptr实现写时复制（COW）
原理 1、使用智能指针管理共享资源 2、write端，若引用计数为1，则write端独占资源，若引用计数不为1，则对共享资源备份进行写操作，以确保线程安全 3、read端，读之前引用计数加1，write端此时若并发访问共享资源，则会发现引用计数不为1，write端不会直接写共享资源，确保线程安全 代 ......
P3612 [USACO17JAN] Secret Cow Code S
P3612 [USACO17JAN] Secret Cow Code S 自我感想 哎，又是一道写不出来的。 完全没有这样的思路，只会笨b模拟只能得40. 解题前应该的思考 通过题目给的数据可以知道纯暴力模拟肯定爆空间。（基本否定正推） 这里根据题目所说的，其实可以知道是一个初字符串通过固定的规律形 ......
聊聊大数据框架的数据更新策略: COW,MOR,MOW
大数据框架下，常用的数据更新策略有三种: COW: copy-on-write, 写时复制; MOR: merge-on-read, 读时合并; MOW: merge-on-write, 写时合并; hudi等数据湖仓框架，常用的是前两种实现数据更新。而Doris则主要用后两种更新数据。 COW 在 ......
xv6 cow
虚拟内存提供了一定程度的间接性：内核可以通过将PTE标记为无效或只读来拦截内存引用，从而导致页面错误，并可以通过修改PTE来更改地址的含义。 xv6中的fork系统调用将父进程的所有用户空间内存复制到子进程中。如果父对象很大，则复制可能需要很长时间。更糟糕的是，这项工作经常被大量浪费：fork通常在 ......
[USACO06DEC] Cow Picnic S
P2853 [USACO06DEC] Cow Picnic S 逆向思维 如果顺着题目走，不大好做。 考虑该题要求的是可以供所有奶牛到达的牧场，那么不如从奶牛所在的牧场下手 即对每个奶牛所在的牧场 \(DFS\)，对所有到达点标记。 那么显然当一个点的标记等于 \(k\) 时，说明该牧场是合适的。 ......
[CF283E] Cow Tennis Tournamsan
CF283E 答案即为 \(\binom{n}{3}\) 减去不合法环数。 一个三元环中最多1个点出度为2,所以出度为 x 的点会造成 \(\binom{x}{2}\) 个不合法的环。 \(\Omicron(nm)\) 的做法就是枚举 i,判断 i 与 n 个点连边是否反向(0,1表示)。 然后可以 ......
[USACO18JAN] Cow at Large P
题目链接 赛时只打了暴力。 Part1 我们考虑在什么情况下要放一个村民，我们设根节点的深度为 \(0\), 那么对于一个节点 \(u\) ,如果在其子树内有一个叶子结点 \(v\), 满足 \(dis_{u, v} \leqslant dep_u\), 那么只要在这个节点放一个村民，就可以把 \( ......
cow relays满足结合律的证明
即证明\((A*A)*A=A*(A*A)\) 因为\(A*A=B\)，所以即证明\(B*A=A*B\) 设\(C_1=B*A\)，那么有$$C_1[i][j]=min_{1≤k≤p}(B[i,k]+A[k,j])$$ \[=min_{1≤k≤p}(min_{1≤l≤p}(A[i][l]+A[l][k ......
[题解]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\) \ ......
P1522 [USACO2.4] 牛的旅行 Cow Tours
Problem 题目简述 给你两个独立的联通块，求：在两个联通块上各找一个点连起来，使得新的联通块的直径的最小值。 思路 本题主要做法：\(Floyd\)。 首先，Floyd求出任意两个点之间的最短路。 枚举每一个点，求出以这个点能走到的所有点中距离的最大值。(一定在能走到的情况下，不然默认距离就是 ......
洛谷P3612 [USACO17JAN] Secret Cow Code S
[USACO17JAN] Secret Cow Code S 题面翻译 奶牛正在试验秘密代码，并设计了一种方法来创建一个无限长的字符串作为其代码的一部分使用。 给定一个字符串，让后面的字符旋转一次（每一次正确的旋转，最后一个字符都会成为新的第一个字符）。也就是说，给定一个初始字符串，之后的每一步都会 ......
题解 STEAD - Steady Cow Assignment
我一眼费用流，等等不太对，感觉还是最大流好点。 题目描述 给你一堆奶牛和牛棚，每个奶牛可以匹配多个牛棚，而每个奶牛对每个牛棚之间的满意度是不一样的，并且每个牛棚的容量也是不一样的，问你最终可以有多少个牛匹配的牛棚满意度之和最小。 具体思路 首先，源点与每个奶牛之间连一条流量为 \(1\) 的边。 要 ......
P1653 [USACO04DEC] Cow Ski Area G
如果把每个方格看作一个点，就是这道题的子任务 B 了。 思路 首先看到目标是保证任意方格可以互通，就可以想到应该是一道强连通分量的题，只要按照题目的要求建图，就可以得到一个有向图，那么用 tarjan 缩点后，就可以得到一个无环的有向图。 这样一个无向图，对于每个有入度有出度的点，肯定都是按照顺序走 ......
P1522 [USACO2.4] 牛的旅行 Cow Tours
# 这是一道纯暴力的题目哦 ## 前言 [传送门](https://www.luogu.com.cn/problem/P1522) 这是本**蒟蒻**第一次发题解，希望大家多多支持！！！ ## 分析 这道题目主要考的~~不~~是**最短路**(~~除了Floyd~~)，关键是对于各个牧区之间的**连 ......
[USACO10DEC] Cow Calisthenics G
1. 注意到“最大值最小”，考虑二分最大直径。 2. 对于当前直径，树形dp + 贪心的封锁。 3. $f_u$：以 $u$ 为根的子树，叶节点到 $u$ 的最大距离 $+1$。 4. 在树形dp时维护 $\max f_{v'}$，与 $f_v$ 组成直径。 5. 复杂度 $\mathcal{O}( ......
[USACO10DEC] Cow Calisthenics G
1. 注意到“最大值最小”，考虑二分最大直径。 2. 对于当前直径，树形dp + 贪心的封锁。 3. `f[u]`：以 u 为根的子树，叶节点到 u 的最大距离 +1。 4. 在树形dp时维护 `mx`，与 `f[u]` 组成直径。 5. 复杂度 $\mathcal{O}(n\log n)$。 Vi ......
[USACO10DEC] Cow Calisthenics G
1. 注意到“最大值最小”，考虑二分最大直径。 2. 对于当前直径，树形dp + 贪心的封锁。 3. `f[u]`：以 u 为根的子树，叶节点到 u 的最大距离 +1。 4. 在树形dp时维护 `mx`，与 `f[u]` 组成直径。 5. 复杂度 $\mathcal{O}(n\log n)$。 Vi ......
「USACO11NOV」 Cow Lineup S
# 「USACO11NOv1」 Cow Lineup S题解 ## 问题描述 农民约翰雇一个专业摄影师给他的部分牛拍照。由于约翰的牛有好多品种，他喜欢他的照片包含每个品种的至少一头牛。 约翰的牛都站在一条沿线的不同地方， 每一头牛由一个整数位置$X_i$以及整数品种编号$ID_i$表示。 约翰想拍一 ......
题解 Cow and Snacks
被黄题创死了2333 [题目链接](https://www.luogu.com.cn/problem/CF1209D) 首先肯定有一个贪心的想法：尽量使得人们拿的花重复，即尽量使得每个人都拿一束花。当然第一个人必须拿两束。 接着思考：如何找出有几个人是必须拿两束花的。 其实很简单，当 $A,B$ 两 ......
UVA10678 The Grazing Cow 题解
[题目链接](https://www.luogu.com.cn/problem/UVA10678) ## 思路 一道简单模拟题。 经过模拟，我们不难发现，牛的活动轨迹是一个椭圆。根据椭圆形面积公式得到 $S = \pi a b$。其中，牛可以到的最左边或最右边时 $a = \frac{l}{2}$， ......
P4183 [USACO18JAN] Cow at Large P 题解
### 题意分析 我们首先想到，枚举贝茜在 $x$ 点，枚举度数大于 $2$ 的点为 $y$。设 $x$ 的度数为 $a$，$y$ 的度数为 $b$。 我们首先发现每个 $x$ 点都有一个初始的贡献为 $a$ 条通往叶子的路径。 如果点 $y$ 到最近的叶子节点的距离大于到 $x$ 的点的距离（农夫 ......
Great Cow Gathering G
# Great Cow Gathering G ## 思路 换根dp，[Tree Distances I](https://www.cnblogs.com/ybtarr/p/17632352.html) 强化版，同样的先思考单个的，那么对于子树 $u$ 对于每一个儿子 $v$ 都有：$f_u = f ......
Tarjan例题：洛谷 P2863 [USACO06JAN] The Cow Prom S
### [在洛谷中查看](https://www.luogu.com.cn/problem/P2863) 模板题，缩完点后扫一遍就行了。 巩固基础。 ```cpp #include using namespace std; const int N = 1e4+5; int n,m,dfn[N],lo ......
[刷题笔记] Luogu P2340 [USACO03FALL] Cow Exhibition G
[Problem](https://www.luogu.com.cn/problem/P2340) ### Solution 乍看可能没有思路。我们注意到本题是牵扯到一头奶牛选or不选的问题，非常自然地想到**01背包**。 接下来我们就尝试将本题背景转换成01背包问题。 我们可以将智商转换成容量， ......
NC106972 Cow Ski Area
## [NC106972 Cow Ski Area](http://poj.org/problem?id=2375) ### 一、题目 $N*M$的滑雪场，每个点都有他的高度，滑雪的时候只能向四周相邻的不高于当前点的高度的点滑，现在滑雪场准备修建若干个缆车线路，使得奶牛可以从任意一个点运动到滑雪场的 ......
USACO23FEB Hungry Cow P
这个涂色很容易让人想到均摊的 set 维护，但是有可能修改同一个位置，不太可做。 同样地，我们考虑只带插入不同位置的情况。 考虑一个线段树做法，直接维护整行格子的权值和以及黑色格子的个数。考虑一个修改 $(i,j)$ 相当于区间覆盖 $[i,k]$ ，其中 $[i,k]$ 中修改前白色格子的数量为 ......
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 ......
题解 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) ......
[USACO07OPEN] Kill That Cow S(bushi
FJ 丢失了他的一头牛，他决定追回他的牛。已知 FJ 和牛在一条直线上，初始位置分别为 $x$ 和 $y$，假定牛在原地不动。FJ 的行走方式很特别：他每一次可以前进一步、后退一步或者直接走到 $2\times x$ 的位置。计算他至少需要几步追上他的牛。 ......
Closest Cow Wins S 最近的奶牛获胜
# Closest Cow Wins S 最近的奶牛获胜 [题目传送门](https://www.luogu.com.cn/problem/P7990) [TOC] ## 题目描述 Farmer John 沿着一条高速公路拥有一个很长的农场，可以被看作类似于一维数轴。沿着农场有 $K$ 块草地（$1 ......