隐藏
Bill Yang's Blog

路终会有尽头,但视野总能看到更远的地方。

0%

题目大意

给出一个随机的排列,请你计算最大值减最小值的差小于等于0~$n$-1的区间分别有多少个。


题目分析

此题可做完全基于随机性。
这题似乎有分治的解法。
然而我用的单调栈+双指针。

阅读全文 »

题目大意

一个树由n个点,n-1条边组成,结点编号为1..n。树上任意两个点之间路径唯一。
定义一个点到一条路径的距离为:该点到路径上最近的一个点需要经过的边的数量。
现在想知道怎样选两个点确定一条路径,使得距离这个路径最远的点尽量近。要求你输出距离路径最远的点距离路径的距离。

阅读全文 »

题目大意

有$n$个餐厅,从0~$n$-1编号,每天都要去一个餐厅吃饭,这个餐厅的编号可以计算得出。但是他不想去$\lfloor \frac{n}{2}\rfloor$天去过的餐厅,如果$\lfloor \frac{n}{2}\rfloor$天去过了,便会向右平移1个餐厅,如果$\ge n$,编号变为0,问这$n$天去哪一个餐厅。


题目分析

这题因为随机数的原因,这道题暴力都可以过。。。

阅读全文 »

题目大意

有$n$个位置和$m$个操作。操作有两种,每次操作如果是$1\, a\,b \,c$的形式,表示往第$a$个位置到第$b$个位置每个位置加入一个数$c$。如果操作形如$2\,a\,b\,c$的形式,表示询问从第$a$个位置到第$b$个位置,第$c$大的数是多少。


整体二分

这道题可以使用树套树解决,但在这里我们提出一种更加神奇的做法,它的名字是:整体二分
整体二分是什么?其实这不是什么新东西,就是CDQ分治的变种。

阅读全文 »

题目大意

修改边权动态维护MST。


CDQ分治缩小数据规模

本题略难。
有两种解法可以做:CDQ分治+缩小规模、CDQ分治+LCT
本处不提及第二种解法。

这大概是CDQ分治的第三个应用了吧,缩小数据规模,使得能在允许的时间范围内完成询问。

阅读全文 »

题目大意


题目分析

显然这道题是一道1D/1D动态规划的问题,我们可以尝试写出方程。
显然,我们如果在每一天要买或卖,不会部分操作,肯定要么全部买要么全部卖。

状态转移

那么设第$i$天没有A、B券,可以买入的A、B券分别有$X_i$和$Y_i$个,能够兑换的人民币为$f_i$。
显然有:

阅读全文 »

题目大意

给定$n$个点,$m$条边的无向图,可以从图中删除一条边,问删除哪些边可以使图变成一个二分图。


题目分析

二分图不能包含奇环,只能包含偶环,这是二分图的第二定义。
显然,我们要删除的边只能在奇环的交上
并不显然的还有:要删除的边不能在偶环上

阅读全文 »