隐藏
Bill Yang's Blog

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

0%

题目大意


题目分析

这题我考试的时候没有看到一个条件啊!!!
对于所有数据,都满足$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

阅读全文 »

题目大意

平面上有n个圆,给定起点和终点,你只能在圆内及圆周上行走,问从起点到终点的最短路程。


题目分析

根据路径规划问题的套路,我们需要把不定的路径转化为定的路径。
考虑哪些路径是一定不会被用到的。

这样的路径一定不会用到,为什么,因为我们把拐点移动到圆的交点处长度一定会变小。

阅读全文 »

题目大意

数轴上有很多单位线段,一开始时所有单位线段的权值都是1。有两种操作,第一种操作将某一区间内的单位线段权值乘以w,第二种操作将某一区间内的单位线段权值取w次幂。并且你还需要回答一些询问,每个询问需要求出某一区间的单位线段权值之积。由于答案可能很大,你只需要求出答案 mod (10^9+7)的值。

阅读全文 »

题目大意

平面上有n个点,求出用这些点可以构成的三角形数。


题目分析

显然能够构成三角形需满足三点不共线。
枚举点$i$,枚举尚未枚举过的点$j$,计算出直线$i\rightarrow j$直线的斜率。
用双指针扫描一下跳过斜率相同的,然后计算个数即可。

阅读全文 »

题目大意

对于给定正整数n,m,我们称正整数c为好的,当且仅当存在非负整数x,y,使得$nx+my=c$。
现在给出多组数据,对于每组数据,给定n,m,q,求[1,q]内有多少个正整数不是好的。
n≤10^5 , m≤10^9 , q≤10^18 , T≤10


题目分析

由题,$nx+my=c$该式完全对称,但是$n$与$m$的范围却不一样,这说明我们需要往$n$的方向考虑。

阅读全文 »