隐藏
Bill Yang's Blog
0%

题目大意

平面上有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分治可以解决很多问题,等我以后整理学习笔记吧。

阅读全文 »

题目大意

给定一个带权树,树上任意两点间的路径权值$d(x,y)$定义为$x$,$y$这两个点之间路径上的最小值,树上任意一点$x$的权值定义为这个点到树上其他所有点的路径权值和,即$\sum_i(d(x,i)), 1\le i\le n$,现求树上一点,使得这个点的权值最大,输出这个值。


题目分析

考虑每个点显然是不可做的,因此考虑每条边对答案的贡献。
如果一条边是权值最小的,如图:

阅读全文 »

题目大意

你可以通过飞机传送到一个图中的任意一个点,你可以每次必须走两条边,然后又通过飞机传送到任意一个点,要求走过的边不重复。输出最多可走的次数以及方案。


初步想法

图不一定连通,那么我们对于每一个连通图进行处理。
定长路径统计:枚举中间点。
枚举中间点,我们就只需要考虑剩下的两条边。
简化问题,首先考虑一棵树的情况:

阅读全文 »