爱心代码编程python，NOI，2011，阿狸的打字机(AC自动机+主席树)

阿狸的打字机是NOI 2011的一道题目，需要运用AC自动机和主席树进行解决。这道题目难度较大，需要运用一些较高级的数据结构和算法。

首先，需要了解AC自动机和主席树的概念和使用方法。AC自动机是一种多模式字符串匹配算法，可以在一个文本串中同时查找多个模式串。而主席树则是一种基于整体二分的数据结构，可以在多个版本的前缀和中快速查找区间和。

接下来，以解决阿狸的打字机为例，详细介绍如何使用AC自动机和主席树解决该问题。

问题描述：有一个打字机，每次可以在末尾输入一个字符或者删除末尾的一个字符，现在有m个字符串需要打印，每个字符串需要花费c[i]的代价，同时，每分钟打印的字符串长度不能超过n，要求最小化打印所有字符串的代价。

解决思路：我们可以使用AC自动机来构建一个字典树，其中每个节点代表一个前缀子串，最后一个节点代表一个完整的字符串。同时，我们用一个数组v来记录每个节点所代表的字符串在原始字符串中出现的位置。另外，我们用dp[i][j]来表示前i个字符串的长度为j的最小代价。当我们需要添加一个字符时，我们就要向AC自动机中添加新的节点，并且更新数组v。当我们需要删除一个字符时，我们就要回退到上一个节点，并且更新数组v。而我们需要满足的条件是每分钟打印的字符串长度不能超过n，因此我们需要用主席树来进行维护。

在构建AC自动机的过程中，我们可以使用广度优先搜索的方法构建整个字典树。同时，我们需要用单调队列来进行维护，保证每个节点都会被访问且只会被访问一次。为了进行动态规划，我们需要先将所有字符串按照长度从小到大排序，然后从前往后枚举每个字符串，并且按照长度从小到大进行转移。转移时，我们需要分别考虑添加和删除字符的情况，然后取最小值更新dp数组即可。最后，我们可以在dp[m][j]中找到满足条件的最小代价。同时，我们需要用主席树来维护每个前缀的长度，并且在进行添加和删除字符时进行更新。最后，我们可以在主席树中进行二分查找，来找到长度不超过n的最大前缀长度。

综上所述，AC自动机和主席树的使用可以解决NOI 2011阿狸的打字机问题。通过仔细分析和实践，我们可以掌握这些高级的数据结构和算法，为解决更加复杂的问题打下坚实的基础。