题意 题目链接。 给定一张有向无自环图，求一个点集满足： 点集内任意两个不同点距离不小于 $2$（即无边相连）。 对于任意一个不在点集内的点，存在一个点集内的点到它的距离不大于 $2$（即两步能达）。 解析 算法实现与 @Mickey_snow、@_Anchor 等题解类似，本篇题解主要重申一种可能更清晰的证明以及错解的 Hack。 简单阐述解法：…

题意 题目链接。 题意有点复杂，大意是有一个猎杀游戏，有 $m$ 名玩家，每名玩家初始有 $3$ 点生命。有 $n$ 个时刻，每个时刻会发生形如 $u_i$ 杀 $v_i$ 的事件，若 $u_i$ 和 $v_i$ 都存活，则 $v_i$ 生命值减 $1$，若生命值为 $0$ 则死亡。现在发生了一次特殊事件：穿越者穿越到某一次追杀后（可以是第 $0$…

题意 题目链接。 有 $n$ 只袜子，每只袜子都可能是左/右袜子且有一种颜色。每次操作你可以：改变袜子的颜色或改变袜子的左右性。你需要使左右袜子一一配对（具体地，若两只袜子一左一右且颜色相同，则这两只袜子配对）。求最小操作数。 解析 首先由于左右袜子必须要一一配对，所以两者数量一定要相等，因此答案最小为 $|\frac{l-r}{2}|$，即我们至…

[hermit autoplay="true" mode="random" preload="auto"]netease_playlist#:6727894619[/hermit] 歌单链接：网易云音乐 若歌曲无法正常播放或未显示播放器，请刷新，若刷新无用，大概率是 cookie 失效了，可以联系我。 高台树色 - 穿堂惊掠琵琶声 作者：高台树色 …

题意 题目链接。 一共有 $n$ 个格子，给定两个整数 $A,B$ 分别位于第 $1$ 和第 $n$ 格，中间有 $n-2$ 个空格。询问是否存在一种填数方案满足任意相邻两个数之差的绝对值在 $[C,D]$ 之间。 解析 考虑这 $n$ 个数之间有 $n-1$ 对差，因此题目等价于： 是否存在 $A+\sum\limits^{n-1}_{i=1} …

一段时间没打字符串相关的题了，找道简单的 Trie 练练手。 题意 题目链接。 维护一个复古打印机，支持添加字母，删除字母，打印字母。求用最小步骤打印出所需的所有单词。 解析 首先容易想到建 Trie，然后在 Trie 上进行 dfs，每次走到一个结点就添加这个结点对应的字母，若走到了一个单词的结尾就打印，然后在每层 dfs 返回之前删除当前字母。…

题面 如图为某种常染色体隐性遗传病的系谱图（深色代表的个体是该遗传病患者，其余为表型正常的个体）。近亲结婚时，该遗传病发病率较高，假定图中第 Ⅳ 代的两个个体婚配生出一个患有该遗传病子代的概率是 $\frac{1}{48}$，那么，得出此概率值需要的限定条件是（　　）。 A．Ⅰ-2 和Ⅰ-4 必须是纯合子 B．Ⅱ-1、Ⅲ-1 和 Ⅲ-4 必须是纯合…

本博客仅罗列定理，不给出证明，如需要请自行搜索。 质数相关 线性筛素数 inline void sieve(int n){//线性筛求 pri 和 phi phi[1]=1; for(int i=2;i<=n;i++){ if(!vis[i]){phi[i]=i-1;pri[++cnt]=i;} for(int j=1;j<=cnt&a…

题意 题目链接。 有一张 $n\times\ n$ 的网格，有 $1,2,3$ 三种颜色，每轮交互库会给出一种颜色，你需要在剩余两种颜色中选一种颜色涂在一个格子上，不可以使任何两个相邻格子颜色相同。你需要扮演涂色者将所有格子涂上颜色。 解析 首先我们考虑到，如果有一个空格子，其上下左右四个格子中有两种颜色，你就输了（因为交互库可以一直给出剩余的这种…

[hermit autoplay="false" mode="circulation" preload="auto"]netease_songlist#:551339691[/hermit] あぁ、少年の僕らよ 啊，少年的我们 情熱の日々も、約束もまた 如果热情的日子和约定也 消えてしまうなら 消逝的话 過ぎ去ってしまうなら 变成过去的话 ここに残…