ARC101F Robots and Exits 题意 数轴上有 $n$ 个 A 类点 $A_i$，$m$ 个 B 类点 $B_j$，任意两点的坐标都是整数且互不相同。 每次操作可以让所有 A 类点同时向左或者向右移动一个单位。 如果在某个时刻 $A_...

ARC103D Robot Arms 题意 平面上有 $n$ 个整点 $(x_i, y_i)$。 要求构造出一个长度为 $m(\in [1,40])$ 的整数序列 $d(\in [1,10^{12}])$，满足 $d$ 可以生成所有整点。 称一个整数序列 $d_{1\dots m}$ 可...

ARC093E Bichrome Spanning Tree 题意 给定一张 $n$ 个点 $m$ 条边的无重边无自环的无向图，边有边权。 求给边染黑白两色，使得包含两种颜色的边的边权和最小的生成树的边权和恰好为 $X$ 的方案数。 $n \l...

ARC103F Distance Sums 题意 有一棵 $n$ 个点的树。 对于每个点 $i$，已知 $d_i$，表示 $\sum_{j=1}^n \operatorname{dist}(i,j)$。 所有 $d_i$ 两两互不相同。 构造出一棵符合要求的树，或者判断无解。 $...

JOI Final 2020 長いだけのネクタイ (Just Long Neckties) 显然 $a,b$ 排序后对应位置上的数相减最优，multiset 维护一下即可，时间复杂度 $\mathcal O(n \log n)$。 const int N = 2e5 + 7; int n, a[N],...

AtCoder Grand Contest 043 Range Flip Find Route 注意到，最后走的路线一定是黑白交替的。 每一次翻转颜色都一定是在进入黑色的时候，将后面一段黑色的路变成白色。 这与最短路很类似，由于边权只有 $0...

Codeforces Round #635 (Div. 1) Linova and Kingdom 设深度为 $d$，子树大小为 $s$，点 $i$ 对答案的贡献为 $d_i - s_i + 1$，从大到小贪心就好了。 const int N = 2e5 + 7; int n, k, d[N], s[N]; vi e[...

莫队算法是由莫涛提出的算法，可以解决一类离线区间询问问题，适用性极为广泛。同时将其加以扩展，便能轻松处理树上路径询问以及支持修改操作。 普通莫队 设定块大小 $T$，将 $m$ 个询问 $[l,r]$ 离线下来...

【LGR-071】洛谷 4 月月赛 & MdOI Round 2 Div.1 Odyssey 首先预处理所有数的分解式，次数模上 $k$。 然后 DP，设 $f_{i,j}$ 为到点 $i$ 且上一条边的权值为 $j$ 的最短路，DAG 转移即可，有效的状态...

其实不是什么学习笔记，只是稍微整理一下。 排列组合 排列 从 $n$ 个元素中有序的选择 $k$ 个元素的方案数： $$ n(n-1)(n-2)\cdots(n-k+1) = \frac{n!}{(n-k)!} = n^{\underline{k}} $$ 组合 从 $n$ 个...