wxyww

分类

未归档(12) 精品(28) 题解(65)

/ 注册

全部文章（共11篇）

【每日一题】字符串

problem 给出一个长度为的字符串，求出他的一个最短子串，要求这个子串里面包含了全部个小写英文字母。 solution 统计出每个位置到后面每种字符的最近距离。其中的最大值就是以当前位置为起点的答案。用当前最靠前的字符所在的位置，然后从前往后扫，对于每个位置都统计一下答案即可。 code #i...

字符串暴力

2020-06-15

1 673

【题解】牛客练习赛64

A 怪盗-1412 problem 用个，个，个进行排列，求最多有多少个子序列。 solution 显然让所有的4和2分别相邻答案会更大。然后就是将1分成两份，分别放在4两边。如果前面的有个，那么答案就是，这是一个二次函数，当时取得最大值。 code /* * @Author: wxyww * @D...

字符串贪心动态规划

2020-05-24

2 724

【题解】 NC5157B 密码系统

solution 其实本题只要解决一个问题，剩下的就是模拟了。这个问题就是如何快速的比较两个字符串的字典序。这是一个非常经典的思路。我们对这两个字符串都哈希一遍，然后二分一下这两个字符串最长的公共前缀长度。然后比较最长公共前缀的下一位上的字符就行了。因为所有要比较的字符串都在同一个母串上。我们只要...

字符串

2020-04-19

4 531

KMP算法

KMP算法？？？　　kmp算法最简单的就是用来匹配子串，也就是从字符串s1中找到s2出现的次数与位置。同时，kmp的nxt数组还有很多高能的用处。 NXT数组：　　nxt数组是kmp算法中极其重要的部分，nxt[i]表示子串s中，上一次s[i]为后缀的位置。（看了后面的原理就很明白了） ...

字符串

2018-07-18

0 452

Manacher算法

Manacher算法？？？　　Mancher算法是用来找最大回文串的，因为功能太过单一，所以用处不是很多，但是在找回文串方面还是很强大的。大致原理：　　枚举回文串的中点，用p[i]表示以i为中心的最大回文串的长度。然后对p[i]进行扩展就可以了。　　　　最简单的扩展就是当s[i+p[...

字符串

2018-07-18

0 468

trie树

trie树？？？　　trie树是一种树形结构，可以用来找前缀固定的字符串。思想　　其实思想很简单，就是将每个字符串都挂到树上去，如果当前节点在之前已经有了就不用新建节点，可以继续前面的向下找。否则就新建一个节点，这样就节省了时间和空间。具体实现　　代码一看就懂了，不多bb 板子...

字符串

2018-08-05

0 459

[luogu3294][背单词]

题目链接题意读完题目就一个感受：这出题人tm不会说人话吗。真的感觉这个题理解题意比想出正解更难。其实题目的意思就是，给出一些单词，给这些单词编个号，然后要求其他的单词中是这个单词后缀的词都在这个词的前面。每个单词的贡献是当前单词的标号减去他的后缀中标号最大的那个的标号。希望我能表达明白吧...

贪心字符串

2018-12-17

0 565

KMP算法

KMP算法？？？　　kmp算法最简单的就是用来匹配子串，也就是从字符串s1中找到s2出现的次数与位置。同时，kmp的nxt数组还有很多高能的用处。 NXT数组：　　nxt数组是kmp算法中极其重要的部分，nxt[i]表示子串s中，上一次s[i]为后缀的位置。（看了后面的原理就很明白了） ...

字符串

2018-07-18

0 430

Manacher算法

Manacher算法？？？　　Mancher算法是用来找最大回文串的，因为功能太过单一，所以用处不是很多，但是在找回文串方面还是很强大的。大致原理：　　枚举回文串的中点，用p[i]表示以i为中心的最大回文串的长度。然后对p[i]进行扩展就可以了。　　　　最简单的扩展就是当s[i+p[...

字符串

2018-07-18

0 471

trie树

trie树？？？　　trie树是一种树形结构，可以用来找前缀固定的字符串。思想　　其实思想很简单，就是将每个字符串都挂到树上去，如果当前节点在之前已经有了就不用新建节点，可以继续前面的向下找。否则就新建一个节点，这样就节省了时间和空间。具体实现　　代码一看就懂了，不多bb 板子...

字符串

2018-08-05

0 471