【拾题杂谈】POJ1734 Sightseeing trip
题面题目链接大秦 为你打开 题目传送门
题目翻译找出带权无向图图上至少有三个的最小环，若无解，输出 No Solution. ，图的节点数不超过 $100$ ，边数不超过 $10000$ ，每条边的权值小于等于 $500$ 且大于 $0$ 。
思路这个数据范围一眼顶针就是 Floyd 算法，但是我们如何去求最小环就变成了问题。我们考虑一个环是如何组成的（前提是环的一部分是最短路）见下图：
这样是一个环的组成部分，那么就可以用这个思路，去得到最小环的权值，但是问题现在又来了，如何得到环上的点。我们发现 Floyd 每次在进行松弛操作会有一个中转点，我们记录这个中转点，不断还原出原路径即可。
代码1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495969798991001011021 ...
【算法介绍】最短路算法
算法简介：晶片也是一种宝石这篇文章主要讲的是最短路径算法，从最低级的 Floyd 开始，到支持最长路的 Dijskra 的初级代码及其优化，还有支持负边权的 Bellman-Ford 算法。最短路径问题作为图论中解决大多数问题的基础，可以与很多图论模型混搭，是一个泛用型很强的问题类型。
算法演示：不能少了冲天转转例一：改良型平衡稳定器首先，作为多个最短路算法的始祖（可能吧，毕竟这个是基础）一些关于最短路的基础概念都是由 Floyd 算法引导出来的，所以我们首先来讲的算法，就是 Floyd 算法。
首先，我们给定一张图。不管他是无向图还是有向图，我们都可以求最短路。而计算出来的最短路，分为两种：
求出一个点到所有点之间的最短路 —— 单源最短路
求出所有点到所有点之间的最短路 —— 全源最短路
那么我们要用的 Floyd 算法，就是求全源最短路的一个最短路算法。试想一下，如果要求我们在 $O(n^3)$ 的时间复杂度内，实现全源最短路，我们会怎么做？不难想到，就是动态规划。
如果我们设置一个状态 $dp[u][v]$ 表示点 $u$ 到 $v$ 的最短路，那么怎么去求最短路呢？ 不难 ...
【拾题杂谈】LuoguP2619 [国家集训队] Tree I
题面：[国家集训队] Tree I题目链接大秦为你打开题目传送门
题目描述给你一个无向带权连通图，每条边是黑色或白色。让你求一棵最小权的恰好有 $need$ 条白色边的生成树。
题目保证有解。
输入格式第一行 $V,E,need$ 分别表示点数，边数和需要的白色边数。
接下来 $E$ 行，每行 $s,t,c,col$ 表示这边的端点（点从 $0$ 开始标号），边权，颜色（$0$ 白色 $1$ 黑色）。
输出格式一行，表示所求生成树的边权和。
样例 #1样例输入 #11232 2 10 1 1 10 1 2 0
样例输出 #112
提示对于 $5\%$ 的数据，$V\leq 10$。
对于另 $15\%$ 的数据，$V\leq 15$。
对于 $100\%$ 的数据，$V\leq 5\times10^4,E\leq 10^5$。
所有数据边权为 $[1,100]$ 中的正整数。
By WJMZBMR
思路首先，要达到最小生成树固定颜色边的目的，最首要的部分就是控制权重。但是发现如果单一的规定白色边或者黑色边排在前面，满足不了一定是 need 条白色边的需求，所以不难想到枚举给白色边的加 ...
【算法介绍】最小生成树
算法简介：割舍怜悯之心最小生成树，就是一张图一直删边，直到删成一颗树为止，这叫做生成树，如果这个生成树的边权之和是所有生成树中最小的，那么他被称为最小生成树，前面我们讲过了一个叫做 Boruvka 的算法，虽然他确实是求最小生成树的方法之一，但是他过于远古，不太常用，代码也不如 kruskal 简单，所以说，我们这里将介绍两种新的最小生成树算法，请看副标题 —— Prim & kruskal 。
算法演示：割舍侥幸之心那么最小生成树，生成树生成树，总归就是树，有两种组成部分，一是点，二是边，而 Prim 和 kruskal 算法分别就是代表了基于点的贪心和基于边的贪心，我们来一个逐个击破。
点贪心：割舍痛苦之心首先就是 Prim 算法，他之所以被称为点贪心，是因为这样一个思路：
生成树，必须要把一个图的所有点连起来，变成一个树，也就是说，所有点，我们都将出现在最终的点集合里。所以，我们一开始随便选择一个点，加入最小生成树点集合，然后每次去寻找和我们最小生成树点集合最近的一个点，这样就可以保证每次选出来的边是最短的，然后就一直循环往复，直到所有点都选完。
然后，我们就发现，这样的 ...
【算法介绍】线段树合并
算法简介：悬星尽散击云碎一般来讲，我们在大值域的权值线段树问题的时候，都会考虑把它变成离线的，然后进行线段树操作。但是，以万恶的出题人视角，一定会把这唯一的路给断掉，也就是强制在线的大值域权值线段树问题，那么我们就要考虑到动态开点权值线段树了。至于动态开点线段树的应用……想必都知道了吧 —— 线段树合并。
算法演示：璇玑合璧镇昆仑第一部分：星罗宿列天权临那么既然要讲的是动态开点权值线段树的应用，自然要讲动态开点权值线段树。那么我们首先来想，动态开点权值线段树的内存理论应该是多少。首先我们想权值线段树的内存，就和普通线段树一样，都是开了 $4N$ 的，那么如果是动态开点，显而易见我们就可以达到线段树的理论内存，$N\log V$ 其中，$N$ 是数据范围，$V$ 是值域。
有人可能想不通：我们都不知道数据里面最大的那个数，怎么开始数组，怎么建树，怎么往下递归寻找答案？
上面这个有人是谁，我也不知道，但是有没有一种可能，我们是动态开点，我们不需要建树，我们的内存就是 $N\log V$ ，内存直接开到这么大就够了，也就是一般来讲的 N<<5 。这个 $5$ 的出处是 $2^ ...
【算法介绍】KMP算法
算法简介：巡护深林KMP 算法，虽然我们已经在 【算法介绍】字符串算法 | 祝馀宫 中提及，但是现在有了更深的理解，我们这篇文章单独讲 KMP 算法以及其原理。为了凑字数，我们再讲一遍废话。 KMP 算法，全称 $Knuth-Morris-Pratt$ 算法，通过一种特殊的性质匹配两个字符串，从而达到减少匹配次数的算法。
算法演示：漫行山薮变量定义：夏堇芳菲我们对于接下来的一些内容做出如下定义：
名称
定义
子串
不用多说了罢，在字符串中截取任意一段连续的内容，被称为子串下文用 $s[l\dots r]$ 表示字符串 $s$ 的从 $l$ 到 $r$ 的这部分子串。 下文所有关于字符串的计算都是以 1 为开始的下标*
子序列
不要求连续，但是在原字符串中内容顺序相同的字符串。
前缀子串
一个字符串的前缀组成的子串，表示为 $pre(s,i)=s[1\dots i]$ ，即 $s$ 字符串长度为 $i$ 的前缀
后缀子串
一个字符串的后缀组成的子串，表示为 $suf(s, i) = s[n-i+1\dots n]$ ，即 $s$ 字符串长度为 $i$ 的后缀
...
【拾题杂谈】LuoguP4159 [SCOI2009] 迷路
题面：[SCOI2009] 迷路大秦为你打开题目传送门
题目背景windy 在有向图中迷路了。
题目描述该有向图有 $n$ 个节点，节点从 $1$ 至 $n$ 编号，windy 从节点 $1$ 出发，他必须恰好在 $t$ 时刻到达节点 $n$。
现在给出该有向图，你能告诉 windy 总共有多少种不同的路径吗？
答案对 $2009$ 取模。
注意：windy 不能在某个节点逗留，且通过某有向边的时间严格为给定的时间。
输入格式第一行包含两个整数，分别代表 $n$ 和 $t$。
第 $2$ 到第 $(n + 1)$ 行，每行一个长度为 $n$ 的字符串，第 $(i + 1)$ 行的第 $j$ 个字符 $c_{i, j}$ 是一个数字字符，若为 $0$，则代表节点 $i$ 到节点 $j$ 无边，否则代表节点 $i$ 到节点 $j$ 的边的长度为 $c_{i, j}$。
输出格式输出一行一个整数代表答案对 $2009$ 取模的结果。
样例 #1样例输入 #11232 21100
样例输出 #111
样例 #2样例输入 #21234565 3012045071054780512024123 ...
【拾题杂谈】斐波那契类的矩阵快速幂
前置知识：矩阵快速幂出门右转 【算法介绍】矩阵乘法 | 祝馀宫 喵！
例一：斐波那契前缀和直接求斐波那契的例子已经在上面的文章中讲过了。这里直接开始讲斐波那契的前 n 项和怎么算。
求斐波那契的前 $n$ 项和对于 $m$ 取模的结果。
首先，不难给出递推式：
\begin{cases}
f_1 = 1\\
f_2 = 2\\
f_i = f_{i - 1} + f_{i - 2} \quad (i\ge 3)\\
s_1 = 1\\
s_i = s_{i-1} + f_i\qquad (i\ge 2)
\end{cases}这个是最最基础的递推式子，我们不难想到之前说的列方程法。我们就可以写出下面的方程组。
\begin{cases}
f_{i+1} &= &0\times f_i + 1\times f_{i+1} + 0\times s_i \\
f_{i+2} &= &1\times f_i + 1\times f_{i + 1} + 0\times s_i \\
s_{i+1} &= &0\times f_i + 1\times f_{i + 1} + 1\times ...
【算法介绍】矩阵乘法
算法简介：正绢六通首先，说到矩阵乘法。字面意思的来讲，就是矩阵与矩阵之间的乘法，他们之间是否满足正常数字之间的乘法规则，也就是交换律与结合律呢？这部分的内容都将在下面被解释。
算法演示：落染五色矩阵加法：缀锦四分这个比较简单。首先我们了解一下矩阵的定义，对于一个 $n$ 行 $m$ 列的矩阵，我们有如下的表示方式：
\left[\begin{matrix}
a_{1,1} & a_{1,2} & \cdots & a_{1,m} \\
a_{2,1} & a_{2,2} & \cdots & a_{2,m} \\
\vdots & \vdots & \ddots & \vdots \\
a_{n,1} & a_{n,2} & \cdots & a_{n,m}
\end{matrix}\right]这样的矩阵，就是我们接下来的基础。首先讲到乘法，肯定会有人想到加法。但是实际上……矩阵的加法和乘法几乎一点关系都没有……但是提到了我们也顺便讲一下。
矩阵的运算不同于数字，两个矩阵之间是否可以进行运算，对于矩阵的行和列有着严格的规定。比如说加法，所对应的两个矩阵行和列必须一模一样，因为矩阵加 ...
CSP-2024 游寄
上午：CSP-J 2024题目钛简单，没有打到 300 分的原因是 T3 没有算内存，直接把打表用的程序交了上去喜提 MLE -50
下午：CSP-S 2024题目还是好简单，没有打到 220 分的原因是：
T1 先把被吃的赋值成了 0，然后再让吃的把被吃的吃了…… -25 赛后扫了一眼代码就改了出来，最煞笔的是大样例全过了……
T2 把已经平方的速度再次平方…… -60，也是赛后看了一眼代码就发现了问题，最傻逼的是赛时我调这个问题调了一整个比赛…… 导致 T3 的暴力分都没打……
T3 ，T2 的策略规划不周，以及最傻逼的考场发挥，暴力分没打…… -20
这次 S组 比赛总计挂分 105 分，直接把大众分打成了煞笔分，我是纸张
