shyyhs

分类

DP专题(52) 图论(4) 多校补题(2) 数据结构(27) 数论(4) 日记(14) 未归档(38) 题解(330)

/ 注册

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

415篇文章 3897人学习

AtCoder思维大提升

6篇文章 750人学习

kuangbin专题记录

0篇文章 0人学习

牛客每日一题推介(裙子计划~)

19篇文章 840人学习

全部文章（共21篇）

线段树

区间+等差数列区间求和 #include <bits/stdc++.h> using namespace std; typedef long long ll; const int N=2e5+5; const int mod=998244353; const int iv=(m...

线段树

2022-07-11

0 526

异度之刃

首先考虑贡献如何算? 比如1 2 3 4 5 2 3 4,很显然的一个算就是把2 3 4去掉,然后只求1 2 3 4 5的贡献. 考虑i以及相邻的一段的贡献,很显然i的贡献就是相邻一段的长度,比如说1 2 3,1的贡献是1,2的贡献是2,3的贡献是3. 知道贡献怎么算了,下面就分为几步解决这个问题....

线段树

2022-04-07

4 421

题解 | #割韭菜# 来自专栏

首先讲ai排序(从小到大)后,后缀一定是不减的. 证明:在没有割草之前这个一定是成立的,假设我有割草,割的高度是b,那么前面的一定小于b,后面=b,然后后面还是比前面长的更快. 由此就产生了一个线段树二分的做法. 上一次被割草的时间day+1,区间内草的增加速度之和spd,区间内左端点的速度nmsp...

线段树

2022-04-05

0 580

题解 | #方块 III# 来自专栏

类似湘潭邀请赛的那个dp...但是湘潭邀请赛的那个dp比这个难,假如赛前做了这个线段树估计那个dp可以秒...惨...code: #include <bits/stdc++.h> using namespace std; typedef long long ll; const int N...

线段树

2021-06-21

5 668

★★飞马祝福语★★ 来自专栏

为什么要写这个题的题解呢? 因为我觉得很可惜...尽管我做过类似的,类似这题 ,知道是线段树上分治跑dp,但是因为只做过一次,不敢写,因为怕bug然后调不出,事实上我又调了很久,确实菜,但是呢必须得说下次我绝对敢写. 这种题是基于线段树本身带有分治结构,对于每段来说就是先算段内贡献,然后算段外的贡献...

线段树 dp

2021-05-30

3 672

石子搬运来自专栏

思路我线段树属于那种看到题解一般能懂,自己有时候想不到的层次...这题应该就是一个线段树...单纯的已知次数下搬运石头肯定是平方答案最优.然后假如不含修改的话,就是一个超级简单的.假如含有修改呢...我们不妨把它放到线段树上进行.令表示为到了这个石头堆(因为线段树是一群一群石头进行维护的嘛~)选了...

线段树 dp

2021-03-11

0 963

[JSOI2009]等差数列来自专栏

思路对于这题,首先要知道维护一些什么东西.我们都知道区间加个等差数列,假如维护单点求和的话,直接维护公差即可.因为区间加一个等差数列只需要两次单点修改和一次区间修改即可.对于这题,我们很容易想到维护公差.但是对于查询操作维护公差是远远不够的.每次是询问你区间中有多少个等差数列.对于这个查询啊,我们...

线段树 dp

2021-03-08

4 1127

区区区间来自专栏

思路只要记录线段树所有区间的一个左端点的值这个题就可以做完..我们可以假设这个左端点是,对于每次修改操作,我们只要知道左端点的值,我们这个区间修改的值就会变得已知,就可以更新,子区间的值也可以更新.总之还是线段树不熟练~. 代码 #include <bits/stdc++.h> usi...

线段树

2021-03-01

0 0

P1471 方差来自专栏

呜呜呜,挺有教训的一题,下次一定仔细看括号!!! #include <bits/stdc++.h> using namespace std; const int N=1e5+500; struct Tree{ int l,r,len; double sum; do...

线段树

2020-12-25

3 579

P1276 校门外的树(增强版) 来自专栏

感觉这题还可以,不像以前的模板题一样,貌似教会我一些其他的东西...2333贴个代码吧~ #include <bits/stdc++.h> using namespace std; const int N=1e5+50; int ans1=0,ans2=0; struct Tree{ ...

线段树

2020-12-23

3 739