USACO2
[P1518 [USACO2.4] 两只塔姆沃斯牛 The Tamworth Two]的解题思路
P1518 [USACO2.4] 两只塔姆沃斯牛 The Tamworth Two 初始思路 利用数字1~4代表方向; 利用两个循环来实现两个角色的行为,通过每一步break实现两个角色的同步。 由于题目本意是同步,而我这实质上是分步(牛在前Farmer John在后),所以用Farmer John ......
P1466 [USACO2.2] 集合 Subset Sums
P1466 USACO2.2 集合 Subset Sums 毫无思路 如果不告诉我这题是DP题,我一定会爆搜。 看了题解,很妙。 居然也能套背包板子。 定义F[i][j]为在前\(i\)个数中选择一些数其和为\(j\)的方案总数。 显然转移方程F[i][j] = F[i - 1][j] + F[i ......
P1457 [USACO2.1] 城堡 The Castle 题解
分析 感觉没有蓝题难度 一道 bfs 题目,相较于大部分 bfs 题,它较为复杂,但分析一下还是很好水过的。 建立墙时,可以用三维数组,\(wall_{~i, ~j, ~pos}\) 表示 第 \(i\) 行第 \(j\) 列 \(pos\) 方向有墙。 观察发现,\(8 = 2^3,4 = 2^2 ......
P1522 [USACO2.4] 牛的旅行 Cow Tours
Problem 题目简述 给你两个独立的联通块,求:在两个联通块上各找一个点连起来,使得新的联通块的直径的最小值。 思路 本题主要做法:\(Floyd\)。 首先,Floyd求出任意两个点之间的最短路。 枚举每一个点,求出以这个点能走到的所有点中距离的最大值。(一定在能走到的情况下,不然默认距离就是 ......
P1522 [USACO2.4] 牛的旅行 Cow Tours
# 这是一道纯暴力的题目哦 ## 前言 [传送门](https://www.luogu.com.cn/problem/P1522) 这是本**蒟蒻**第一次发题解,希望大家多多支持!!! ## 分析 这道题目主要考的~~不~~是**最短路**(~~除了Floyd~~),关键是对于各个牧区之间的**连 ......
[刷题笔记] Luogu P1466 [USACO2.2] 集合 Subset Sums
[Problem](https://www.luogu.com.cn/problem/P1466) ### Description 有一个长度为$n$的数组为$1-n$,求有多少种选择方案使得选择数之和等于序列和的一半 ### Solution 题面翻译成这样是不是就好做了? 首先,序列和的一半我们 ......