bzoj 4491. 我也不知道题目名字是什么 题解
Preface 题目链接 Description 给定一个序列A[i],每次询问l,r,求[l,r]内最长子串,使得该子串为不上升子串或不下降子串 N,Q<=50000 Solution 设 $L[i]$ 表示以 $i$ 为起点,往左最多能成为子串的长度,$R[i]$ 表示以 $i$ 为起点,往右最多能成为子串的长度。 那么很显然区间 $[l…
Luogu P4088 [USACO18FEB]Slingshot P 题解
Preface 题目链接 rua!调了半天发现原来是 $id$ 的问题。。。 Description 有一个数轴,上面有 $n$ 个传送门,使用第 $i$ 个传送门,你可以从 $x_i$​ 走到 $y_i$​,花费的时间为 $t_i$ 秒。你的速度为 $1$ 格/秒,有 $m$ 次询问,每次你要从 $a_i$​ 走到 $b_i$​,最多使用一次传送…
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表示。每个方格有一个…