xuxuxuxuxu

题解

未归档(20)

/ 注册

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

题解 P2365 【任务安排】来自专栏

题解 P2365 【任务安排】算法:斜率优化动态规划由于题解里没有关于的斜率优化做法,我打算写一下这种特殊的斜率优化动态规划由于可以小于零,所以斜率不具有单调性,所以我们不能像原来一样维护下凸壳。我们不能只保留相邻两点斜率大于的部分,我们要把整个下凸壳都保留下来。这时队首也就不是最优解了，要二...

斜率优化

2020-01-17

0 682

题解 P3242 【[HNOI2015]接水果】来自专栏

题解 P3242 【[HNOI2015]接水果】题意：给你一棵个点的树和条路径，每条路径都有一个权值。有k组询问，每次询问给你一条路径和一个值。问你被这条路径包含的所有路径中的第K小的路径的值题解：我用的是树上莫队+平衡树(或分块)的方法平衡树的话是,分块的话就是稍微口胡一下树上莫队...

莫队分块

2020-01-17

0 689

题解 CF280D 【k-Maximum Subsequence Sum】来自专栏

题解 CF280D 【k-Maximum Subsequence Sum】题意：长度为的数列，支持两种操作： 1.修改某个位置的值 2.询问区间里选出至多个不相交的子段和的最大值。一共有个操作题解：线段树+堆当k=1是答案就是最大子段和当k=2是答案就有两种情况了： 1:最大子段和+不相...

线段树堆

2020-01-17

0 750

题解 P5471 【[NOI2019]弹跳】来自专栏

题解 P5471 【[NOI2019]弹跳】做法：思维+动态开点线段树+分块首先我们考虑最短路做法，发现边数是级别的。一维的情况我们能用线段树优化建边，但二维呢？反正我不会。我们想到Dijkstra的思想，每次找到dis最小的点，并用这个点去更新其他点。我们把矩形看成点，相当于每次找出dis...

线段树分块

2020-01-17

0 791

题解 P5216 【DLS 采花】来自专栏

题解 P5216 【DLS 采花】题解：考虑算每个数对答案的贡献。第i个数的有贡献，当且仅当第i个数的约数出现在它后面。假设第i个数有x个约数，那么有贡献的概率就是，有贡献的方案数就是总方案数概率。为什么是呢?有个数，要选出那个数放在最前面，当然是。代码： #include<bit...

数学

2020-01-17

0 624

题解 CF392D 【Three Arrays】来自专栏

题解 CF392D 【Three Arrays】题解首先肯定是要枚举一个的，我枚举的是（中的位置）。但我们不能从小到大枚举，要从大到小枚举。为什么呢？从大到小枚举的话，相当于是每次会多一些限制，这样比较好维护（如果是撤销限制，那不是很麻烦吗）。考虑会多什么限制呢？就是那个数原来是在中被消...

线段树

2020-01-17

0 705

题解 P5490 【【模板】扫描线】来自专栏

题解 P5490 【【模板】扫描线】题解看了怎么多题解，竟然没有一篇是下传标记的。我来写一份常规的下传标记的做法。我们需要维护区间最小值和最小值的个数对于一个询问，如果区间最小值>0，那么返回区间长长度，否则说明区间有些地方是0，那么答案就是区间长度-最小值个数（长度）然后就是普通...

扫描线

2020-01-17

0 638

题解 CF1288E 【Messenger Simulator】来自专栏

题解 CF1288E 【Messenger Simulator】简单思维+数据结构 1.首先发现x的最小值一定是x或1（x出现过就为1，否则为x） 2.然后我们发现x最大值要么是x，要么是出现x 之前的 x所在位置。这个我们直接用线段树维护每个值的位子即可。相当于对于一个数，他会把比他大的数都加1...

线段树

2020-01-17

0 557

拉格朗日插值 2 来自专栏

题目：给你一个次数不超过的函数在点上的取值，以及一个整数，就的值。答案对取模。题解：当然这题可以推广成很多题,例如:求中的连续的m项。我们首先要会普通的拉格朗日插值，还要会在取值连续时的做法，你还要会多项式乘法，由于本题对取模，所以用，元根是前置知识有点多啊啊啊由于是连续的点，即$...

2019-09-30

1 681

HNOI2015 接水果来自专栏

题意：给你一棵个点的树和条路径，每条路径都有一个权值。有k组询问，每次询问给你一条路径和一个值。问你被这条路径包含的所有路径中的第K小的路径的值题解：我用的是树上莫队+平衡树(或分块)的方法平衡树的话是,分块的话就是稍微口胡一下树上莫队：把一颗树的欧拉序搞出来，对于查询的两点（假设入...

2019-09-30

1 656