K远点对 K-D Tree 真是优雅的暴力！开局建棵树，剪枝刷题数！ 题意： 给定二维平面上的 N N N个点，求第 K K K远的无序点对。 思路： 别问我为什么想到用K-D Tree的，因为是看了题解的。 本题没有插入、删除等高级操作，仅仅建树和查询，代码简...

Finding Hotels 在前车之鉴的基础上，真好，又是 1 A 1A 1A 题意： 在二维平面上给定 N N N个带权点； ...

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

JZPFAR 题意： 给定平面上 N N N个点，然后 M M M个询问：给定一个点，求第 K K K远点。 思路...

The Coronation 题意： 给定 n n n个长度为 m m m的 01 01 01串，定义两个串相似：两...

K-th occurrence 之前网络赛跟队友合体出的题，当时我写的后缀自动机，他写的主席树，hhh！ 现在我会写主席树，他会写后缀数组，于是各自独立的A了！并且我跟之前网络赛时的解法还不完全一样 巨佬队友bxd的后缀数组+主席树解法 题意： 给定一个串 S S S，有 Q Q ...

时空旅行 题意： 给定一棵以 0 0 0为根的树，每个节点上有信息（一种是增加某个带权三维点，一种是删除某个带权三维点）；询问要求从根节点到某个节点的信息总和中找到一个最优带权三维点。 思路： 首先，每个星球的 y , z ...

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

（扩展）欧拉定理 练一手板子题啦！ 欧拉定理：当 a , m a,m a,m互质时，有 <mstyle displaystyle="true" scriptlevel="0"> ...

线性筛 总体思想：筛某个合数时，总是这个数的最小质因数筛除它。 划重点 ：因数个数 d ( n ) d(n) d(n)、因数和 s ...

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

Lomsat gelral 之前没有记录过dsu on tree，挑了一个板子题记录一下 DSU on tree（Disjoint Set Union，树上启发式合并） 思想：利用每个节点到根节点路径上的轻边数复杂度是 l o g log log级别的，同时只...

读入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(); ...

#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...