xixike

扫描线，数论 + 找规律，dp + kmp

数论, 树的直径 + 优化建图, 01trie及其特殊操作

# 前言 刚开始学 OIOIOI 的时候学过对拍，但是后来基本上没有用过。 （暴力都不会写什么对拍） 临近 CSPCSPCSP 稍微复习了一下，于是写一篇博客记录一下（以后忘了还可以看）。 # 正文 # 方法 # 1. 准备好你需要对拍的程序 a.cpp 123456789101112#include <iostream>#include <cstdio>#include <algorithm>using namespace std;int main(){ long long a, b;...

# 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...

贪心 + 对顶堆, AC自动机 + 树状数组, Tarjan缩点 + 拓扑排序

逆康托展开 + 高精度, 抽屉原理 + set, 线段树分治 + 可撤销并查集

模板题：P5854 【模板】笛卡尔树 # 定义 无相同元素的数列构造出的笛卡尔树具有下列性质： 结点一一对应于数列元素。即数列中的每个元素都对应于树中某个唯一结点，树结点也对应于数列中的某个唯一元素 中序遍历（in-order...