分数：J95，S70.5 Day -1 看了一会之前的题目，然后逛了一逛洛谷。 冲了一个澡然后大约 9:30 就睡觉了。 Day 1 上午，CSP-J 初赛 八点多起来，由于考场是中科院小学玉泉分校（后文简称“玉泉小学”）里学校不算很远，大约骑车十几分钟就到了，所以没有那么急。 8：50 到了校门口，等了几个同学一起进校。玉泉小学真的很像首师附。 …

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

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

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

题目链接：洛谷 P1048 题目大意 给定一个最大重量为 $V$ 的背包，和 $n$ 个物品。每个物品有一个重量和价值。现在问在背包可以装下的范围内，最大的价值是多少。 朴素 DP 我们定义 dp[i][j] 为到第 $i$ 个物品，背包的重量为 $j$ 的最大价值。 我们可以得出状态转移方程： $$ \text{dp[i][j] = max(dp…