子谦。

未归档

入门教程(10)

/ 注册

全部文章 / 未归档（共52篇）

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

P2219 [HAOI2007]修筑绿化带

我是题面这道题跟理想的正方形很像，不大明白蛤OI是怎么想的，一年出两道这么相近的题这道题有两个矩形，所以就有了两种做法（说是两种做法，其实只是维护的矩形不同）一种是维护大矩形，一种是维护小矩形，我这里采取了维护小矩形的方法先求出以\((i,j)\)为左上角的大矩形和小矩形的权值和为多...

2019-01-17

0 378

P2216 [HAOI2007]理想的正方形

我是题面题意挺清晰的，做法也挺简单的用单调队列维护以\((i,j)\)为左上角的正方形里最大最小分别是多少，存到数组里，然后遍历找答案，就这样下面放代码 #include<algorithm> #include<iostream> #include<cst...

2019-01-17

0 481

P1486 [NOI2004]郁闷的出纳员

我是题面题意应该比较清晰，很明显，平衡树轻松应对，我用的是Splay 对于新建操作，我们可以记录之前对工资的调整\(sum\)，在平衡树中插入\(k-sum\)即可，别忘了判断\(k\)是否大于等于\(min\) 对于增加操作，我们给\(sum\)加上\(k\)即可对于减小操作，我们给\...

2019-01-17

0 429