前缀函数 前缀函数的定义是：一个字符串最长的真前缀和真后缀。真前后缀的意思是这个前缀或者后缀不是这个字符串本身。 我们定义 $f(i)$ 的意思是这个字符串从第 $1$ 位到第 $i$ 位的字符串的前缀函数。 通过定义，我们可以暴力求出前缀函数 $f(i)$，复杂度 $O(n^2)$。 显然，这个复杂度太高了，于是我们可以尝试优化。 优化 第一个重…

今年五一的假期，我决定去崇礼。 第一天 5 月 2 日下午，我坐上了开往崇礼的火车。我买了一个一等座，只可惜靠的窗户是较小的。 陆陆续续，车上的人渐渐多了起来。周围，由安静，变为了喧嚣。我带上耳机，听着音乐，看着外面的风景匆匆划过。外面的风景，由平原，变为山峰。火车，穿过一个又一个隧道。 随着列车往北，室外气温逐渐变低，季节也明显地更偏向春天。我甚…

今天在写代码的时候，发现程序虽然过编译了，但是运行的时候会显示： terminate called after throwing an instance of 'std::out_of_range' what(): basic_string::substr: __pos (which is 1844674407370955161…

SPFA学习笔记 SPFA，他死了！——某次 noi T1 的出题人。 感觉和 DIJ 很像。 使用范围：负边权，判断负环，随机图 不适用于构造图。容易超时。 思路： 对于出发的点，向所有可以到达，并且没到达过的点的边都进行松弛（见 图论——dijkstra），将松弛的点入队，注意是队列不是优先队列。 继续重复上面的操作，直到队列为空。 #incl…

https://note.ztrztr.top/

难度：黄。 思路 我们假设 $x \bmod k == y \bmod k$，那么 $x = nk + a$，$y = mk + a$。我们可以计算出： $$ y - x = (mk + a) - (nk + a)\\ $$ $$ y - x = mk - nk\\ $$ $$ y - x = (m - n)k\\ $$ $$ K | y - x …