__故人__

分类

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

/ 注册

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

30篇文章 846人学习

22篇文章 1707人学习

全部文章（共169篇）

网络优化

分析我们看出，这是一个匹配问题。左边的点只能匹配右边的节点。而一个节点可以匹配的数量为。我们可以考虑用网络流来解决这个问题。向左边节点连接一条容量为边。右边节点向连接一条容量为的边。如果右侧节点满足，那么左侧节点向连一条容量为的边。最后 ...

2020-10-01

5 929

Minimizing maximizer

分析对于这类问题，我们先观察是否有什么性质。由于我们要求的所有数最后都可以到达。而在行动时候会经过的所有节点。那么我们的问题就随之转换为，到最少要经过几个区间。那么我们可以先考虑。令为考虑到前个机器，当前点为的最小步数。那么我们就有两个转移和。那么这...

2020-09-29

4 713

[SCOI2016]背单词

分析非常好的思维题。我们发现第一条件完全没有用，其实就是要求我们，使每个串的后缀必须先于该串出现。那么我们可以根据后缀来构成一个拓扑图。那么现在问题就是求，求出一个拓扑图的遍历顺序，要求这个最小。我们发现最小代价的遍历顺序，那么一个点的贡献就是。那么我们优先的来遍历一定是最优的。 ...

2020-09-29

4 574

病毒

分析要求有一条可以无限长的串，满足所有字串没有出现过。那么我们可以考虑自动机。我们用表示，那个无限长的串不可以匹配的节点。那么我们就会有这个转移，因为是我的一个后缀，那么后缀都不能到，更别说自己了。那么我们直接在自动机上就好了。代码 #include<bits/st...

2020-09-29

3 534

Stressful Training

分析比较简单的贪心题。我们考虑到二分一个答案。那么存在也是成立的。所以这个是具有单调性的。那么为了让所有的点都是合法的。那么肯定要拿出最近一个将要不合法的节点让他的电量。那么当第次充电时发现最近的节点没电的时间在之前，则是个非法答案。那么我们算法就是如果快速找到第一个将要不合法...

2020-09-29

3 617

Mike and Friends

分析可以说是关于自动机运用的较难题了。但是能用坚决不用自动机。我们考虑一个串作为字串出现在其它字符串中，那么就是看这个串的结束节点的集合有多少这个区间的串。所以现在的思路就是，对所有串建一个广义后缀自动机，这里不能建那种之后就不管的伪自动机。要使用树建法，或者在线建法。然后...

2020-09-28

6 638

丝之割

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

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