xixike

# Description 洛谷传送门 # Solution KruskalKruskalKruskal 重构树好题。 我们先按照水位 aaa，建 KruskalKruskalKruskal 重构树。具体来讲：按水位从高到低排序，每次选出剩余边中水位最高的一条边插入到树中，这样就建成了一个小根堆。 然后我们再来考虑询问。 对于一个水位线 ppp，若 p<Kruskalp < Kruskalp<Kruskal 重构树上的点 xxx 的水位，那么在以 xxx 为根的子树中，开车是可以随意通行的，对答案没有贡献。 若 p>t[x].depp...

# Description Luogu 传送门 # Solution 首先有一个明显的结论，如果两个子串是 iii 相似，那么它们也一定是 1≤j≤i1 \leq j \leq i1≤j≤i 相似。 所以我们可以通过 SA 把 height 数组求出来，然后从大到小排序，并依次枚举。 每次对两个相邻的后缀进行处理，把它们两个所在的并查集合并。 考虑合并都有哪些操作，回顾一下问题，我们需要计算 kkk 相似的个数及最大权值。 先看个数：由于我们是按 height 数组从大到小枚举的，所以已经在并查集里的子串一定是合法的，所以 ans1+=sizx×sizyans_1 += siz_x...

# Description Luogu 传送门 # Solution 观察到数据范围：状压就你了！ 于是我们快乐地使用状压 dpdpdp 来解决这个问题。 首先我们开一个 match[i][j]match[i][j]match[i][j] 数组表示所有字符串第 iii 位能否匹配 j∈a⋅⋅⋅zj \in a···zj∈a⋅⋅⋅z（这个描述起来有点抽象，可以根据代码理解一下）。 然后就是 dpdpdp 了，我们设 dp[i][k]dp[i][k]dp[i][k] 表示第 iii 位匹配 k(k∈a⋅⋅⋅z)k(k \in a···z)k(k∈a⋅⋅⋅z)...

# Description Luogu 传送门 说实话我感觉这题说的还挺迷的，看了好久题意才看懂 QwQ 这里稍微解释一下吧，就是初始的时候给你一个字符矩阵，上面有黑白两种格子，保证黑格子四联通。 然后你需要扩展这个字符矩阵。 简单来说，假设当前矩阵为 kkk 级矩阵，要扩展成 k+1k + 1k+1 级矩阵，我们把黑格子变成当前字符矩阵（kkk 级矩阵）的样子，白格子就变成当前字符矩阵大小的全白格子。 这是样例一的 2...

模板题：P5854 【模板】笛卡尔树 # 定义 无相同元素的数列构造出的笛卡尔树具有下列性质： 结点一一对应于数列元素。即数列中的每个元素都对应于树中某个唯一结点，树结点也对应于数列中的某个唯一元素 中序遍历（in-order traverse）笛卡尔树即可得到原数列。即任意树结点的左子树结点所对应的数列元素下标比该结点所对应元素的下标小，右子树结点所对应数列元素下标比该结点所对应元素下标大。 树结构存在堆序性质，即任意树结点所对应数值大 / 小于其左、右子树内任意结点对应数值 根据堆序性质，笛卡尔树根结点为数列中的最大 / 小值，树本身也可以通过这一性质递归地定义：根结点为序列的最大 /...

# Day -2 大晚上的在机房颓废时，教练突然进来。 曰：“现在疫情又有反复，大家把核酸证明什么的都上传好，去秦皇岛也带上，多带点口罩和酒精湿巾，在火车上一直戴着口罩，向 fzj 学习，口罩不离嘴。” stostosto 房神 orzorzorz，真・防疫好少年。 然后教练继续曰：“到时候还要查健康码，大家能带手机的都带上。” 都…… 带…… 上……（为什么其他学校都是不让带手机，到了我们这里变成了强制带手机……） 没手机的咋办？感觉要凉凉，CSP RP−−CSP \...

哈哈输出大样例能得的分都比打了 3.5h 得分高。 # A. 「清华集训 2017」小 Y 和恐怖的奴隶主 期望 dp + 矩阵乘法 看完题之后比较晕，没有想到把 1，2，3 血的怪的数量都记录下来，整个 4 维期望 dp，直接跳过了，有点亏。 设状态 dp[i][a][b][c]dp[i][a][b][c]dp[i][a][b][c]，表示打了 iii 次之后场上 1，2，3 血的怪物分别有 a,b,ca, b, ca,b,c 只。 暴力转移显然会 TLE。 不难发现，总共只有 165 个状态，加上答案状态就是 166 个状态，所以可以编个号，然后压到一维里，使用矩乘加速。 code #...

# 一级标题 # 二级标题 # 三级标题 # 四级标题 # 五级标题 # 六级标题 sum=∑i=1nai×bisum = \sum_{i = 1}^{n}a_i \times b_i sum=i=1∑n​ai​×bi​ 无序列表 1 无序列表 2 无序列表 3 无序列表 4 有序列表 1 有序列表 2 有序列表 3 有序列表 4 普通引用 行高亮参考链接import java.util.Scanner;...Scanner in = new Scanner (System.in);// 输入 Scan 之后，按下键盘 Alt + “/” 键，Eclipse...