【拾题杂谈】BZOJ4260 CodeChef REBXOR
题面题目链接大秦 为你打开 题目传送门
备用题面给定一个含 $N$ 个元素的数组 $A$ ，下标从 $1$ 开始。请找出下面式子的最大值：
$(A[l1]⨁A[l1+1]⨁…⨁A[r1])+(A[l2]⨁A[l2+1]…⨁A[r2])$
其中 $1≤l1≤r1<l2≤r2≤N$，其中 $x\bigoplus y$ 表示 $x$ 和 $y$ 的按位异或。
思路首先要做这道题我们有个构想，就是一类经典题，要求两个不重叠也不相邻的连续异或和最大值。如果是不是异或和，单纯的是加和的话，我们一定有人会做，就是前后缀最大子段和相加。
那么如果是异或的话，我们有这样的性质。$a\bigoplus a =0$ 就是说相同的数异或就相当于没有异或，有了这个性质我们可以有前缀异或和。就是用 $sum[i]$ 表示 $A_1 \bigoplus A_2 \bigoplus \cdots \bigoplus A_i $ 的值，那么如果是区间 $[l,r]$ 之间的数的异或和，就可以用 $sum[r] \bigoplus sum[l - 1]$ 。
然后如果我们把前缀最大值和后缀最大值分开算的话，单独的 ...
【拾题杂谈】517九段第十课B
题面题目链接大秦 为你打开 题目传送门
备用题面给定了一个树（一个无环无向连通图）包含 $N$ 个节点，以及编号为 $1$ 到 $N−1$ 的边。
你需要执行以下两种指令：
CHANGE i t ：将第 $i$ 条边的费用改为 $t$ 。
QUERY a b ：询问从节点 $a$ 到节点 $b$ 的路径上的最大边费用。
思路基础构建首先我们要有一个共识，就是遇到这种树上边权操作的题目一定要往边权转化为点权的思路上想一想。为什么这么说呢，如果是点权的话，我们可以遍历啊等等各种方式去维护，但是如果是边权就会变得麻烦，因为两个点之间就是一条边，我们可以认为图是若干条点与点的关系构成的，那么维护点肯定比维护边要方便，因为我们的数据记在点上就可以通过给出的若干关系来得出答案。
那么这种题我们要如何把点权转化为边权呢？这就有一个常用技巧。对于树上一条边来说，我们习惯把边的信息记载儿子方向的点上面，因为对于树来说，一个父亲可以有多个儿子，但是一个儿子只能有一个父亲，这样的映射关系就告诉我们存在儿子方面一定不会有冲突。
那么如果我们把一个问题的边权转化成了点权，那么这道题就从一个修改边权的问题变成 ...
【算法介绍】字典树算法
算法简介：流光的星火$\tt Trie$ 树，已经在曾经的文章中提及，但是说呢，并没有多提应用以及一些细节，所以说我们单独开一篇文章来讲 $\tt Trie$ 树。
友情链接：
【算法介绍】字符串算法 | 祝馀宫
那么字典树字典树，形如其名，就是字典形状的树。我们就是基于字典的顺序来排列，会在下文提到。
算法引导：长明的烛火那么所谓字典顺序，就是我们在做字符串比大小的时候说的字典序。如果看过英文字典的话，就会发现一个这样的规律：
优先按照字典序排序，意思就是按照每一位的字符顺序排，越靠前的位置权值越大。比如说对于字符串 abcd 和 bcda 第一位 a 小于 b 所以说 abcd 小。
如果一个串是另一个串的前缀，则短的那一个小。比如说对于字符串 abc 和字符串 abcd 那么显然就是 abc 更小。
知道了这个字典序的顺序，那么我们字典树又是怎么个东西呢？首先我们要明确的一点是，这个字典树是一个新的数据结构，肯定不会是像数组一样列表式存储，我们要有内存上和形式上的优化。再结合字典树中的 “树” 这个关键词，我们大致会有这样的猜想。
树的节点，或者树的边表示一个字符，然后 ...
【年度总结】回首与展望
77abf031e6414ecb2c71905320d5dd6a7d744d0cffe5461506da11afde159fd057ca4dfd641d39e51422ec9dac18839ed62f2e6b761f1ebacd8b1948bfee06381c616d05047ffc935b06a7dab5050fd4ecd8e6311aa85bc7a24334ce5dcced71d51d1754bb552c275e8da4675492bf99fb2c0aacbdaeaa521b2fcc591111f2ce24b275097b1b8f49382f231e2a424a95605eb1eb9b4d76036c90c14854d39c51587bbd5e314ffcad02f90498e51c4d823b339305d1dee4d1d341b2589e93dc473dc75d4a14eaa9efe352ba7c033dc5b487f9d589298db163f8a6c242e49314840e7f90bb532a53cc132a77f361eaa82f7854790ab67a1220e ...
【算法介绍】Manacher 算法
算法简介：鱼龙沉四方$\tt Manacher $ 算法，也叫马拉车；是一个用于求字符串中最大回文子串的算法。相同于 KMP，$\tt Manacher$ 也是一种基于字符串的自动机，他们的本质都是基于已知信息来求出未知信息解决问题。而从实现上来讲，$\tt Manacher$ 算法更加相似于拓展 KMP，到时候慢慢推出来就知道了。
友情链接：
【算法介绍】拓展KMP（Z函数） | 祝馀宫
算法小引：赫赫雷涌起我们首先从这个算法最最基础的模板开始：P3805 【模板】manacher - 洛谷 | 计算机科学教育新生态题目的意思很简单，要我们求一个字符串的最长回文子串。
那么首先考虑暴力，这里提一嘴，发现了一个很有趣的现象：同样是 $O(n^3)$ 的暴力，如果我们优先计算较短的回文串这题只能拿十八分，但是如果优先计算较长的回文串，答案会是原来的两倍也就是三十六分！这里贴上两次的代码以方便比较。
1234567891011121314151617181920212223242526// 18ptsinline void Work() { int n = strlen ...
【算法介绍】拓展KMP（Z函数）
算法简介：幽邃鸦眼首先说呢，这个拓展 KMP 其实和 KMP 关系不算特别大。我们定义了一个函数 $\operatorname Z(i)$ 表示字符串 $s$ 中 $s[1\dots n]$ 和字符串 $s[i\dots n]$ 的最长公共前缀的长度，这个函数被叫做 $\operatorname Z$ 函数，由于其代码实现相似于 KMP 算法，于是呢这个算法在国内被称为拓展KMP也就是说本名 $\operatorname Z$ 函数，小名拓展 KMP 。
算法演示：圣裁影羽那么首先的首先，我们要知道一个新的算法怎么做，我们肯定是从他的定义出发来看看暴力是怎么样的。那么说我们已经在简介中给出了 $\operatorname Z$ 函数的定义：函数 $\operatorname Z(i)$ 表示字符串 $s$ 中 $s[1\dots n]$ 和字符串 $s[i\dots n]$ 的最长公共前缀的长度。我们可以给出一个例子尝试一下。哦对了我们有一个特殊值 $\operatorname Z(1)=0$ 就是说原字符串和原字符串的最长公共前缀长度，本来说应该是 $n$ 的，但是被特殊定义成了 $ ...
【算法介绍】曼哈顿与切比雪夫距离
算法简介：外酥里嫩众所周知，我们在数学上的两点间距离一般指的是直线距离。也就是欧几里得距离，但是，这篇文章我们要讲的是另外两个常用的距离，曼哈顿还有切比雪夫距离。
所谓曼哈顿距离，对于二维直角坐标系来说，他就是两个点的横坐标之差还有纵坐标之差的和。我们还会用他来计算出切比雪夫距离的计算方式，所以说开始吧~
算法演示：大火宽油首先来看看曼哈顿距离，虽然说我们已经知道曼哈顿距离是什么，也知道怎么去求他，但是呢题目肯定不会考你模板的，所以说我们来一个经典例题试试水。
Clarke 是一位患有多重人格障碍的患者。有一天，他变成了一个几何学的学习者。他对一种有趣的距离一一曼哈顿距离进行了研究。点 $A(x_A,y_A)$ 和点 $B(x_B,y_B)$ 之间的曼哈顿距离是 $|x_A - x_B| + |y_A - y_B|$ 。现在他想要找到 $n$ 个点中任意两点之间的最大距离。
那么其实就是式子转化的问题，因为我们肯定不可以用 $n^2$ 复杂度过这道题，所以说我们要考虑一种类似线性的做法。这就要基于式子的变形了，我们发现这个绝对值非常的难受，所以说我们首先需要的就是去掉绝对值。
大力分讨 ...
【算法简介】递归与回溯
算法简介：如影流露的冷刃递归和回溯，亲家兄弟如影随形，几乎哪里都能看到他们，所以说这里的副标题是万物根基。递归的思想，相信都不陌生，就是把所有的问题分成小块小块的去解决。而回溯，就是在递归完了之后，往回走，再接着递归。这种一步一步的枚举方式，可以很方便的穷举出所有的情况结果，这个就是递归。
像我们熟知的算法动态规划，它最初的形态也是递归，不过因为递归的特性而不利于优化，所以呢后续就有了非递归形式的动规，而各种神奇的动规优化方式也接踵而来。
算法演示：层见叠出的谜象正如标题，层见叠出，就是递归的基本特征。对于斐波那契数列，相信大家都不陌生，我们可以用下列的函数来表示斐波那契的值：
\forall x\in \operatorname N^{\ast},\operatorname{f}(x)=
\begin{cases}
1 &{x\le 2}\\
\operatorname{f}(x-1) + \operatorname{f}(x-2) & \operatorname{other.}
\end{cases}这就可以称为递归的基本形式了。如果我们要求第 $3$ 个斐波那契数，就会根据函数 ...
![Math Combinatorial Counting [I]](https://image.jiuci.top/i/2025/01/01/h05d9w.png)
Math Combinatorial Counting [I]
Definition of Combinatorial CountingWe all have studied some basic Combinatorial Counting in primary , middle or high school. But now I still want to tell you the definition of Combinatorial Counting.
The Combinatorial Counting is a old things in math. Know we will get many branch in math that have some correlation with Combinatorial Counting.
I think the Combinatorial Counting is a way to discuss the method to calculate a combo of set. We all know we have such as problem in primary :
Problem : ...
【拾题杂谈】CF835F Roads in the Kingdom
题面：Roads in the Kingdom题面翻译题目描述
王国有 $n$ 座城市与 $n$ 条有长度的街道，保证所有城市直接或间接联通，我们定义王国的直径为所有点对最短距离中的最大值，现因财政危机需拆除一条道路并同时要求所有城市仍然联通，求所有拆除方案中王国直径的最小值。
输入格式
第一行一个整数 $n$，接下来 $n$ 行每行三个整数 $u,v,w$ 表示城市 $u,v$ 之间有一条长度为 $w$ 的道路。
输出格式
一行一个答案，表示所有方案中直径最小值。
题目描述In the Kingdom K., there are $ n $ towns numbered with integers from $ 1 $ to $ n $ . The towns are connected by $ n $ bi-directional roads numbered with integers from $ 1 $ to $ n $ . The $ i $ -th road connects the towns $ u_{i} $ and $ v_{i} $ and its lengt ...
