Category: oi

126 篇文章

Luogu P1225 黑白棋游戏 题解
Preface 题目链接 这题真的恶心,状压写错了调半天。。。 Description 给定一个 $4\times 4$ 的棋盘,每一格放一个棋子,共有 $8$ 个黑棋,$8$ 个白棋。每次可以交换相邻两个格子的棋子,问最少要多少步才能从初始状态到达最终状态。并且需要输出交换方法。 Solution 由于棋盘十分小(只有 $4\times 4$ )…
Luogu P1168 中位数 题解
Description 题目链接 给出一个长度为 $N$ 的非负整数序列 $A_i$,对于所有 $1 ≤ k ≤ (N + 1) / 2$,输出 $A_1, A_1 \sim A_3, …,A_1 \sim A_{2k - 1}$ ​的中位数。即前 $1,3,5,…$ 个数的中位数。 Solution 众所周知,$vector$ 可以当平衡树来用。…
bzoj 2006. [NOI2010]超级钢琴 题解
Description 题目链接 给定一个长度为 $n$ 的序列,选出 $k$ 个长度在 $[L,R]$ 之间的子段(不可重复),求 $k$ 个子段和的最大值。 $N\leq 500,000,k\leq 500,000,-1000\leq A_i \leq 1000,1\leq L\leq R\leq N$ Solution 由于 $n$ 十分巨大…
Luogu P3237 [HNOI2014]米特运输 题解
Description 题目链接 又臭又长的题面差评 给定一棵树,该树满足一定的性质: 节点 $x$ 的所有子节点权值必须相等节点 $x$ 的所有子节点的权值之和等于 $x$ 的权值 Solution 设第 $x$ 个节点的权值为 $v$,它有 $sz[x]$ 个直系子节点,显然,这 $sz[x]$ 个直系子节点的权值均为 $\frac{v}{sz…
Luogu P3203 [HNOI2010]弹飞绵羊 题解
Description 题目链接 某天,Lostmonkey 发明了一种超级弹力装置,为了在他的绵羊朋友面前显摆,他邀请小绵羊一起玩个游戏。 游戏一开始,Lostmonkey 在地上沿着一条直线摆上 $n$ 个装置,每个装置设定初始弹力系数 $k_i$​,当绵羊达到第 $i$ 个装置时,它会往后弹 …
Luogu P3591 [POI2015]ODW 题解
Description 题目链接 给定一棵n个点的树,树上每条边的长度都为1,第i个点的权值为a[i]。Byteasar想要走遍这整棵树,他会按照某个1到n的全排列b走n-1次,第i次他会从b[i]点走到b[i+1]点,并且这一次的步伐大小为c[i]。对于一次行走,假设起点为x,终点为y,步伐为k,那么Byteasar会从x开始,每步往前走k步,如…
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)。一些格子是坚固得令人惊讶的莲花,还有一些格子是岩石,其余的只是美丽、纯净、湛蓝的水。 贝西正在练习芭蕾舞,她站在一朵莲花上,想跳到另一朵莲花上去,她只能从一朵莲花跳到另一朵莲花上,既不能跳到水里,也不能…