K远点对 K-D Tree 真是优雅的暴力！开局建棵树，剪枝刷题数！ 题意： 给定二维平面上的     N    N   N个点，求第     K    K   K远的无序点对。 思路：  别问我为什么想到用K-D Tree的，因为是看了题解的。 本题没有插入、删除等高级操作，仅仅建树和查询，代码简洁。 进入正题：考虑暴力，暴力遍历对于每个点而言能形成的所有点对，显然复杂度为     O   (    n   2    )    O(n^2)   O(n2)，不可行，接下来考虑剪枝。 首先，     K   =   m   i   n   (   100   ,     n   ∗   (  ...

Finding Hotels 在前车之鉴的基础上，真好，又是     1   A    1A   1A 题意： 在二维平面上给定     N    N   N个带权点；     M    M   M个询问，每次询问最近的权值小于某一给定值的点。 思路：  依旧用K-D Tree进行暴力+剪枝。 首先将     N    N   N个点建好K-D Tree，然后对每个询问，暴力查询。 考虑K-D Tree的通用优化思想：对于某个根节点，在剪枝的情况下最好只遍历它的一个子树！ 先搞定当前节点，然后看看询问节点在当前节点的考察维度的左边还是右边，然后就先遍历所在的那一边；关键剪枝： 如果询问点与当前...

TATT 题意： 求最长的非递减的四维偏序长度。 思路：  先将序列任选一个维度进行排序，然后依次将这些点插入到K-D Tree中。 每插入一个点之前，计算以当前点结尾的最长偏序长度（剩下的是三维偏序问题），然后再将当前点插入即可。 当然，K-D Tree重点还是在剪枝上。此处考虑两种剪枝即可：  如果当前子空间某一个维度的最下值都大于询问点的这一维度，则剪枝； 如果当前子空间最长偏序长度小于当前答案值，则剪枝（询问时优先处理可能的长度较长的子空间）。   代码 #include "bits/stdc++.h" #define hhh printf("hhh\n&...

JZPFAR 题意： 给定平面上     N    N   N个点，然后     M    M   M个询问：给定一个点，求第     K    K   K远点。 思路：      K    K   K远点对的弱化版本？  建好普通的K-D Tree 每次询问维护一个大小为     K    K   K的小顶堆即可 剪枝也非常基础  代码 #include "bits/stdc++.h" #define hhh printf("hhh\n") #define see(x) (cerr<<(#x)<<'='<<(x)&l...

The Coronation 题意： 给定     n    n   n个长度为     m    m   m的     01    01   01串，定义两个串相似：两个串对应位置相同的位置数量不小于某给定值     k    k   k；可以通过反转字符串使得两个     01    01   01串从不相似变成相似，求最少的反转次数使得所有的     01    01   01串两两相似。 思路：  刚看到这题时还想过网络流、双向bfs？QAQ，后面突然想到好像可以2-Sat，于是就A了。。。 那怎样想到2-Sat呢？考虑到每个     01    01   01串有两种状态，只能选其中...

K-th occurrence 之前网络赛跟队友合体出的题，当时我写的后缀自动机，他写的主席树，hhh！ 现在我会写主席树，他会写后缀数组，于是各自独立的A了！并且我跟之前网络赛时的解法还不完全一样 巨佬队友bxd的后缀数组+主席树解法 题意： 给定一个串     S    S   S，有     Q    Q   Q个询问：求子串     S   [   l   ,   r   ]    S[l,r]   S[l,r]在     S    S   S中的第     k    k   k次出现位置。 思路：  由于后缀自动机可以知道某个子串的     e   n   d   p   o   s...

时空旅行 题意： 给定一棵以     0    0   0为根的树，每个节点上有信息（一种是增加某个带权三维点，一种是删除某个带权三维点）；询问要求从根节点到某个节点的信息总和中找到一个最优带权三维点。 思路：  首先，每个星球的     y   ,   z    y,z   y,z坐标显然是没用的。 每个节点的信息原本的控制范围为其所在子树，如果将其处理成     d   f   s    dfs   dfs序，则其控制的区间为数组上一个连续线段；这时我们考虑将这些线段利用线段树分治拆解开来(每个控制线段被拆解为     l   o   g    log   log段)。 需要注意的是，每个...

中国剩余定理：猜数字 求解下列同余方程组（模数互质）      {     <mstyle displaystyle="false" scriptlevel="0">   x   ≡    a   1   <mtext>   </mtext>  (  <mtext>   </mtext>  m   o   d  <mtext>   </mtext>   m   1   <mtext>   </mtext>  )   </mstyle> ...

（扩展）欧拉定理 练一手板子题啦！ 欧拉定理：当     a   ,   m    a,m   a,m互质时，有     <mstyle displaystyle="true" scriptlevel="0">   a   b    ≡    a    b   %   φ   (   m   )    <mtext>   </mtext>  (   m   o   d  <mtext>   </mtext>  m   )  </mstyle>   \displaystyle a^b ...

线性筛 总体思想：筛某个合数时，总是这个数的最小质因数筛除它。 划重点 ：因数个数     d   (   n   )    d(n)   d(n)、因数和     s   (   n   )    s(n)   s(n)、欧拉函数     p   h   i   (   n   )    phi(n)   phi(n)、莫比乌斯函数     m   u   (   n   )    mu(n)   mu(n)等均为     n    n   n的积性函数，能很好的利用“最小质因数”筛法性质。 一、筛质数 处理出     1   e   8    1e8   1e8以内的素数用时     1 ...

【生物】分类 这场比赛拿了个B题一血，舒服！  题意：模板题 给定一张连通图，求出以1为根的最小生成树（然后就跟图没啥关系了）。 对于这棵生成树，有3种操作+3中询问：  更换根节点 树上     x    x   x到     y    y   y的最短路径上的点权加     d    d   d 树上     x    x   x所在子树所有节点点权加     d    d   d 求     x    x   x和     y    y   y的     L   C   A    LCA   LCA 求     x    x   x到     y    y   y的最短路径上的点权之和 ...

Lomsat gelral 之前没有记录过dsu on tree，挑了一个板子题记录一下 DSU on tree（Disjoint Set Union，树上启发式合并）  思想：利用每个节点到根节点路径上的轻边数复杂度是     l   o   g    log   log级别的，同时只有当每次遍历轻边时才会将整棵轻边连接的子树额外暴力遍历一遍，所以每个节点被暴力遍历的次数就是     l   o   g    log   log级别的，这样就保证了整体复杂度在     l   o   g    log   log级别啦！(默认点修改为O(1)) 三种     d   f   s    dfs...

读入int 类型 使用方法 a[i] = read(); 不用在乎数字前面的空格、换行之类的 非负数 inline int read() { int x=0; char c=getchar(); while(c<'0'||c>'9') c=getchar(); while(c>='0'&&c<='9') x=x*10+c-'0', c=getchar(); return x; }  有负数 inline int read() { int x=0, sign=1; char c=getchar(); while((c<'0'||c>'9')&a...

#include "bits/stdc++.h" #define hhh printf("hhh\n") #define see(x) (cerr<<(#x)<<'='<<(x)<<endl) using namespace std; typedef long long ll; typedef pair<int,int> pr; inline int read() {int x=0,f=1;char c=getchar();while(c!='-'&&(c<'0'||c&g...