子谦。

分类

入门教程(10) 未归档(52)

/ 注册

全部文章（共61篇）

游记集合

2018年 11 月 9 日至11日 NOIP2018游记 2019年 4 月 5 日至7日 SDOI2019退役记

2019-03-01

0 433

P2824 [HEOI2016/TJOI2016]排序

题面这是一道非常巧妙的线段树的题我们会发现维护\(1 \sim n\)的序列非常困难，但如果我们维护\(01\)序列的的顺序，就非常容易了但是我们怎么能把这道题变成维护\(01\)序列的顺序呢？这道题只会对一个位置的数进行询问那么我们是不是可以二分枚举这个数是几？这样的话，大于等...

2019-02-25

0 377

P3224 [HNOI2012]永无乡

题面一开始，每个集合只有一个岛，对于一个集合，我们建一棵线段树，当连边的时候，我们先判断一下是不是已经在一个集合，然后合并线段树，查询的时候查询所在集合的线段树即可，若\(k\)大于集合元素数，输出\(-1\) 那么怎么维护集合呢？并查集啊做完了下面是代码 #include<a...

2019-02-25

0 470

P3605 [USACO17JAN]Promotion Counting晋升者计数

题面一道线段树合并的入门题直接建一堆权值线段树然后合并就可以了下面是代码 #include<algorithm> #include<iostream> #include<cstring> #include<cstdio> #include...

2019-02-25

0 348

P4314 CPU监控

题面这是一道堪称“线段树3”的线段树好题,对于\(lazy\)标记的操作可以说是非常巧妙我们用结构体来记录\(lazy\)标记，结构体中定义\(a,b\)两个元素，\(a\)表示加上\(a\)，\(b\)表示赋值为\(b\) 那么对于\(\{a_1,b_1\},\{a_2,b_2\}\)两...

2019-02-24

0 523

P2939 [USACO09FEB]改造路Revamping Trails

题面这是一道分层图的模板题（大家都这么说），这使得我这个从来没有学过分层图的蒟蒻不知如何是好网上的讲解我也都看不懂，或者说好像没找到讲解。。在跟DDOSvoid大佬进行一番不知所云的交流过后，我忽然明白了这个东西所谓分层图，就像它的名字一样，把图分成一层一层的，上一层可以到达下一...

2019-02-21

0 461

P4254 [JSOI2008]Blue Mary开公司

题面这道题的意思就是给出若干个一次函数，当\(x=x_0\)时，最大的\(y\)为多少这种题可以用李超线段树来处理什么是李超线段树呢？李超线段树存储的是在区间上方暴露最多的直线标号，为了便于描述，我们称它为优势直线例如下图在区间[0,5]，AB就是暴露最多的线段可以证...

2019-02-21

0 382

P1772 [ZJOI2006]物流运输

题面很明显，这道题要求最短路，如果换路线不要钱的话，我们直接对于每天分别求最短路即可，但可惜的是要钱，那就dp啊设\(f[i]\)为第一天到第\(i\)天最小费用，那么\(f[i]=min(f[j-1]+(i-j+1)*l+K)(1<=j<=i)\)，\(l\)表示第\(i\)天...

2019-02-20

0 415

P2261 [CQOI2007]余数求和

我是题面题意还是很清晰，很容易理解 1e9范围明显不能暴力，除非你能把常数优化到\(\frac1 {10}\)，但我实在想象不到用了这么多取模怎么把常数优化下去我们可以把\(k\%i\)变成\(k-k/i*i\)(整除) 那么总的和也就从\(\sum_{i=1}^{n}k\%i\)变成了...

2019-01-20

0 331

CF992C Nastya and a Wardrobe

我是题面题意很清晰，这种题，我们当然还是有两种方法来做啦方法一：找规律读完题我们来看样例，通过样例一已我们大概可以看出，答案或许是\(n*2^{k+1}\) 肯定不能这么简单对吧，那就来看样例二，难道答案是\(n*2^{k+1}-k\)或者是\(n*2^{k+1}-2^{k-1}\)也...

2019-01-20

0 379