【拾题杂谈】[USACO5.4] 周游加拿大Canada Tour
题面：周游加拿大Canada Tour题目描述你赢得了一场航空公司举办的比赛，奖品是一张加拿大环游机票。旅行在这家航空公司开放的最西边的城市开始，然后一直自西向东旅行，直到你到达最东边的城市，再由东向西返回，直到你回到开始的城市。除了旅行开始的城市之外，每个城市只能访问一次，因为开始的城市必定要被访问两次（在旅行的开始和结束）。
当然不允许使用其他公司的航线或者用其他的交通工具。
给出这个航空公司开放的城市的列表，和两两城市之间的直达航线列表。找出能够访问尽可能多的城市的路线，这条路线必须满足上述条件，也就是从列表中的第一个城市开始旅行，访问到列表中最后一个城市之后再返回第一个城市。
输入格式第 $1$ 行: 航空公司开放的城市数 $N$ 和将要列出的直达航线的数量 $V$。$N$ 是一个不大于 $100$ 的正整数。$V$ 是任意的正整数。
第 $2\sim N+1$ 行: 每行包括一个航空公司开放的城市名称。城市名称按照自西向东排列。不会出现两个城市在同一条经线上的情况。每个城市的名称都 是一个字符串，最多 $15$ 字节，由拉丁字母表上的字母组成；城市名称中没有空格。
第 $N+ ...
【奇技淫巧】我做到了一类特殊动态规划……
起因我满怀欢喜的打开洛谷，发现洛谷 USACO 的绿色DP只剩下了这道！于是粗略扫了一眼，马上编码，炸了！好吧看错了题，事情又变得疏忽迷离……
题面题目传送门
题目描述传说，数千年前圣帕特里克消灭了哞尔兰所有的蛇。然而，蛇们现在卷土重来了！圣帕特里克节是在每年的3月17日，所以Bessie要用彻底清除哞尔兰所有的蛇来纪念圣帕特里克。
Bessie装备了一个捕网，用来捕捉 $ N $ 组排成一行的蛇（ $ 1 \leq N \leq 400 $ ）。Bessie 必须按照这些组在这一行中出现的顺序捕捉每一组的所有蛇。每当 Bessie 抓完一组蛇之后，她就会将蛇放在笼子里，然后带着空的捕网开始捕捉下一组。
一个大小为 $ s $ 的捕网意味着 Bessie 可以抓住任意包含 $ g $ 条的一组蛇，其中 $ g \leq s $ 。然而，每当 Bessie 用大小为 $ s $ 的捕网抓住了一组 $ g $ 条蛇，就意味着浪费了 $ s-g $ 的空间。Bessie 可以任意设定捕网的初始大小，并且她可以改变 $ K $ 次捕网大小（ $ 1 \leq K<N $ ）。
请告诉 B ...
【奇技淫巧】环形动态规划设计
算法简介：占理不饶人环形动态规划，是我们做动归过程中极其常见的一种类型。它的推导过程有时候非常循规蹈矩，或者说存在一些特定的思路来搞定，正巧遇到了新的一种做法，于是写了这篇文章讲一下。
我们都知道，环形动态规划的特点，就是维护结构是一个环。环的特殊之处就是相对于线性结构，就是数组这类来说，数组只会影响前一个或者后一个，如果在开头或者结尾就溢出之类的。
但是如果是环状结构，就会发现他们的特殊处在于最后一个会影响第一个，第一个会影响最后一个，这样的存在让我们非常难受，于是乎，就会有下面几种特殊的方式来转化环状结构。
算法演示：最终解释权那么说到转化环结构，常见的有两个方式。
第一个，暴力点，常见的破环为链
第二个，斯文点，罕见的分讨结果
但是他们的相同之处在于都是运用一种转化来使环变为线性结构的形式，只不过表现形式不同而已。我们下面可以用两个例题来大致认识一下这两种方法。
算法例一：真火炼宝印直接上题！
题目大意在一个圆形操场的四周摆放 $N$ 堆石子，现要将石子有次序地合并成一堆，规定每次只能选相邻的 $2$ 堆合并成新的一堆，并将新的一堆的石子数，记为该次合并的得分。
试设计出一个 ...
【拾题杂谈】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$ 复杂度过这道题，所以说我们要考虑一种类似线性的做法。这就要基于式子的变形了，我们发现这个绝对值非常的难受，所以说我们首先需要的就是去掉绝对值。
大力分讨 ...