Qianmo's Blog

KMP 题目链接：Acwing 831. KMP字符串 KMP的过程一般比较抽象，较难理解。 题目背景： 123给定一个字符串S，以及一个模式串P，所有字符串中只包含大小写英文字母以及阿拉伯数字。模式串P在字符串S中多次作为子串出现。求出模式串P在字符串S中所有出现位置的起始下标。 我们先考虑暴力算法怎么做，然后怎么去优化： 假如s是比较长的串，p是比较短的串，我们可以遍历s的同时遍历p，即写一个二重循环。这么做的目的是为了按位匹配。在这个过程中设置一个变量flag来记录是否成功匹配。 假如出现不匹配的情况，即s[i+j-1]!=p[i]，那么我们直接break，同时把flag变为false 这个时间复杂度是感人的，为O(n∗m)O(n*m...

...

Nim游戏 Nim游戏属于公平组合游戏ICG，即满足以下特点： 由两名玩家交替行动 在游戏进程的任意时刻，可以执行的合法行动与轮到哪名玩家无关 不能行动的玩家判负 先看一下模板题题目： 甲，乙两个人玩 nim 取石子游戏。 nim 游戏的规则是这样的：地上有 nnn 堆石子（每堆石子数量小于 10410^4104），每人每次可从任意一堆石子里取出任意多枚石子扔掉，可以取完，不能不取。每次只能从一堆里取。最后没石子可取的人就输了。假如甲是先手，且告诉你这 nnn 堆石子的数量，他想知道是否存在先手必胜的策略。 举个例子，对于两堆石子2 3，先手从第二堆拿了一个，变成2 2，那么接下来不管后手从哪一堆石子拿几个，先手只需要在另一堆石子里拿相同个数的石子就能保证最后后手没有石子取。比如后手从第一堆里拿一个，变成1 2，先手只需要在第二堆里拿一个，变成1 1，后手再从第一堆里拿一个，变成0 1，先手拿掉，变成0 0，先手获胜 我们先引出两个概念： 先手必败状态：在Nim游戏中指先手遇到0 0，此时先手必败 先手必胜状态：先手如果通过某些操作能够走到必败状态，即0...

题解：P11276 第一首歌 题意 这道题需要我们找到一个最短的字符串，使得给定的字符串既是它的前缀也是它的后缀。 KMP算法 用 pi[i] 表示字符串 s[0:i] 的最长的即是前缀又是后缀的子串的长度，那么 pi[n-1] 就是整个字符串最长的即是前缀又是后缀的字串的长度，也就是我们的答案的长度。 假设 k = pi[n-1] ，意味着整个字符串最长的即是前缀又是后缀的字串的长度为 k ，则 s[0:k] 既是s的前缀也是 s 的后缀，那么我们只需要把 s[0:k] 加上 s.substr(k) 就能得到最小的满足条件的答案 计算pi数组 其中 pi 数组是整个题目的关键所在，我们通过 while 循环不断回到之前的前缀位置，直到匹配或找到最大前缀后缀，具体见代码。 代码 1234567891011121314151617181920#include <bits/stdc++.h>using namespace std;const int N = 1e6+10;int pi[N];int main(){ string s; cin...

本题采用双向 BFS 来解决。 首先分析一下时间复杂度：变换规则数 R≤6R \leq 6R≤6 ，字符串长度 L≤20L \leq 20L≤20，操作数在 10 次以内，用朴素 BFS 的时间复杂度为 O((L⋅R)10)O((L\cdot R)^{10})O((L⋅R)10) ，完全爆炸；采用双向 BFS 的时间复杂度为 O((L⋅R)5)O((L\cdot R)^{5})O((L⋅R)5) ，相对于朴素做法降低了很多的时间复杂度。 但对于本题，可能出现以下情况：每次变换可能在字符串的多个位置替换、变换规则可能形成“无限繁殖”的状态等，导致搜索空间飞速增长。双向 BFS 并不能保证通过本题的数据，但也是一种优化搜索的方法。 双向 BFS 的具体步骤： 开两个队列 qa,qbqa,qbqa,qb，一开始分别把起点和终点丢入队列中。 每次选择较小的队列进行扩展，将队头其可能经过变换规则得到的字符串丢入队列中（注意假如扩展 qbqbqb...

本题要求求一个地图中的岛屿数量，但是不包括子岛屿（在其它岛屿围成的环之间）。 对于求岛屿，可以使用搜索中的 Flood Fill 算法来实现，对每个为 111 的陆地进行 BFS，标记与它相邻的所有陆地。为了实现环内部的岛屿不被统计，我们可以先 BFS 海域，在 BFS 海域的过程中如果遍历到为 111 的陆地，就来一遍 Flood Fill 将其相邻的陆地全部打上标记，如果遍历到为 000 的海水就不入队（只有 000 会入队）。 需要注意的是，遍历海域是八个方向拓展的，而遍历陆地是四个方向扩展的。同时我们能保证海水拓展八个方向得到的岛屿都不在环内，这是因为陆地不入队，岛屿在环内的话是进不去的。可以借助下面样例来理解： 123450111111001101011000111111 我们不可能遍历到 (3,2)(3,2)(3,2) 位置的 000 的，因为 000 不入队，遍历海域是进不到环内的，自然就遍历不到环内的 111 了。所以我们对于每次 Flood Fill，直接将答案加 111...