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表示。每个方格有一个…
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 #include<…
loj 6062 「2017 山东一轮集训 Day2」Pair 题解
Description 题目链接 给出一个长度为 $n$ 的数列 $\{a_i\}$ 和一个长度为 $m$ 的数列 $\{b_i\}$,求 $\{a_i\}$ 有多少个长度为 $m$ 的连续子数列能与 $\{b_i\}$ 匹配。 两个数列可以匹配,当且仅当存在一种方案,使两个数列中的数可以两两配对,两个数可以配对当且仅当它们的和不小于 $h$。 对…
bzoj 3653 谈笑风生 题解
Description 题目链接 设T 为一棵有根树,我们做如下的定义: 设a和b为T 中的两个不同节点。如果a是b的祖先,那么称“a比b不知道高明到哪里去了”。 设a 和 b 为 T 中的两个不同节点。如果 a 与 b 在树上的距离不超过某个给定常数x,那么称“a 与b 谈笑风生”。 给定一棵n个节点的有根树T,节点的编号为1 到 n,根节点为1…