__故人__

分类

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

/ 注册

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

30篇文章 846人学习

22篇文章 1707人学习

全部文章（共169篇）

[CH弱省胡策R2]TATT

分析可以考虑到为结尾的最长的序列。那么。所以其实这个是个四维偏序。所以我们考虑来做。时间复杂度为。但是有几个非常重要的减枝条件。可以参照代码。代码 #include<bits/stdc++.h> using namespace std; int read() { ...

2020-09-27

3 513

#207. 共价大爷游长沙

分析因为我们要维护，删边，加边。所以我们考虑使用。那么现在就是求问一条边是否被所有路径经过。所以我们考虑用子集异或。那么我们之后，节点的子树中的异或和必须等于。所以我们还有维护虚子树。如果能分析到异或。这道题就不难了。代码 #include<bits/stdc++.h>...

2020-09-27

4 642

[国家集训队]JZPFAR

分析一次过，非常爽。考虑上的最近邻查询。虽然有人已经证明上的最近邻查询时间复杂度会被构造数据卡到。但是多数情况下是非常快的。那么这道题，只是把最近邻换成第大距离。我们只需要用个堆来动态维护一下就好了。注意因为有编号的问题，所以要注意查询的小细节。代码 #include<bi...

2020-09-26

6 521

Censoring

分析我们对于字串匹配，考虑和自动机。但是对于删除操作不太好维护。所以我们考虑原串在自动机上匹配。用栈保存路径，如果一旦发现该节点有一个标记，那么我们就往后退步，之后继续匹配，直到原串匹配完毕，总的时间复杂度为。代码 #include<bits/stdc++.h&g...

2020-09-26

5 566

[HNOI2006]最短母串

分析发现这个是与字串有关系的，就考虑后缀自动机和自动机。我们发现对于这个问题后缀自动机使用会非常的不自然，因为我们并没有一个原串。我们就考虑如何用自动机解决。我们可以把所有的目标串插入自动机。因为所以结尾并没有太多状态，可以考虑状压。令为考虑到节点，现在状态为的最小串。...

2020-09-26

4 616

Mokia

分析开始学了，先来做一个模板题。个人感觉其实就是一个高维的二叉搜索树。其实可以像替罪羊树一样重构来保证平衡，为了偷懒就没写了。代码 #include<bits/stdc++.h> using namespace std; // #define int long long co...

2020-09-25

2 488

List of Intergers 来自专栏

分析求第大的大于等于且与互质的数，那么我们先考虑如果我们枚举第大是谁，其实并不好做。这样时间复杂度的的下限至少为。那么我们考虑二分一个值，与互质的数的总个数求出来，这样二分的值就具有单调性了，也可以很好的处理大于等于这个条件，做一次差分就好了。那么现在算法的主要问...

2020-09-25

3 620

CF1037H Security

写在前面的好久没有写这样令人心旷神怡的题目了。分析在区间中选取一个字典序严格大于的且字典序尽量小的字串。我们先考虑如何让的字典序严格大于，那么必然存在一个使得并且。既然是要让字典序最小，所以考虑从大到小枚举，找到第一个可行的就退出，就可以保证字典序的最小...

2020-09-25

3 665

Escape Through Leaf

分析我们可以先写出暴力转移方程表示节点到子树中某个叶子节点的最小代价。那么转移方程为可以看出这个是类似的直线方程的，但是斜率并不单调，所以考虑李超线段树，但是从一个子树转移到另一个子树不能暴力转移，否则时间复杂度为。所以我们考虑线段树合并，处理完子树后进行线段树合并。这样时间复...

2020-09-24

3 585

快速傅立叶之二来自专栏

分析联系一下基础卷积。，虽然这个不是最基本的卷积形式，但是我们可以通过，令，那么原式变为而是一个常数，所以我们成功的构造了卷积形式。做一次就好了。代码 #include<bits/stdc++.h> using namespace std; int read() ...

2020-09-24

3 602