k-D Tree 是一种可以高效处理 $k$ 维空间信息的数据结构,在算法竞赛的题目中一般 $k = 2$。 建树 k-D Tree 具有二叉搜索树的形态,二叉搜索树上的每个节点都对应 $k$ 维空间内的一个点。其每个子树中的点...
Codeforces Round #647 (Div. 1) – Thanks, Algo Muse! 题解
Codeforces Round #647 (Div. 1) - Thanks, Algo Muse! Johnny and Contribution 傻逼模拟题,用 stable_sort 排序一下,然后判一下无解。 const int N = 5e5 + 7; int n, m, a[N], p[N], q[N]; vi e[N]; ...
AtCoder Grand Contest 037 题解
AtCoder Grand Contest 037 Dividing a String 可以证明划分出来的段长度不超过 $2$,于是 $\mathcal O(n)$ DP 即可。 const int N = 2e5 + 7, inf = 1e9; int n, f[N][2]; char s[N]; int main() { ...
JOISC 2018 题解
JOISC 2018 Day 1 道路建设 发现操作本质上是一个 $\text{access}$,LCT 维护即可,逆序对就把路径上的颜色块爬下来树状数组求就行了,时间复杂度 $\mathcal O(n \log^2 n)$。 const int N = 1e5 + 7; s...
AtCoder Grand Contest 044 题解
AtCoder Grand Contest 044 Pay to Win 倒着考虑,记忆化搜索一下即可。 #define ll __int128 const int o[3] = {2,3,5}; const ll inf = 1e18; ll n, a[3], d; map<ll, ll> p; inline ll f(ll x) ...
USACO 2018-2019 Platinum 题解
USACO 2018 December Contest Balance Beam 单调栈求一个上凸壳即可。 卡精度,要用 __int128。 const int N = 1e5 + 7; int n; __int128 a[N]; vi s(1, 0); inline bool pd(int i, int j, int k) { ...
OI Blogs
一些神仙的博客,没脸放到友链上所以就放这儿来。 cz_xuyixuan hzwer immortalCO Matrix67 matthew99 mcfx Menci Miskcoo nocriz OwenOwl rqy Sengxian VFleaKing yww
JOISC 2019 题解
JOISC 2019 Day1 試験 (Examination) 裸的三维偏序模板题,$\mathcal O(n \log^2 n)$ 的 CDQ 分治即可。 const int N = 6e5 + 7; int n, m, a[N], c[N], t, ans[N]; struct P { int x, y, z, o; ...
USACO 2019-2020 Platinum 题解
USACO 2019 December Contest Greedy Pie Eaters 区间 dp。 考虑最后放上去的区间,必有一个位置被新覆盖了。 枚举这个位置即可,时间复杂度 $\mathcal O(n^3)$。 const int N = 307; int n, m, a[N][N...
Codeforces Round #641 (Div. 1) 题解
Codeforces Round #641 (Div. 1) Orac and LCM 每个质因子考虑一下即可。 namespace shai { const int N = 1e6 + 7; int p[N], v[N], phi[N], miu[N]; inline void init(int n) { v[...