P2607 [ZJOI2008] 骑士 难度：紫（省选/NOI−）。 知识点：图论，树形 DP，DFS。 知识点难度（知识点模板题）：绿。 代码长度：中偏短（$52$ 行） 代码难度：较低。 思路 这道题是采用树形 DP 的《没有上司的舞会》的模板的，状态定义为： $dp[i][0]$ 是以 $i$ 为根的子树不选择这个节点的最大答案。 同理，$d…

P10801 题目大意 给一个字符串，求通过改变最多 $k$ 个字符后最小化这个字符串的严格循环节的长度。 思路 从题目，我们能初步分析出一下几点： 答案肯定是字符串长度的因子； 由于随着答案的减小，需要操作的次数会增加，那么我们就能想到二分。 我们可以先统计字符串长度的每个因子，然后存到数组里面。 然后二分这个数组，找到最小符合条件的答案。 二分…

Trie 树 Trie 树是一种可以快速查找一个字符串是不是在目前集合中的一个数据结构。 Trie 树的中文名是字典树，顾名思义，这个数据结构就是一个长得像字典的树。 思路 ​​ 上面这个图就是一个 Trie 树，这种树是一个有根树。这种数据结构中，我们不再把每个字符串完全分开存储，而是把相同的合并了。 插入 我们从根节点开始，检查根节点的边有没有…

题目大意 有一个图，依次删去一些点后有多少个连通块。 思路 一道并查集 + 离线 的题目。 这道题第一眼肯定是想如何维护可以删除节点的并查集，但是这样不太可做。（或许是我太菜了。）但是我们发现他只有一个删除的操作，没有增加的操作，那么就可以想到离线计算。 离线计算，也就是把原本是读入后立马运算的操作都存起来，再算。 这样的好处就是我们可以按操作倒着…

CSP 初赛笔记，持续更新中。 出栈序列 出栈序列满足 FILO 的规则，也就是先进后出。 如果入栈的顺序是降序排列，那么可以快速判断的依据就是任意数A的后面比A大的数都是按照升序排列的 如果入栈的顺序是升序排列，那么可以快速判断的依据就是任意数A的后面比A小的数都是按照降序排列的 哈夫曼编码 哈夫曼编码详解——图解真能看了秒懂_已知字符集abcd…

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

题面 思路 这道题第一眼应该可以看出是一道搜索的题目。 我们先用 bfs 搜索一遍，用来计算出洪水到达每一个位置的最少时间。 这里需要注意的一点是，有可能有多个洪水的初始地点，所以每一个洪水到达一个地点的时间有可能不一样。所以在更新洪水达到时间的时候，我们需要注意不要直接赋值，要取最小值。 第二遍 bfs 是计算能不能达到别墅和最短时间，这个直接 …

题面 思路 50 pts 暴力。我们发现每次操作等于将前面的红的变成蓝的，将第一个蓝的变成红的。 要养成写暴力的好习惯。 #include <bits/stdc++.h> using namespace std; /* */ int n; string s; int cnt = 0; bool check() { for (int i …

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

难度：黄。 思路 我们假设 $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 …