【刷题日记】开学前半个月和开学后半个月的刷题总结

COGS468-超级钢琴

应该是我写的第一道NOI,算是一道数据结构题,非常好的一道题。

首先有一个数列,然后每次让你求所有长度在L到R的序列中和最大的那个,一共求k次。

然后存一下前缀和,枚举所有可能的左端点对应的右端点的区间,把这个区间中值(前缀和)最大的点加入到一个大根堆里,然后每次取出堆顶元素并把顶端元素对应区间的次大值加入到堆里,取k次后的所有得到的元素的和就是答案。

次大值的话可以用可持久化线段树,部分数据比较夸张的可能需要离散化。

COGS1708-费波那契平方和

用矩阵瞎搞一下就可以了…….

显然要用快速幂就不用多说了,wanzz有一个比较好理解的公式是f(x)^2=f(x)*f(x+1),如果感兴趣的话可以自行尝试证明一下。

COGS2762-鬼畜の素数

这个是半年前lym和我出在syzoj的一道题,最初的题面跟现在不太一样,当然都是线性筛一波解决了………这个题建议直接看代码。

COGS293-单词查找树

建一颗trie树然后插入的时候记一下新建了几个点就行了,也是2000年的NOI题……….

COGS1946-马拉松

这题还不错,可以稍微讲一下。

建两颗线段树,一颗是正常的,另一颗线段树存的是每个点的前一个点和后一个点的距离与正常的距离的差值,然后查找和修改就很简单了…….

COGS2019-软件包管理器

又是一道NOI,不过这题是非常裸的树剖,直接上代码了。

COGS2559-组合数问题

NOIP2016的day2t1,去年考试的时候把公式化简了一下然后暴力算得了50分……..

正解是利用组合数的递推公式(_{m}^{n}\textrm{C}=_{m-1}^{n-1}\textrm{C}+_{m-1}^{n}\textrm{C})进行预处理,还有要记得%k,然后再开个数组存一下情况数就可以O(1)查询了。

COGS1612-大话西游

不知道怎么说,总之,数据结构题,挺迷的…….代码

COGS1829-普通平衡树

还是数据结构题……大力写了一波treap

写的时候sxy学长一直安利无旋treap………..

COGS2614-滑稽树

第一发树套树,之前树剖+主席树就得了50分,其实用树状数组套权值线段树即可,代码


后记

其实还写了一些题,但是说起来太迷就不放了,下一个月应该会写更多NOIP题吧……..

还是先一省一为目标。

2017.9.9,23:26

6 Comments

发表评论

电子邮件地址不会被公开。 必填项已用*标注