ZeRoLJ42

题解

/ 注册

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

【每日一题】【7月21日】区间权值

题意：给定两个长度为的数组和，求。结果对取模。题解：喜闻乐见的简单推式子题。先令，即为的前缀和；，即为的前缀和。那么：分开算一下左边：第一步和式变换，我是从具体表示意义直接写出右边的式子的。两个和式表示的的所有子区间，原来是先枚举，再枚举。变...

每日一题

2020-07-21

10 748

【每日一题】【6月8日】[SCOI2005]最大子矩阵

题意：给定一个的矩阵，从中选出个互不重叠的子矩阵，使得总分值最大。其中。题解：注意到。先考虑的情况，是一个比较经典的最大子段和问题，可以用求解，复杂度为。具体做法这里就不说了。再考虑的情况，由的求解做法接着往下考虑。子矩阵可以是第一列的连续行，或者第二列...

每日一题

2020-06-05

5 870

【每日一题】【6月2日】旅游

题意：给定一棵个节点的树，初始选择节点，之后每次选择可以取一个之前未选择的且不与之前选择的节点相邻的节点，问最多可以取多少个节点？题解：树形。初始节点，当作树的根。那么之后每次节点选择，都是在已选择节点的子节点树中进行选择。我们可以尝试把这个过程倒过来，由子节点对应的子树选择的结果...

每日一题

2020-06-01

0 799

【每日一题】【6月1日】Contest

题意：支队伍一共参加了三场比赛。一支队伍认为自己比另一支队伍强当且仅当在至少一场比赛中比的排名高。求有多少组，使得自己觉得比强，自己也觉得比强。算一组。解法：题目应该是有个没有显式声明的条件：一场比赛种不存在两支队伍排名相同。如果加上这个条件，也能做，处理一下...

每日一题

2020-05-29

0 927

【每日一题】【5月29日】管道取珠

题意：有上下两个管道，上管道有个球，下管道有个球，每次可以从上管道或者下管道末尾取出一个球。对每种最终取出的小球序列统计方案数。记不同的序列数为，第种序列的方案数为。显然有。需要你来计算，结果对取模。数据范围: 解法：关键点：需要将求和式中的平方转化出来：视为两个相...

每日一题

2020-05-28

1 927

【每日一题】【5月28日】Protecting the Flowers

题意：有头奶牛在践踏花田，第头牛每分钟会毁坏朵花，把第头牛关进栅栏里需要分钟。关进栅栏的过程中，不会毁坏花朵。同一时间只能处理一头牛，问怎样安排可以使得被毁坏的花朵数目最少。题解：贪心。比较典型的贪心题目。因为同一时间只能处理同一头牛，所以我们只需要确定顺序即可。确定顺序再...

每日一题

2020-05-27

0 615

【每日一题】【5月27日】货币系统

题意：有种面值的货币，第种货币面值为。这组货币组成的货币系统定义为。求与等价的货币系统中，最小的。两个货币系统等价定义为：任意面额，要么均不能被两个货币系统表示出来，要么均能被表示出来。题解：考虑中会存在哪些数：考虑某个面额：若不能被表示出来，那么中肯...

每日一题

2020-05-27

0 845

【每日一题】【5月26日】[JSOI2007]建筑抢修

题意：个建筑，每个建筑有完成的持续时间，以及截止时间。同一时间只能抢修一个建筑，每个建筑需要在截止时间前完工，否则就报废。问最多能有多少建筑抢修成功。题解：贪心。先按截止时间排序。然后顺序抢修，能抢修成功的则抢修。同时维护一个优先队列/堆，堆里存放抢修成功的建筑的持续时间。当不能抢修成功...

每日一题

2020-05-25

0 759

【每日一题】【5月22日】[CQOI2009]中位数图

题意：给出的一个排列，统计该排列有多少个长度为奇数的连续子序列的中位数是。题解：先考虑一段区间中位数为有什么性质：这一段区间内大于的数和小于的数一样多，并且包含。然后做一个简单的转化，大于的数记为，小于的数即为。那么中位数为的区间就有：区间包含所在...

每日一题

2020-05-21

0 621

【每日一题】【5月21日】图的遍历

题意：给定无权双向图，顶点数为，边数为。从顶点开始遍历，每次“走两步”。问最少需要添加多少条边，可以走遍整个图。解法：先考虑连通块内的情况：对顶点进行黑白染色，那么和顶点颜色相同的点，都可以直接通过原图中的边走到。然后再考虑从某个点如何“走两步”走到另一个颜色不同的点：若某个顶...

每日一题

2020-05-20

0 613