xuxuxuxuxu

分类

未归档(20) 题解(24)

/ 注册

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

39篇文章 2130人学习

全部文章（共43篇）

题解 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 627

题解 CF392D 【Three Arrays】来自专栏

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

线段树

2020-01-17

0 711

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

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

扫描线

2020-01-17

0 637

题解 CF1288E 【Messenger Simulator】来自专栏

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

线段树

2020-01-17

0 557

NOIP初赛来自专栏

1.计算机基础错题： 1.在微机中，通用寄存器的位数是（计算机字长）。 2.WINDOWS 9X 是一种（多任务图形方式）操作系统． 3.第一个给计算机写程序的人是（Ada Lovelace）。 4.为解决web应用中的不兼容问题，保障信息的顺利流通，（万维网联盟（W3C））制定了一...

NOIP

2019-10-15

6 1989

拉格朗日插值 2 来自专栏

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

2019-09-30

1 681

HNOI2015 接水果来自专栏

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

2019-09-30

1 656

一只log的神仙做法来自专栏

经过同学的指点，发现F题有一只log的做法——点分树。首先两个点在点分树上的lca一定在原树上这两个点的路径上。所以我们把x-y的路径分成x-点分树上的lca 和点分树上的lca-y的两条路径。用树链剖分的方法维护一下点分树上的点到其他点的信息即可。

2019-09-14

2 712