Cows
P9194 [USACO23OPEN] Triples of Cows P 题解
直接建边边数过多,不好处理。我们可以考虑建一些虚点,让 \(u_i\) 和 \(n+i\) 连边,\(v_i\) 和 \(n+i\) 连边。设这些新连的点为白点,与白点有连边的点在原图中一定相连,并且一定是一棵树。删除操作相当于把 \(u\) 的子白点连到他的父白点上,使用并查集维护即可。 这时再考 ......
[USACO07DEC] Sightseeing Cows G
[USACO07DEC] Sightseeing Cows G 题目描述 Farmer John has decided to reward his cows for their hard work by taking them on a tour of the big city! The cows ......
P9194 [USACO23OPEN] Triples of Cows P 题解
Description 给定一棵初始有 \(n\) 个点的树。 在第 \(i\) 天,这棵树的第 \(i\) 个点会被删除,所有与点 \(i\) 直接相连的点之间都会两两连上一条边。你需要在每次删点发生前,求出满足 \((a,b)\) 之间有边,\((b,c)\) 之间有边且 \(a\not=c\) ......
USACO 2023 US Open Platinum Triples of Cows
洛谷传送门 LOJ 传送门 hot tea. 一次删点操作的影响太大了,考虑添加虚点以减小影响(相同的套路在 CF1882E2 Two Permutations (Hard Version) 也出现过)。 具体而言,我们把第 \(i\) 条边 \((u, v)\) 变成 \((u, n + i), ......
【LuoGu】3047 Nearby Cows G ——两次DFS+树上DP
[USACO12FEB] Nearby Cows G 题目描述 给你一棵 \(n\) 个点的树,点带权,对于每个节点求出距离它不超过 \(k\) 的所有节点权值和 \(m_i\)。 输入格式 第一行两个正整数 \(n,k\)。 接下来 \(n-1\) 行,每行两个正整数 \(u,v\),表示 \(u ......
P1204 [USACO1.2] 挤牛奶Milking Cows
## P1204 [USACO1.2] 挤牛奶Milking Cows ### 题目描述 三个农民每天清晨 $5$ 点起床,然后去牛棚给三头牛挤奶。 第一个农民在 $300$ 秒 (从 $5$ 点开始计时) 给他的牛挤奶,一直到 $1000$ 秒。第二个农民在 $700$ 秒开始,在 $1200$ ......
P7154 [USACO20DEC] Sleeping Cows P
[原题](https://www.luogu.com.cn/problem/P7154) 我们先思考如果没有极大匹配这个限制该怎么做 ysx曾经说过:dp要先考虑递推顺序 看到这个题的限制$s_i \leq t_i$,可以想到这题要先按照$s_i$和$t_i$的顺序排序 不妨设$dp_{i,j}$表 ......
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 ......
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 ......
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) 的牛棚享用晚餐。她知道,以她所在的区域为起点,每次移动至 ......
NC51101 Lost Cows
题目链接 题目 题目描述 $N (2 \leq N \leq 8,000)$ cows have unique brands in the range 1..N. In a spectacular display of poor judgment, they visited the neighbor ......