Aspe's Blog

斜率优化DP

数学真**

简介对于形如f[i]=min(k(i)*x(j)+y(j)+b(i))[j<i]，满足k函数有单调性，的DP方程，可以运用数学推导，用单调队列，以O(n)的复杂度解决，这其实就是个板子。max同理，下面讨论min的情况答案都是比出来的在求f[p]时，我们来比1比i与j(i<j<p)对f[p]的贡献吧。若i比j好，用作差法，即f[i->p]-f[j-...

Posted by Aspe on July 31, 2018

开学阶段学习总结

还债，纳命来！

声明任务太多，只能粗略写了，挑重点写了。区间DP 石子合并 f[i][j]与f[i][k]，f[k+1][j]有关，搞搞就好。凸多边形划分把n边形化成n-2个三角形所产生的贡献和最大，f[i][j]代表i与j连了一条边，从点i到j的贡献，然后枚举一个中间点k，这样就构成一个三角形并划分子问题了。删回文串把字符串一直删回文，删成空串的最短步骤，其实不用考虑整个回文...

Posted by Aspe on July 7, 2018

最长上升子序列

只有nlogn

#include <iostream> #include <cstdio> using namespace std; const int oo=233333333; const int ML=100100; int tp; int f[ML]; void Push() { tp++; f[tp]=oo; } int Find(int le,int ri,in...

Posted by Aspe on July 3, 2018

Splay

扶摇直上九万里

简介 Splay，也就是大名鼎鼎的伸展树，是平衡树的一种，说他平衡，其实不平衡，但是均摊就是logn的！并且，Splay灵活多变堪称区间之王，原理也十分暴力，写起来也还好，引用严指导的话，就是“垃圾代码构造器”。核心其核心就在于，能用均摊logn的时间，把一个结点升高，一般是到根结点，然后再进行插入删除等各种操作，也就是说，把一个结点升高，就是一次Splay操作，Splay的所有操...

Posted by Aspe on June 24, 2018

可持久化线段树

修改保留就是插入

定义可以回到某个历史版本的线段树，可以知道前几次修改的情况。这将使线段树有更灵活的应用。做法不难发现，其实，每次修改，我们更改的点，就是从叶子到根的一条路径，只有logn的点改变了，其他还是原样。做法就出来了，把修改变为插入logn个改变的点，并连接到上次修改的，旧的树上，这样就相当于多了一颗新树。图的话可以看此文背景。有几个版本，我们就有了几棵线段树 ...

Posted by Aspe on June 9, 2018

AC自动机的运用

树！

声明对于后缀结点和失配指针两种说法，本文采用后缀(Next)结点这种说法。这里说的后缀树，并不是真正的所谓的后缀树。只是后缀树的一种，或者说，是一种广义的后缀树。 AC自动机见：https://yhf4aspe.github.io/2018/03/17/AC%E8%87%AA%E5%8A%A8%E6%9C%BA/ 注意前缀后缀什么的不要晕啊！要有耐心去分析！ Tr...

Posted by Aspe on May 17, 2018

中考集训规划

停课太好啦

一、数据结构和字符串 splay，可持久化，line-cut tree KMP，Trie，Hash，后缀数组二、DP，数论，图论 DP优化（单调队列，凸包，斜率）数论网络流

Posted by Aspe on May 15, 2018

AC自动机

=Trie+KMP

定义：一如既往的来下个定义： 1，并不是可以帮我们自动AC的东东。 2，不用理解自动机的定义也没关系（其实是我看不懂啦）所以，AC自动机是个什么算法呢？是一种多匹配算法。相比于KMP的一个串匹配另一个串，AC自动机是一个串匹配一个字典。举个例子，就好比在网站注册用户名时，系统会检测是否与其他人重名，AC自动机是用于解决类似的问题的算法。也就是说，AC自动机是...

Posted by Aspe on March 17, 2018

Hello World!

About Me

为什么现在写呢？当然是直到今天才知道要写这个啦。三年前。 “写写总结，搞搞博客，很有帮助。”——jt “吼蛙！”——aspe 20180221 我是Aspe /读SP/ 初中的爱文偏理数学不好的OIer 于GD某高校的附属初中就读（20180707我怎么变某大学附属的高中生了？？？）于小四开始学习信息学（奥电）此博客用于记录我OI的历程。然而以后并不想成为MN/CXY...

Posted by Aspe on March 15, 2018

C++的字符串

C++ 中有一个类，是 string，可以让我们定义一个 string 类型的变量。就是字符串。对应函数库 #include <string> 字符串的定义——“string” 例如：定义一个字符串类型的名为s的变量 string s; // s 初始值为”“——空串 string s（"abcd"); // 可通过这样的方式把 s 的初始值定为"abcd" ...

Posted by Aspe on April 25, 2015