隐藏
Bill Yang's Blog

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

0%

题目大意

修改边权动态维护MST。


CDQ分治缩小数据规模

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

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

阅读全文 »

题目大意


题目分析

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

状态转移

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

阅读全文 »

题目大意

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


题目分析

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

阅读全文 »

题目大意


题目分析

这题我考试的时候没有看到一个条件啊!!!
对于所有数据,都满足$x1\lt x2 \lt \cdots \lt xn-1 \lt xn,1\le s\le n,0\le L\le n-1$ 。

那这道题其实看完题解后并不是很难。(废话)

阅读全文 »

比赛题目

A. Fair Game

题目大意: A和B在玩一个游戏,每个人选一个数字,然后取走所有写有这个数字的卡牌,游戏是公平的定义为有一种方案使得A和B可以取走所有卡牌且使得A和B取走的数目相同。
题目分析: Hash判一下如果有两个不同的且个数相同即可判为YES。

阅读全文 »

题目大意

有$N$个物品,体积分别是$W_1$,$W_2$,…,$W_N$,第$i$个物品丢失了。要使用剩下的$N$-$1$物品装满容积为$x$的背包,有几种方法呢?。把答案记为Count($i$,$x$),输出$1\le i\le N,1\le x\le M$的Count($i$,$x$)表格。


题目分析

这道题是有$O(nm)$的做法的,但是此处不做解释,可以参考PopoQQQ或hzwer的博客。
我们谈一种普适性更强,思维要求更低的方法:CDQ分治。

阅读全文 »

题目大意

给定一棵$n$个节点的树,每条边的长度为1,同时有一个权值$w$。定义一条路径的权值为路径上所有边的权值的最大公约数。现在对于任意$i\in [1,n]$,求树上所有长度为$i$的简单路径中权值最大的是多少。如果不存在长度为$i$的路径,则第$i$行输出0。


题目分析

这道题第一眼看成了点分治,然后开始思考如何处理$i$个询问。
嗯?这不是点分治+FFT。
正当我准备开始写的时候,我才发现最大公约数不具有最优合并性。
两个最大公约数合起来说不定更小。

阅读全文 »

题目大意

动态加点,询问距离一个点曼哈顿距离最近的点。


题目分析

考虑距离点$(x,y)$曼哈顿最近的点$(x0,y0)$。那么曼哈顿距离$\mid x-x0 \mid+\mid y-y0\mid$最小。

讨论四种情况,若点$(x0,y0)$在点$(x,y)$的左下方,则曼哈顿距离转为$x-x0+y-y0=(x+y)-(x0+y0)$。
那么我们就可以统计在$(x,y)$左下方的点中$(x0+y0)$最大的点。
动态加点->维护时间轴,再加上维护$x$、$y$轴,共维护三维偏序,使用CDQ维护。

阅读全文 »

题目大意

给一个序列,动态删除一些数,求删除元素前整个序列的逆序对数。


题目分析

若不包含删除操作,那此题就是一个二维偏序问题。
满足$i\lt j$且$a_i\gt a_j$的个数,树状数组维护即可。(因为编号已经有序,所以不需排序)

但是我们有删除操作怎么办呢?那么我们加入时间轴代表删除操作,时间轴$t$前表示在执行某次删除操作前的情况。

显然,这是一个三维偏序问题,我们可以用CDQ分治维护时间维。
关于三维偏序可以看这两篇文章:传送门1传送门2

阅读全文 »