子谦。

分类

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

/ 注册

全部文章（共61篇）

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

P2331 [SCOI2005]最大子矩阵

我是题面题面这么简洁，清晰，易懂，真是不可多得的良心题面（比我上一篇博客那道题良心多了）我们会发现m只有2 如果m是一个较大的数的话可能会麻烦一点，只有2的话就很好做了我们先来考虑m为1的情况，很简单，\(f[i][j][0/1]\)表示是否选第i个，已经选了j个连续矩形，最大为多少，...

2019-01-15

0 379

P3709 大爷的字符串题

我是题面神奇的阅读题，没有良好的语文功底可能就真的要拿10分了很明显这道题的意思是求区间众数出现的次数的相反数怎么维护呢？又没有强制在线，上莫队啊 \(cnt[i]\)记录\(i\)出现的次数，\(sum[i]\)记录出现i次的数有几个，\(maxa\)记录答案好了，这道题我们做完...

2019-01-10

0 491

UVA10859 Placing Lampposts

我是题面这道题使我知道了一种很神奇的方法，一定要认真看哦如果没有被两盏灯同时照亮的边数应尽量大这个限制的话，这就是一道很经典的树形DP题——没有上司的舞会很可惜，这个限制就在那里，它使得我辛苦写出来的贪心是错的，我只能做到尽量小 /托腮由于总的边数是确定的，我们可以通过维护被一盏灯照...

2019-01-10

0 353

P2286 [HNOI2004]宠物收养场

我是题面题意简单明了，两种数，如果加入一个数的时候有另一种数还存在，那就取出另一种数中与这个数差值的绝对值最小的将其删除（多个则取较小），并对答案产生它们差值的绝对值的贡献，如果没有另一种数存在，那就先将这个数存下平衡树裸题，直接两个平衡树维护就ok了，一个也能维护，稍麻烦一点线段树好像...

2019-01-10

0 506

P1484 种树

我是题面会T+M的方法一：读完题很容易想到直接DP \(f[i][j][k]\)表示到第\(i\)棵树为止共种了\(j\)棵树（\(k\)为1表示包括第\(i\)棵树，否则不包括）最大权值和为多少显然，先不说会T，我们甚至开不下这么大的数组优化掉一维，\(f[i][j]\)表示选\...

2019-01-09

0 413

CF530D sum in the tree

我是题面、原题地址很简单的一道贪心题首先，先想想怎么判断是否合法题目中说，a是自然数，那么子节点的s明显是不能比父节点大的，如果比父节点大，不合法！所有深度为偶数的点的s被删除了，也只有深度为偶数的点被删除了，所以如果深度为奇数的点被删除了，或者有深度为偶数的点没有被删除，不合法！ ...

2019-01-08

0 430

洛谷 P5078 Tweetuzki 爱军训

题目连接很明显，1e6的范围，要么nlgn要么O(n) nlgn的话可能会想到借助一些数据结构，我并没有想到这种做法对于这种题，O(n)的做法要么是线性递推，要么就应该是贪心了考虑这道题我们怎么贪心如果可以走无数个来回的话，那很明显我们可以从小到大依次取出，一定是最大的可惜只能...

2018-12-14

0 391