Solutions

题目大意 二维平面上有一些点，保证不存在重合的点和三点共线。求每一个点集的凸包在平面上包含的点数的和。 $n\leq1000$ 。 题解 有趣的。 假如所有点都在所有凸包内，答案 $n2^n$ 。 考虑斥掉不合法的。对于一个点对，它们直线分割的半平面，两个平面内的点不能同时取。那么枚举一个点，把所有点挪到以它为原点的坐标系，然后极角排序，双指针维护半平面的区间即可。 本题的启发：如果有“不存在 …

Jayun 发布于 2023-11-16 16:43:52

00

[AGC001E] BBQ Hard 题面 有 $n$ 个数对 $(a_i, b_i)$ ，求出 $$\sum_{i=1}^{n}\sum_{j=i + 1}^{n}{a_i+b_i+a_j+b_j \choose a_i+a_j} $$ 答案对 $10 ^ 9 + 7$ 取模。 $n\leq10^5,a_i,b_i\leq2000$ 。 题解 考虑组合意义，相当于横着走 $a_i+ …

Jayun 发布于 2023-11-16 07:39:36

00

题意 在一棵树上，边有边权，给定 $k$ 个特殊点，对于每个点 $i$ 求，从 $i$ 出发必须经过所有特殊点的最短路径长度（可重复）。 $n,k\leq10^5$ 。 题解 不能直接对 dfn 排序然后线性做因为不对。 考虑树形 DP，答案就是从 $i$ 出发到每个有点的儿子一来一回，最终减去最长链，也可以跑到父亲那里，换根即可。对于最长链，有时需要次长链更新。 const i …

Jayun 发布于 2023-11-15 20:21:26

00

退火。 const int N = 1e3 + 5; inline ll Read() { ll x = 0, f = 1; char c = getchar(); while (c != '-' && (c < '0' || c > '9')) c = getchar(); if (c == '-') f = -f, c = getchar(); whil …

Jayun 发布于 2023-11-15 16:39:38

00

题意 给出一棵大小为 $n$ 的树，和两个值 $p,q$ ，求有多少个四元组 $(a,b,c,d)$ 满足路径 $a\rightarrow b$ 的长度是 $p$ ，路径 $c\rightarrow d$ 的长度是 $q$ ，且两路径不交。 $n,p,q\leq3000$ 。 口胡 考虑容斥转化问题为求交的。交有两种情况，两条路径的 LCA 都是同一个点；一条路径穿过另一条 …

Jayun 发布于 2023-11-15 08:10:28

00

板题，只放代码。 const int N = 3e5 + 5; inline ll Read() { ll x = 0, f = 1; char c = getchar(); while (c != '-' && (c < '0' || c > '9')) c = getchar(); if (c == '-') f = -f, c = getchar(); …

Jayun 发布于 2023-11-14 21:40:39

00

KDT 板子，但被卡了。 const int N = 4e5 + 5, K = 2; const ll inf = 1e16; inline ll Read() { ll x = 0, f = 1; char c = getchar(); while (c != '-' && (c < '0' || c > '9')) c = getchar(); if (c …

Jayun 发布于 2023-11-13 21:50:47

10

题意 $n$ 点树， $q$ 次询问，给 $m$ 个特殊点。树上每个点由最靠近它的特殊点控制，如果距离相同取编号小的。问每个特殊点控制多少点。 $n,q,\sum m\leq3\times10^5$ 。 题解 虚树。然后考虑树形 DP，从下往上扫一遍从上往下扫一遍。细节很多。 代码 const int N = 3e5 + 5, INF = 0x3f3f3f3f; inline ll …

Jayun 发布于 2023-11-12 21:42:33

00

题意 给定一棵树，多组询问，每组询问给定 $k$ 个点，你可以删掉不同于那 $k$ 个点的 $m$ 个点，使得这 $k$ 个点两两不连通，要求最小化 $m$ ，如果不可能输出 $-1$ 。询问之间独立。 $n,q,\sum k\leq10^5$ 题解 特殊点作为关键点，将关键点按 $\mathrm{dfn}$ 排序，求出相邻点的最近公共祖先也作关键点，按照原树祖先后代关 …

Jayun 发布于 2023-11-12 20:44:28

00

板。 const int N = 3e5 + 5; inline ll Read() { ll x = 0, f = 1; char c = getchar(); while (c != '-' && (c < '0' || c > '9')) c = getchar(); if (c == '-') f = -f, c = getchar(); while …

Jayun 发布于 2023-11-12 20:21:20

00