Bill Yang's Blog
0%

题目大意

平面上有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$的方向考虑。

阅读全文 »

题目大意

维护一个W*W的矩阵,初始值均为S.每次操作可以增加某格子的权值,或询问某子矩阵的总权值.修改操作数M<=160000,询问数Q<=10000,W<=2000000.


题目分析

这道题其实也是三维偏序的变种。
关于三维偏序可以看这两篇文章:传送门1传送门2
为什么这道题是三维偏序呢?我们来胡乱分析分析。

阅读全文 »

题目大意

维护三维偏序,统计有$i$个比当前点大的点有多少个。


三维偏序普适框架

维护三维偏序使用CDQ分治解决。
CDQ分治是什么?请参考这里
在这里我们提出一种不需要在CDQ中排序的方法,普适性强,常数更小。
初学者请先使用排序的方法,更容易理解,再接受本文方法。

阅读全文 »

题目大意

求出三维偏序的最长序列长度。(偏序指各个维度对应单调)


CDQ分治简介

维护三维偏序,CDQ分治经典应用。
CDQ分治的思想:
我们在网上搜索CDQ分治的学习资料时都大同小异,大概都是说先递归左边,计算左边信息对右边的影响,再递归右边。
实际上这确实是CDQ分治的思想,但是就这么一句话并不能使新学CDQ分治的同学们理解。
在这里我先总结一下CDQ分治解决偏序问题的思路,CDQ分治可以解决很多问题,等我以后整理学习笔记吧。

阅读全文 »