题解

有 $N$ （ $1 \le N \le 35$ ）盏灯，它们的开关通过 $M$ （ $1 \le M \le 595$ ）条连接构成一个网络。 每盏灯都有一个开关，当你切换它时，该灯及所有与之直接相连的灯都会改变状态（开变关，关变开）。 请找出最少需要切换多少次开关，才能把所有灯都打开。 题目保证至少存在一种切换方案可以将所有灯点亮。 在这道题中，以邻接矩阵结合 $n\times 1$ …

Jayun 发布于 2025-08-18 13:50:52

00

很 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

题目大意 一个长度为 $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

题目大意 一个 $n\times m$ 的棋盘上填充着棋子，其中有一个空格。除了一些固定的棋子，空格相邻的棋子可以移动到空格上。一个棋盘上固定的棋子是确定的，给出 $q$ 个询问，对于每个询问回答，空格一开始在 $(ex,ey)$ 时， $(sx,sy)$ 上的指定棋子能否移动到 $(tx,ty)$ 和最少操作数。 $n,m\le30,q\le500$ . 思路 优先考虑初始位 …

Jayun 发布于 2025-06-21 05:00:58

10

题目大意 有 $n$ 个人做报告，第 $i$ 个人会使兴奋度 $x$ 变成 $a_i\lvert x\rvert+b_ix+c_i$ 。 初始兴奋度为 $s$ ，调整报告顺序使得最后的兴奋度最大。 $n,s,|a_i|,|b_i|,|c_i|\le15$ . 思路 调整顺序，范围又很小，于是考虑状压 DP。 贡献是分段函数，可以看作是端点在 $y$ 轴上的两条射线，并不是 …

Jayun 发布于 2025-06-18 20:44:39

10

题目大意 给定以 $1$ 为根结点的一棵树，有 $n(n\leq5\times10^5)$ 个节点，对于每个 $k\leq n$ ，求随机选取 $k$ 的结点的期望 LCA 深度，结果对 998244353 取模。 题解 考虑每个点 $u$ 的贡献为 $$\text{dep}(u)\left(\binom{|T_u|}{k}-\sum_{v\in\text{son}(u)}\bi …

Jayun 发布于 2025-06-16 21:07:38

10

题目大意 $n$ 排两列，塞 $n$ 对情侣，求恰好 $k$ 对情侣没有被拆散的数量。对 $998244353$ 取模。 题解 注意到，答案表达式为 $$\binom{n}{k}\cdot n^{\underline{k}}\cdot 2^k\cdot f_{n-k} $$ 其中 $f_i$ 是 $i$ 对情侣全被拆散的数量。有 $$f_i=4i(i-1)\left(f_{ …

Jayun 发布于 2025-06-12 21:26:59

10

给定 $n$ , $p$ , $r$ , $k$ ( $1\le n\le 10^9$ , $0\le r,2\le p\le 2^{30}-1$ )，求 $$\sum_{i\bmod k=r}{nk\choose i}\bmod p $$ 题解 $$\begin{aligned}&\sum_{i\bmod k=r}{nk\choose i}\\=&\sum_{i\bm …

Jayun 发布于 2024-03-01 14:13:10

10

Maximize Mex 题面 在一所学校里有 $n$ 名学生和 $m$ 个社团，社团被编号为 $1$ ~ $m$ 。第 $i$ 个学生有一个能力值 $p_i$ ，且属于社团 $c_i$ （每个学生恰好属于一个社团） 。 学校将要举行一个为期 $d$ 天的活动，每天学校要举行一场程序设计比赛 —— 校长将会从每个社团中各选出一个人（如果某个社团没有人，就不选）组成一个 …

Jayun 发布于 2024-02-29 18:32:31

00