__故人__

题解

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

/ 注册

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

2020牛客国庆集训派对day1 D 来自专栏

分析要求我们在一条直线上确定一个点。要求它覆盖的点最多。我们可以转换一下，对于每个点我们可以覆盖到它的地方有哪些。如此我们发现这些地方，一定在直线上构成一个线段，或者没有交点。那么我们就可以求出这个范围，然后通过差分就可以求出最多被覆盖的区间。这个我们可以通过勾股定理来求。但是我们最后得到的是一个...

2020-10-05

6 795

2020牛客国庆集训派对day1 C 来自专栏

分析给你一棵树，求至少要几次操作，变化为一条链。我们知道无论变化多少次总度数一定不变。而一条链的度数分布为根据鸽巢原理，只要对于的节点操作次就可以了。总的复杂度为。代码 #include<bits/stdc++.h> const int N = 3e5 + 100...

2020-10-03

6 574

2020牛客国庆集训派对day1 B 来自专栏

分析我们换一个题面，其实是要我们求。那么我们发现这个的出现太突兀了，考虑用枚举这个。那么我们枚举之后，就暴力枚举这个区间就可以了。为什么呢？我们可以证明只会有种取值。那么我们完全可以再枚举一个，又因为的大小是具有单调性的，所以二分枚举边界就可以了。关键是的枚举，...

2020-10-03

7 0

2020牛客国庆集训派对day1 A 来自专栏

分析我们需要加几个字符在末尾将其变为回文串。那么我们可以很容易考虑到，回文中心一定在这个字符串上。那么当一个回文中心确定时，这个串其实也就确定了。那么添加的长度为。所以我们就应该寻找最大的可行的。那么当一个字符可以为回文中心时当且仅当，回文中心加上回文半径覆盖了第个字符的。那么求出每个...

2020-10-03

5 787

网络优化

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

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