前缀函数 & KMP 学习笔记
前缀函数前缀函数的定义是：一个字符串最长的真前缀和真后缀。真前后缀的意思是这个前缀或者后缀不是这个字符串本身。我们定义 $f(i)$ 的意思是这个字符串从第 $1$ 位到第 $i$ 位的字符串的前缀函数。通过定义，我们可以暴力求…
CATEGORY
信竞
这个分类下的文章与记录。56 篇内容
↗
模拟测验（零）水灾 做题笔记
题面思路这道题第一眼应该可以看出是一道搜索的题目。我们先用 bfs 搜索一遍，用来计算出洪水到达每一个位置的最少时间。这里需要注意的一点是，有可能有多个洪水的初始地点，所以每一个洪水到达一个地点的时间有可能不一样。所以在更新洪水…
模拟测验（一）双色球 做题笔记
题面 思路50 pts暴力。我们发现每次操作等于将前面的红的变成蓝的，将第一个蓝的变成红的。要养成写暴力的好习惯。#include <bits/stdc++.h> using namespace std; /* …
SPFA 学习笔记
SPFA学习笔记SPFA，他死了！——某次 noi T1 的出题人。感觉和 DIJ 很像。使用范围：负边权，判断负环，随机图不适用于构造图。容易超时。思路：对于出发的点，向所有可以到达，并且没到达过的点的边都进行松弛（见 图论—…
P1154 奶牛分厩 题解
难度：黄。思路我们假设 $x \bmod k == y \bmod k$，那么 $x = nk + a$，$y = mk + a$。我们可以计算出： $$y - x = (mk + a) - (nk + a)\$$ $$y - …