题意： 求区间第k大数 思路： 可持久化线段树。 其实这东西在国内更常见的名字应该是 zhu xi 树？应该是由于“中国高端数据结构领导者”的hjt比较早得引入（？推广？）而得来的。 不过之前没写什么东西都被封，写个zhu xi 树，怕是政治敏感够枪毙100回了orz 似乎也叫函数式线段树。 写个模板题练下手。学习笔记之后补。 /* *********************************************** Author :111qqz Created Time :2017年10月16日 星期一 21时51分55秒 File Name :2104.cpp …

题目链接 题意： 给定二维平面的n个点，要求一个面积最小的正方形，使其能覆盖所有的点。 思路： 先考虑如果水平竖直地放置正方形（边和坐标轴平行）圈住所有点的最小正方形的边长是: L=max(xmax−xmin,ymax−ymin) 然后考虑如果正方形旋转的话，能圈住所有点的正方形边长是随着角度先减后增的，有凸性，可以三分。。。 但是枚举角度计算正方形的话比较麻烦，可以选择旋转平面上的点，使得正方形仍然是水平竖直放置的，因为这样计算正方形的边长比较方便。 如果把点表示成极坐标形式: x=r×cosθ,y=r×sinθ,，θ是极角 那么顺时针旋转 α 角度后： x′=r×cos(θ−α),y=r×sin(θ−α) 化简一下 …

题目链接 题意： 有n个点，表示n个圆的圆心，问一组圆的半径，满足相邻(i,i+1)或者(n,1) 圆相外切。 思路： 我们发现确定第一个半径之后，其他的圆的半径似乎能解出来？ 然后发现，其实只有n为奇数的时候能解出来，n为偶数不行。 那么我们可以奇数偶数分别处理。 对于奇数，直接解出来。式子不写了，很好推。 对于偶数，我们发现，最后会是一个关于r1的二次表达式。 一眼三分。然后训练的时候我就直接三分了。。？？？ 三分的过程中判断一下是否所有圆的半径都满足实际意义。。。 然而这是错得，而且错得很显然。因为。。如果不满足实际意义，是根本没办法判断，该往哪个方向继续三分的。 然而这是错得，而且错得很显然。因为。。如果不满足实际意义，是根 …

题意： 给定一个 N∗N(N≤4e9) 的矩阵，现在经过这样一个变换：将 (x,y) 变为 ((x+y)%N,(x+2×y)%N)(0≤x<N,0≤y<N) 现在求经过多少次这样的变换之后在回到 N∗N 的原始矩阵。 思路： 在模n的剩余系下可以写成(fib(n)x+fib(n+1)y,fib(n+1)x+fib(n+2)y)的形式fib(n)表示Fibonacci数列的第n项 所以就成了斐波那契数列循环节。。经典题。注意会爆long long,要用ULL 又写了遍板子，去年的东西都忘得差不多了orz /* *********************************************** Author …

题意： 有一棵树，水源在根节点1，房子在叶子节点。有若干操作，操作可能是歹徒占领或者离开一个房子。我们不想给歹徒供水，可以通过切断边实现（如果某个叶子节点到根节点的路径上有一条边被切掉，那么就不能供水了。）对于每次操作后，问不给所有歹徒供水最少要切多少条边，并且问在切满足前面最小的情况下，最少使得多少个良民受影响。初始没有歹徒。 思路： 我们先考虑第一个问题。容易知道，假设与根相连的有k条边，那么最多只需要切k次，就切断了所有房子的水源。 也就是说，从最少切的次数角度的考虑，切与水源相连的边一定是最优的。 我们可以考虑把树根1去掉，这样得到k棵子树 然后可以预处理出，对于每个叶子节点，其非根的最远祖先是谁，也就是k棵子树的根节点都是 …

题目链接 题意： 在一个二维平面上，有n个加热设备，每个加热设备加热一个圆形，加热设备需要信号源才可以工作，信号源在原点上，但是高度不确定。假设设备的加热半径是一个与{信号源与设备的距离}有关的表达式。现在想要满足，至少有k个加热设备加热的面积大于s，问信号源的最高高度是多少。 思路： 训练的时候一眼二分，但是求圆并的时候gg了。。毫无思路。 搞定了多个圆面积并。。这题就很easy了。。 需要注意，每次二分的时候，记得初始化圆的d... /* *********************************************** Author :111qqz File Name :H.cpp …

题目链接 题意&思路： 给出n个圆 求恰好k个圆相交的面积，k属于1..n 先放个别人的代码。。。 我真是体会到了。。。软件工程这门课的重要性。。。 这代码真是烂得印象深刻。。。几何题全是面向过程？ circle和point 类写在一起。。。感觉所有糟糕的写法这份代码全都占了。。。 /* *********************************************** Author :111qqz Created Time :2017年10月11日 星期三 19时53分30秒 File Name :ciru.cpp ************************************************ …

题目链接 题意： 多n个圆的面积并。 思路： 发现和求2个圆的完全不一样，具体请参考 SPOJ 8073 The area of the union of circles（计算几何の圆并）（CIRU） 圆的面积并  格林公式在面积并问题中的应用 （用格林公式搞真是跪烂了。。。。 没有仔细看细节，当成板子好了(我最菜.jpg 将代码写成了自己熟悉的风格。 以及双倍经验题:SPOJ VCIRCLES /* *********************************************** Author :111qqz Created Time :2017年10月11日 星期三 19时53分30秒 File Name …

题目链接 题意: If two point such as (xi,yi,zi) and (xj,yj,zj) xi≥xj yi≥yj zi≥zj, the bigger one level add 1 问每个point的level是多少。 思路： cdq分治，先去重并统计相同的点的数量，需要注意要记录原id对应到了哪个新id /* *********************************************** Author :111qqz Created Time :2017年10月10日 星期二 19时53分38秒 File Name :5618.cpp …

Description 有n朵花，每朵花有三个属性：花形(s)、颜色(c)、气味(m)，又三个整数表示。现要对每朵花评级，一朵花的级别是它拥有的美丽能超过的花的数量。定义一朵花A比另一朵花B要美丽，当且仅当Sa>=Sb,Ca>=Cb,Ma>=Mb。显然，两朵花可能有同样的属性。需要统计出评出每个等级的花的数量。 Input 第一行为N,K (1 <= N <= 100,000, 1 <= K <= 200,000 ), 分别表示花的数量和最大属性值。 以下N行，每行三个整数si, ci, mi (1 <= si, ci, mi <= K)，表示第i朵花的属性 Output 包含N …