每月存档: 2020年8月

6 篇文章

Luogu P2493 [SDOI2011]贪食蛇 & bzoj 2284. [Sdoi2011]贪食蛇 题解
Description 题目链接Luogu 题目链接bzoj 相信大家都玩过贪食蛇游戏,现在有一个改版贪食蛇游戏,跟传统的贪食蛇游戏一样,贪食蛇在活动区域内运动,吃食物,但是这个改版的贪食蛇游戏有着一些特别的规则。 活动区域: 贪食蛇的活动区域是一个R行C列的网格A,贪食蛇活动不能超过这个网格的范围。第i行第j列的方格用Ai,j表示。每个方格有一个…
Luogu P2446 [SDOI2010]大陆争霸 题解
Description 题目链接 $m$条单向边连接$n$个城市,通过每边要$w_i$​单位时间。从$1$开始,依次摧毁城市,仅仅摧毁不用时间,直到摧毁$n$结束。部分城市被别的城市保护,只有保护它的城市被摧毁后,才能摧毁这个城市。求结束的最短时间。 Solution 把所有保护关系从保护者连向被保护者一条边,每一次遍历到一个点时,把所有与该点有关…
Luogu P1606 [USACO07FEB]Lilypad Pond G 题解
Description 题目链接 为了让奶牛们娱乐和锻炼,农夫约翰建造了一个美丽的池塘。这个长方形的池子被分成了M行N列个方格(1≤M,N≤30)。一些格子是坚固得令人惊讶的莲花,还有一些格子是岩石,其余的只是美丽、纯净、湛蓝的水。 贝西正在练习芭蕾舞,她站在一朵莲花上,想跳到另一朵莲花上去,她只能从一朵莲花跳到另一朵莲花上,既不能跳到水里,也不能…
Luogu P4366 [Code+#4]最短路 题解
Description 题目链接 给定一张 $N$ 个点的图,$M$ 条边,另外任意两个点之间还有一条权值为 $(i \oplus j) \times C$ 的边,问 $A$ 到 $B$ 的最短路。 $1\leq N \leq 10^5,1\leq M \leq 5\times 10^5$ Solution 首先,暴力建图肯定是不行的,$…
bzoj 3091 & Luogu P4842 城市旅行 题解
Description 题目链接Luogu darkbzoj 给定一个森林,初始形态是一棵以 $1$ 为根的树,要求进行以下操作。 连接 $x,y$断开 $x,y$$x$ 到 $y$ 的路径上每个点权值加上 $d$求在 $x$ 到 $y$ 的路径上任选 $2$ 个点之间路径上点的权值和的期望 对于 $100\%$ 的数据,满足 $1<=N&l…
bzoj 2959 长跑 题解
Description   某校开展了同学们喜闻乐见的阳光长跑活动。为了能“为祖国健康工作五十年”,同学们纷纷离开寝室,离开教室,离开实验室,到操场参加3000米长跑运动。一时间操场上熙熙攘攘,摩肩接踵,盛况空前。  为了让同学们更好地监督自己,学校推行了刷卡机制。  学校中有n个地点,用1到n的整数表示,每个地点设有若干个刷卡机。  有以下三类事…