题解
Greatest of the Greatest Common Divisors
题意
给定一个长度为 $n$ 的序列 $a_i$ 和 $q$ 个询问，每个询问求出 $[l,r]$ 内所有数对的最大公约数中的最大值。
$n,q\leq10^5$ 。
思路
经典正难则反：不好直接求 GCD 就考虑约数的贡献。
然后类似扫描线的思想，离线后把时间作为一个维度处理区间信息，这里用树状数 …
Jayun 发布于 2025-09-13 20:21:23
00
[ICPC 2024 Yokohama R] Tree Generators
题意
规定表达式生成树的操作。根据以下过程，从一个表达式生成一棵树。
表达式 $\texttt{1}$ 生成一棵仅包含一个标号为 $1$ 的节点的树。
对于两个表达式 $E_1$ 和 $E_2$ ，表达式 $(E_1E_2)$ 按如下方式生成一棵树：
从 $E_1$ 生成一棵拥有 $n_1$ …
Jayun 发布于 2025-09-13 18:59:45
00
Dijkstra
题意
给定一张 $n$ 个点， $m$ 条边的无向图，有点权 $p_i$ ，边权 $q_i$ 。生成树的权值为
$$\sum_{e\in E}q_e\sum_{u\in\text{inaccessible}(e)}p_u
$$
其中 $\text{inaccessible}(e)$ 表示从生成树中删除 $e$ 后，从 $1$ 出发不能到达的结点集合。
求可能的最小权值。
思路 …
Jayun 发布于 2025-09-13 16:39:24
00
题意
给定一种构建树的方式，给出 $n-1$ 个操作，每次操作给出 $u,v$ ，只能从 $u$ 所在的连通块内随机选一个点连向 $v$ 所在连通块内随机的点
Jayun 发布于 2025-09-01 13:35:50
00
题意
给定一个由 $n$ 个点组成的凸包， $q$ 次询问，每次询问给出一个圆，求出从凸包到圆各处最小期望长度。
$n,q\leq5000$ 。
题解
如果圆心在凸包里直接从圆心出发，否则看圆心到凸包的距离。
代码
const int N = 5010;
const ld eps = 1e-6;
inline ll read() {
ll x = 0, f = 1;
char c = …
Jayun 发布于 2025-08-30 14:35:51
00
高斯消元
有 $N$ （ $1 \le N \le 35$ ）盏灯，它们的开关通过 $M$ （ $1 \le M \le 595$ ）条连接构成一个网络。
每盏灯都有一个开关，当你切换它时，该灯及所有与之直接相连的灯都会改变状态（开变关，关变开）。
请找出最少需要切换多少次开关，才能把所有灯都打开。
题目保证至少存在一种切换方案可以将所有灯点亮。
在这道题中，以邻接矩阵结合 $n\times 1$ …
Jayun 发布于 2025-08-18 13:50:52
00
线性动态规划（线性 DP）
很 naive 的一个想法是双向 BFS，但是 $n$ 太大不管用。
$S$ 与 $T$ 的异或值和操作一相关； $T$ 的值相同区间和操作二三相关。
11100101
11110000
00010101
对于 $T$ 的值相同区间且 $S$ 在此区间未成为目标，是否一定需要对此区间进行操作二三？
否：当有一个更大的区间可以进行操作一使得至少两个值相同区间得到满足。而操作一是 …
Jayun 发布于 2025-08-12 22:46:40
00
【MX-S4-T2】「yyOI R2」youyou 不喜欢夏天
题目描述
youyou 有一个大小为 $2 \times n $ 的网格，每个格子可能是黑色或者白色。
现在 youyou 和 yy 要在这个网格上玩一个游戏：
youyou 先选取出一个可以为空的连通块。
之后 yy 可以选择网格中最多 $m$ 列，将这些列上下行的格子颜色互换。
定义一个格子集合 $S$ 为一个连通块， …
Jayun 发布于 2025-08-12 16:34:23
00
线性动态规划（线性 DP）
题目大意
一个长度为 $n$ 的排列 $\{P_i\}$ 的价值为
$$\sum_{i=2}^n|P_i-P_{i-1}|
$$
给定 $n,m,k$ ，求出长度为 $n$ ，价值不小于 $m$ 的排列的频率，保留小数点后 $k$ 位。
$n\le 100$ .
思路
不难想到用 DP 实现。暂且先考虑设 $f_{i,j}$ 表示填了 $i$ 个位置，且价值达到 $ …
Jayun 发布于 2025-06-24 01:02:37
10
SPFA
题目大意
一个 $n\times m$ 的棋盘上填充着棋子，其中有一个空格。除了一些固定的棋子，空格相邻的棋子可以移动到空格上。一个棋盘上固定的棋子是确定的，给出 $q$ 个询问，对于每个询问回答，空格一开始在 $(ex,ey)$ 时， $(sx,sy)$ 上的指定棋子能否移动到 $(tx,ty)$ 和最少操作数。
$n,m\le30,q\le500$ .
思路
优先考虑初始位 …
Jayun 发布于 2025-06-21 05:00:58
10