子谦。

分类

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

/ 注册

全部文章（共61篇）

洛谷 P4116 Qtree3

Qtree系列第三题我是题面读完题大概不难判断是一道树剖的题这道题的关键是记录两种状态，以及黑点的序号（不是编号）线段树啊当然定义两个变量v,f，v表示距离根节点最近的黑点，默认-1，f则表示区间内是否含有黑点，有为1，无为0 那么，怎么才能取当前路径距离根节点最近的黑点的呢？...

2018-07-26

0 386

洛谷 P4114 Qtree1

Qtree系列都跟树有着莫大的联系，这道题当然也不例外我是题面读完题，我们大概就知道了，这道题非常简单，可以说是模板题。树剖+线段树轻松解决直接看代码吧 #include<algorithm> #include<iostream> #include<cst...

2018-07-26

0 373

洛谷 P2647 最大收益

我是题面恩，贪心，鉴定完毕。一个物品是否放进来，取决于它是否能对答案做出贡献。那物品i的贡献就是\(w[i]-r[i]\) 可是收益的减少是会叠加的那就是\(w[i]-j*r[i]\)，j表示选择物品i后又选择的物品数量可是我怎么知道选择i后又会选择几件物品啊那么我们引入一...

2018-07-09

0 298

洛谷 P1972 [SDOI2009]HH的项链

不是裸题，鉴定完毕。我是题面对于这道题，我是离线做的。。。树状数组吧，好些点我们可以很轻易地得到一个很显然的结论，就是关于同一个数，我们只需要记录它不超过当前区间的最后一次出现的位置即可。举例，假设一个区间为[l,5]，数字分别为1,2,3,1,4，那么无论l取几，只要包含了第4个数...

2018-07-09

0 414

洛谷 P3258 [JLOI2014]松鼠的新家

树剖，裸题，鉴定完毕。我是题面读完题，恩，树剖，裸题，没劲。处理很简单，既然每到一个房间吃一块糖，那么就在每条路径上的每个房间放一颗糖，但是每条路径的终点也就是下一条路径的起点，在这里只能加一次，所以别忘记处理完再-1，又因为最后一个点不需要糖，所以直接每条路径的终点的糖-1即可上代...

2018-07-09

0 403

洛谷 P2146 [NOI2015]软件包管理器

真没有想到，这竟然会是一道NOI的原题，听RQY说，这套题是北大出的，北大脑抽认为树剖很难。。。只恨没有早学几年OI，只A这一道题也可以出去吹自己一A了NOI原题啊好了，梦该醒了，我们来看题以后放链接不放题面了，洛谷题面直接拷出来总是很迷我是题面读完题，我们会发现，这道题，好像是...

2018-07-09

0 365

洛谷 P1064 金明的预算方案

好久没做背包的题了，有点生，回去刷几道水题找找感觉，又遇到了这道金明的预算方案还是原来的配方还是原来的味道。本来以为附件数目不限，结果发现至多两个，索性不改了，接着写下去。老规矩，先放题面题目描述金明今天很开心，家里购置的新房就要领钥匙了，新房里有一间金明自己专用的很宽敞的房间。...

2018-07-07

0 352

洛谷 P2015 二叉苹果树

老规矩，先放题面题目描述有一棵苹果树，如果树枝有分叉，一定是分2叉（就是说没有只有1个儿子的结点）这棵树共有N个结点（叶子点或者树枝分叉点），编号为1-N,树根编号一定是1。我们用一根树枝两端连接的结点的编号来描述一根树枝的位置。下面是一颗有4个树枝的树 2 5 \ / ...

2018-06-05

0 424

洛谷 P1471 方差

还是***惯，先放题面题目背景滚粗了的HansBug在收拾旧数学书，然而他发现了什么奇妙的东西。题目描述蒟蒻HansBug在一本数学书里面发现了一个神奇的数列，包含N个实数。他想算算这个数列的平均数和方差。输入输出格式输入格式：第一行包含两个正整数N、M，分...

2018-06-05

0 444

洛谷 P1198 [JSOI2008]最大数

又一道非常简单的线段树入门题先看题题目描述现在请求你维护一个数列，要求提供以下两种操作： 1、查询操作。语法：Q L 功能：查询当前数列中末尾L个数中的最大的数，并输出这个数的值。限制： LL 不超过当前数列的长度。 (L \ge 0)(L≥0) 2、插入操作。语法：A ...

2018-06-04

0 364