A fresh start.

分类 OI 下的文章

October 16, 2018

洛谷TG试炼场DP-lv1总结

晚上做了洛谷TG试炼场的DP lv1 模块,还是大致总结一下。洛谷P1005 矩阵取数游戏区间DP。对于每行,我们可以单独处理。用 $ f[l][r] $ 表示已经取了 $ l..r $ 这个区间后的得分最大值。然后记忆化搜索即可。$ $ 肯定是爆long long了,按理来说应该要写高精的,但是我发现这玩意写高精如果没有运算符重载版的是真的恶心,然后__int128水过去了。#includ...
October 11, 2018

初赛知识点复习

排序希尔排序作者: dreamcatcher-cx 出处: https://www.cnblogs.com/chengxiao/本文版权归作者和博客园共有,欢迎转载,但未经作者同意必须保留此段声明,且在页面明显位置给出原文链接。我们来看下希尔排序的基本步骤,在此我们选择增量gap=length/2,缩小增量继续以gap = gap/2的方式,这种增量选择我们可以用一个序列来表示,n/2,(n...
September 28, 2018

2018年9月做的几道搜索题的总结

我前段时期刷紫书才发现我搜索实在是菜的一匹,近期就在做这方面的题。今天突然有觉得自己该发一篇文章了,于是就有了这个。洛谷P1379 八数码难题这道题其实并不是太难,说到这我想起了一位已经AFO搞物竞的同学花了三个月改了九个版本真正纯种暴搜最后拿了15的故事,主要难点集中在判重。这里我用的是康托展开。康托展开是用来求在n个数的 所有排列组合中 某种排列组合的编号(就是从小到大的第几个)。公式是...
May 26, 2018

紫书第九章-动态规划初步 刷题总结

很久没写过总结了。紫书做了那么多道题,但是我的动规并没有找到什么感觉,也就只有普及难度的可以不看题解写,剩下的都是看着题解写完的,我还是太弱了。这里还是来总结一下吧。例题9-1 UVa1025-A Spy in the Metro$f[i][j]$表示在车站i,时刻是j,还剩多少时间(根紫书略有不同)决策有三个,上左边的车,上右边的车,如果都不开往幼儿园就等一时刻的车。注意还要判断某一时刻是...
April 24, 2018

洛谷4092 [HEOI2016/TJOI2016]树

第一次写树剖没看题解A题,发现题解洛谷题解区大佬里竟然没有一个做法一样的,实在是太激动了树剖学习:https://llf0703.com/p/shu-lian-pou-fen.html题目链接:洛谷 P4092BZOJ P4551方法裸树剖,直接用线段树维护每一段区间中被标记的最深的节点就行了。先全部赋值为-1,然后向上传递时直接取两段中的最大值即可(因为越深的点dfs序越大)还有需要注意的...
April 16, 2018

树链剖分总结

作为一个上个月刚学完线段树的蒟蒻,看Splay又看不懂,便直接跳着来学树剖了。又在一个博客上看到说学树剖之前最好还要把LCA给学了,便去花了一天学了一个Tarjan求LCA(然而后来发现并不怎么需要),然后是几乎照着别人的代码把树剖抄懂的。在这里我就讲一下我理解的树剖。准备工作链表/链式前向星线段树/树状数组/Splay等可以维护一段数据的数据结构LCA (其实只涉及到一些思想,而且几乎用不...
February 6, 2018

最小生成树

概念最小生成树即为无向图中结点构成的树中各边权值之和最小的树,可以有多种情况。一般用Kruskal(克鲁斯卡尔)算法或Prim(普里姆)算法求出。Kruskal算法方法可以将Kruskal算法理解成对边的贪心算法。1.将路径用邻接表存储,存储的值为起点、终点和权值;2.将邻接表按照权值为关键字排序;3.从最小权值的边开始循环,每连接起两个结点就把它们并到同一个集合(并查集实现),连接之前判断...
December 2, 2017

NOIp2017爆炸记

Day -N去年只参加PJ,凑巧拿了个一。今年第一次参加TG,还有在徐妈的逼迫下又参加了PJ,还想拿个高分(事实上死的很惨)Day 0就复习了点简单的东西(毕竟考前三天才学会c++的文件,P转C的痛苦),中午大半时间在颓2048,感觉什么都没干Day 1上午TG。妈的我第一题找了大半个小时都没找出规律就打了个暴力了事;第二题纯种模拟,二十多个变量,样例都过了,当时感觉应该没有问题;第三题直接...