模板及讲解

高斯消元是什么

求解多元一次方程组的一个消元方法，主要借助矩阵来完成。

BZOJ 1013
题意：给定$n$维空间一个球面上$n+1$个点的坐标，求球心坐标。
提示：球心是到球面上任意一点距离都相等的点。

根据提示，我们设$a_{i,j}$为点$i$的第$j$维坐标，$x_{j}$为球心$j$维坐标，则对于每个点$i$ 有

$$
\sum_{j=1}^n (a_{i,j}-x_{j})^2=C
$$

其中$C​$为一个常数。这个方程是二元$n​$次方程，不好解，我们采用邻项相减的方法，使其变为一维以及消除$C​$，则

$$
\sum_{j=1}^n(a_{i+1,j}-x_{j})^2 - (a_{i,j}-x_{j})^2=0
$$

化简，将$x_j$移到左边，得

$$
\sum_{j=1}^n 2x_j(a_{i,j}-a_{i+1,j})=\sum_{j=1}^n(a_{i,j}^2-a_{i+1,j}^2)
$$

则可以构造矩阵高斯消元。

poj 2185
题意：求一个大矩阵的循环子矩阵，最后一个子矩阵可以作裁剪。
性质1：子矩阵位置在最左上方不会对答案造成影响。
性质2：行列上字母分布规律。
根据性质2，我们可以将每行 Hash，那么就只剩一行数，做一次 KMP 求最小循环节作为宽
列同理作为长
乘起来就是答案

CH 1809
题意：求字符串$A$每个后缀与$B$匹配次数。

字符串Hash做法：
将$A, B$都Hash，然后枚举$A$的后缀(起始位置)，然后现在关键看$A, B$能最多匹配多少位。那么根据字符串的一类单调性，我们运用二分，固定左端点，二分右端点，然后就能求出。

KMP做法：
还不会先空着 qwq

BZOJ 1500
题意：请写一个程序，要求维护一个数列，支持以下 $6$ 种操作：
请注意，格式栏中的下划线表示实际输入文件中的空格
.png)

用 splay 维护序列 (舍弃二叉排序树的左右儿子大小比较)：
插入：新建一棵 splay 插到原树上
删除：提取区间以后打删除标记，注意卡内存用辣鸡回收优化
修改：提取区间以后打标记，注意这里标记都是标时即改
翻转：提取区间以后打标记，若有修改标记则无需做任何事情
求和：提取区间输出区间和
求最长字段和：维护 $ls, rs$分别表示左起最长区间和，右起最长区间和。
则可以通过维护得到。

具体看Splay 学习笔记

模板及讲解

计算几何大坑

知识点

向量点积

几何方法：$\vec a \cdot \vec b=|\vec a||\vec b| \cos \theta$
坐标系：$\vec a(x_1,y_1), \vec b(x_2,y_2)，​$则$\vec a \cdot \vec b=x_1x_2+y_1y_2​$

判垂直：$\vec a ⊥ \vec b \Leftrightarrow \vec a \cdot \vec b = \vec 0$

向量叉积

几何方法：$\vec a \times \vec b=|\vec a||\vec b| \sin \theta$
坐标系：$\vec a(x_1,y_1), \vec b(x_2,y_2)，$则$\vec a \times \vec b=x_1y_2-x_2y_1$

判共线：$\vec a ∥ \vec b \Leftrightarrow \vec a \times \vec b = \vec 0$

向量旋转

设$\vec a(x, y)$，逆时针转角为$\theta$，则旋转后的向量为$(x\cos \theta-y \sin \theta, x \sin \theta+y \cos \theta)$

模板及讲解

Splay

Splay 就是平衡树。

Splay 的原理

例题 (不涉及区间操作)：Bzoj 3224

需要建立一个虚节点 0 作为初始根，加入一个正无穷和负无穷免除边界困扰。(类似 set)

核心操作：

• void rotate(int x)：对 $x$ 进行旋转操作
• void splay(int x, int gl = 0)：将 $x$ rotate 到 $gl$ 的孩子

辅助操作：

• bool rel(int x)：返回 $x$ 在 $fa[x]$ 中的左右位置
• void pushup(int x)：维护 $x$ 点信息 (更新)

实现操作：

• void insert(int x)：插入一个值为 $x$ 的节点并转到根
• void find(int x)：找一个值为 $x$ 的节点转到根，不存在则返回当前数的前驱或后继
• int kth(int k)：找值第 $k$ 大数
• int rnk(int x)：值 $x$ 的排名
• int pre(int x)：值前驱
• int succ(int x)：值后继
• void remove(int x)：删除一个值为 $x$ 的节点，若点还存在，转到根
  阅读全文 »

poj 3764
题意：给定一棵$n$个点的带权无向树，求树上路径异或和的最大值。

利用 Xor 性质，我们发现路径异或和满足容斥 (即$[l,r]$可由$[1,r]，[1, l-1]$得出)
那么我们求根到每个点的异或和$d_i$，然后尝试如何异或出一条路径来
我们发现任意两个$d_i,d_j$的异或和为某条路径的异或和，且不漏解
那么问题转化为求序列$d_i$两两异或最大值。
因为 Xor 常用 Trie 维护，所以我们可以运用 Trie 求这个最大值。将所有$d_i$以二进制形式插入 Trie (高位在上，定一个最大位数，不够在前面补0)，边权为二进制位，然后对于每个二进制下的$d_i$在Trie树上走尽量相反的边，因为这样保证异或后大。树上没有最优边那就只能走另一条边。这样下来的路径就是$d_i$与其他$d_j$的最大异或值。$O(n \cdot len)$操作即可，$len$为二进制最大位数。

BZOJ 2351
题意：给定$n \times m$大小矩阵，$q$次询问$a \times b$大小矩阵是否是大矩阵的一部分。

给行列分别hash一次，行先hash，然后将hash值再hash一次，即hash列

然后查询子矩阵Hash值直接像二维前缀和一样做即可，类比于一维的 Hash 方法

Codeforces 1084C
题意：给定一个$n$长小写字母序列，找出只包含a的子序列，满足每两个a之间有b，求方案数。
DP思想。从后往前扫，对每个a维护从这个位置开始顺序，这个位置必选的合法序列数量。
对于更新，不妨用b将序列分块，每个a只能继承他右边最近的一块的值。然后自身还有一个贡献，累加即可。

Codeforces 1084D
题意：树上每个点有正权值$a_i$，每条边有负权值$W$，你可以随意选择一条路径，使得这条路径的总权值最大，要求每个点每条边至多都只能走一次。
一开始想得好偏……
然而就是个树形DP，设$dp(u)$为$u$子树中的某个点到$u$的路径最长权。则转移为
$dp(u)=max(dp(v)-W(u,v)+a_u)$，当且仅当$dp(v)-W(u,v) \leq 0$
然后这样最后要统计每个点的$dp$值取个$max$就行了
等等，路径不一定是”直”的。所以我们要在DP每个点的过程中合并两条路径来得到”弯”的路径