Author: yzxoi

125 篇文章

Luogu P4772 灰化肥,会挥发 题解
Description 在Farmer Justin的农场中有许多灰化肥,它们都堆积在A仓库里。为了方便施肥,Farmer Justin需要修一些公路使得他能用拖拉机把这些灰化肥拉到其他仓库里。由于Farmer Justin及其懒惰,所以他只想一次拉完所有的灰化肥送到其他仓库里。但是灰化肥见光易挥发,所以Farmer Justin需要尽快把这些灰化…
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的整数表示,每个地点设有若干个刷卡机。  有以下三类事…
浅谈Link Cut Tree
前言 Link Cut Tree 可真是好用呢~ 刚入门的各位不需要担心,LCT其实十分简单。 陈指导写的LCT也不过10几行,我这个菜鸡打的模板也只有50+行。 所以LCT码量很小 好了,步入正题。 正文 简介 A link/cut tree is a data structure for represen…
IOI国家集训队1999-2019年论文集 (文末附下载链接)
国家集训队论文列表(1999-2019) 1999 陈 宏 -《数据结构的选择与算法效率——从IOI98试题PICTURE谈起》 来煜坤 -《把握本质,灵活运用——动态规划的深入探讨》 齐 鑫 -《搜索方法中的剪枝优化》 邵 铮 -《数学模型的建立、比较和应用》 石润婷 -《隐蔽化、多维化、开放化──论当今信息学竞赛中数学建模的灵活性》 杨 帆 -…
Luogu P2617 Dynamic Rankings 题解
Description 题目链接 给定一个含有 $n$ 个数的序列 $a_1,a_2 \dots a_n$​,需要支持两种操作: Q l r k 表示查询下标在区间 $[l,r]$ 中的第 $k$ 小的数C x y 表示将 $a_x$​ 改为 $y$ Solution 树状数组套主席树 Code [crayon-5f6…