__故人__

分类

CF(8) UOJ(1) 每日一题(3) 牛客小白月赛27(10) 算法模板(10) 随笔(20) 题解(117)

/ 注册

TA的专栏 52篇文章 0人订阅

30篇文章 846人学习

22篇文章 1707人学习

全部文章（共169篇）

第二类斯特林数·行来自专栏

推式子那么就转化为一个卷积形式。那么。用优化一下，就变为了。代码 #include<bits/stdc++.h> using namespace std; const int N = 8e5 + 100,mod = 167772161; int read() {in...

2020-10-24

4 572

You Are Given Some Strings...

分析我们如何处理。我们其实需要一点小技巧。我们发现，如果出现在中。那么一定有一个位置满足是的后缀。是的一个前缀。那么我们就可以枚举每一个位置，看能够作为前缀的串的个数和作为后缀串的个数。最后答案为。而求后缀，我们可以用，而求前缀有个小技巧，反转后再插入 ...

2020-10-23

3 599

CF163E e-Government

分析非常好的一道题，用到的也是在中非常有意思的，考察了多方面的知识。我把考察的知识写在了下面。一个串出现的次数等同于。就是在指针构成的反树链上的权值。基本的差分和数据结构。由于我们有了性质一，那么我们对于一个串的插入其实就是子树，删除反之。而对于子树操作可以用树链剖...

2020-10-22

5 592

[SDOI2014]数数

分析我们把数字考虑为字符串，那么现在我们就是要求出有多少方案满足没有出现在串中。关于这道题，因为我们要对子串考虑，比较自然考虑到树和。由于并不能很好处理失配的问题，那么考虑自动机。我们定义其中表示，该节点为一个的结尾，那么当我们转移到这个点的时候是非法的。但...

2020-10-22

9 758

[JSOI2007]文本生成器

分析仍然考虑。我们考虑这个串是否可行，主要看是否经过了一个的节点。那么我们定义表示考虑前长的串，现在到了节点，合法，不合法的个数分别有多少个。那么转移就暴力转移了，因为和都很小。那么总的复杂度为。代码 #include<bits/stdc++.h> u...

2020-10-22

6 612

Video Game

分析我们考虑上的，定义为，匹配了个字符，当前在节点的最大价值。那么转移为那么，现在的问题就在于如何求出数组。由于指针指向的是最长后缀，所以有的转移，这个可以在构造指针时就构造好。那么总的复杂度为。代码 #include<bits/stdc++....

2020-10-22

5 640

Fuzzy Search 来自专栏

分析我们发现难点其实是在如何处理距离为的节点也可以匹配的问题。我们可以把四个字符拆开，一样的我们定义一个新的距离函数就可以了。那么按照套路反转或者。我们就得到了一个卷积形式，那么最后的时间复杂度为。代码 #include<bits/stdc++.h> using...

2020-10-22

6 711

起床困难综合症来自专栏

分析由于混合位运算并不具备结合律，所以我们应该是不能强制将式子化简的。但是我们考虑位运算的本质。举一个例子运算，我们如果完整的写出表达式为我们可以发现，其实位运算的结果只取决于每一位，而并不是整个数字的值。那么我们可以按位考虑每一位，其实按位考虑也是解决关于位运算问题的一种常见方法。我们可...

2020-10-21

13 1084

[TJOI2013]单词

分析做法非常多，有的。好像复杂度都是的。这里提供一种广义后缀自动机的做法。这里采用了绝对没有空节点的在线做法，空间为线性。代码 #include<bits/stdc++.h> using namespace std; const int N = 1e6 + 10; char...

2020-10-21

4 564

Censoring

分析有一道加强版的题解这里。那道题要求有多个模板串。而这道题只有一个，那么我们可以通过来解决。考虑用栈储存路径，遇到完美匹配就返回步。时间复杂度为。代码 #include<bits/stdc++.h> using namespace std; const int N ...

2020-10-21

5 543