__故人__

题解

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

/ 注册

全部文章 / 题解（共116篇）

丝之割

分析真的是好题。我们考虑并不是所有线段都是有用的，如果有两条线段相交，那么其实我们只需要切断第一个就行了。所以我们可以形式化的表达当则时，这才是个合法图。而我们就是要求这个图转换为合法图之后的最小答案。我们考虑线性。令以结尾的最小代价。那么我们的转移为。我们发现其实后面...

2020-09-28

4 666

Physical Education Lessons

分析非常平凡的一道题，没太大意义。这里放松，敲了一个。有区间覆盖的，如果保证随机，其实还是不错的。代码 #include<bits/stdc++.h> using namespace std; struct Node{ int l,r; mutable int...

2020-09-28

6 445

任务安排

分析我们先把最初的方程写出来。令为结尾的最小代价。那么转移为。那么我们令是的决策点，那么用前缀和那么化简后，那么我们把这个化为了的形式。但是并不单调，所以我们考虑使用维护一个上凸壳。时间复杂度为。代码 #include<bits/stdc++...

2020-09-28

5 611

[SCOI2009]最长距离

分析因为都很小，所以暴力搜索就可以过。加个小减枝就可以了。那么我们枚举一个点作为起点，然后求到其它点最少通过多少个障碍就可以了。因为用了搜索，这里不分析时间复杂度。代码 #include<bits/stdc++.h> using namespace std; const int ...

2020-09-27

4 581

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