uniHk

分类

01Trie(5) AC自动机(7) CDQ分治(4) dsu on tree(1) K-D Tree(5) 主席树(5) 各类说明(1) 后缀数组(1) 后缀自动机(11) 回文自动机(6) 字符串（杂）(6) 康托展开(1) 数学(7) 整体二分(1) 斜率优化DP(3) 树链剖分(3) 概率DP(2) 算法(Lazy)(38) 线性基(5) 莫队(6) 计算几何(3)

/ 注册

全部文章（共121篇）

洛谷-P1169 棋盘制作(悬线法)

国际象棋是世界上最古老的博弈游戏之一，和中国的围棋、象棋以及日本的将棋同享盛名。据说国际象棋起源于易经的思想，棋盘是一个 8 × 8 ...

2020-01-02

0 430

HDU-6579 Operation(多校1B)(线性基)

终于又做了一道线性基！前缀线性基求区间最大异或值 Operation Time Limit: 8000/4000 MS (Java/Others) Memory Limit: 262144/262144 K (Java/Others) Total Submission(s): 1073 Ac...

2020-01-02

0 448

牛客多校1-H XOR(线性基)

题目链接题意：给定n个整数，求满足子集异或和为0的子集大小之和。题解：相当于求每个数出现在子集中的次数之和。先对n个数求线性基，设线性基大小为r，可以分别计算线性基内数的贡献和线性基外数的贡献线性基外：共n-r个数，枚举每个数x，将线性基外剩余的n-r-1个数任意排列，显然共...

2020-01-02

0 566

后缀自动机

最最详细的解析基础学习简洁明了的讲解小小总结总状态数不超过 2 n − ...

2020-01-02

0 358

Manacher算法

洛谷-P3805板子题关键点: 要有两个字符串，且处理后的字符串长度略大于原串2倍（肯定 < 2 ...

2020-01-02

0 436

AC自动机(Automaton)

小小总结千万记住insert完以后要build!!!老是忘掉QAQ insert函数就只是trie数的插入函数，可在结尾根据条件打一些标记 build函数(构建fail树)，主要利用BFS match函数中跑fail树其实就是反复跑后缀 fail树上倒过来建树以后可以进行很...

2020-01-02

0 441

洛谷-P4052+P3311 （AC自动机+数位DP）

洛谷-P4052 文本生成器题目地址虽然这题应该称为记忆化搜索，但是就想当做数位DP(QAQ) 一开始数组开小了，导致了WA，TLE，RE以及两个AC，深深的体会到了数组开小了什么错误都有，哈哈题意：给出一个字典，求长度为M且包含字典中至少一个单词的文本有多少个。思路：虽...

2020-01-02

0 711

洛谷 P-2292 L语言(AC自动机)

洛谷 P-2292 L语言一道比较简单的题，结果自己脑补了各种奇葩(错误)的判断，搞了一个多小时。。。题意：用已知字典去识别一个串，求最长可识别前缀（指能将此前缀分解为字典里面的单词）思路：建好AC自动机，记录好每个点所代表的字符串的长度拿要匹配的串从前往后匹配，若某个点...

2020-01-02

0 429

洛谷 P3041 视频游戏的连击Video Game Combos(AC自动机+拓扑排序+数位DP)

洛谷 P3041 视频游戏的连击Video Game Combos 难度一般，不过这个数位DP其实应该叫做记忆化搜索题意：玩游戏时可以通过按键组合打出combo技能；然后是已知N个combo的按键方式，然后求K次按键最多可以放出的combo技能（combo技能之间可以重叠）。思路： ...

2020-01-02

0 505

洛谷 P-4045 密码(AC自动机+状态压缩+数位DP+乱搞)

洛谷 P-4045 密码记AC的第一道黑题！题意：已知一段密码包含了一些字符串，然后求满足条件的密码有多少个，数量小于42时还得全部输出思路：一开始WA了两个点，不知道WA的什么，索性把读入的字符串去重了，实际上不需要建好AC自动机，同时记录当前点是哪个字符串的结尾，方便...

2020-01-02

0 583