【杂记】2020年3月9日

这是默子几年前写的博客，仅留作纪念！

又是很颓的一天啊……

日常肝题，奇怪的是今天居然没有玩游戏

上午10:30

其实醒来有很长时间了

但是一直懒在床上没有动，看了会 许胤龙的《组合数学引论》

怎么可能看懂，这个东西简直需要两个脑子

对Fibonacci数和Catalan数有了更深刻的认识。

但是还有些不太明白，明天再看看书吧……

唉，当一个蒟蒻的快乐是大佬们永远体验不到的

新知识的海洋在向蒟蒻招手。

至于大佬呢？大佬们忙着发现新的类地星球，不屑于在地表游玩。

安利一款超棒的游戏《坎巴拉的太空计划》

虽然我还不怎么会玩，勉强靠着新手教程发射了第一次火箭

但是游戏真的超棒，物理、航天、宇宙爱好者的最佳选择

这里贴一段游戏评论

本游戏百小时都出不了新手村

但是作为一个太空模拟它做到了尽可能的真实（相比其他游戏

没有什么超光速引擎，没有跃迁，没有虫洞

你用最笨拙的方式——燃料和引力飞向星空

在其他游戏里习惯了线性一样的移动后，回过头来看看这个游戏

它真正代表了人类对太空在历史上的探索

坎巴拉的太空计划-游戏截图

听说最近出系列2了，如果有机会的话，夏天入手，112RMB

学生党伤不起啊……

---

中午12：30

麻婆豆腐香啊，三碗米饭????是日常操作。

写到这里，我觉得我该减肥了????????????

嗯，从明天开始做一些运动吧……

不过，现在吃饱了才有力气明天减肥嘛负罪感--

下午18：00

午觉愣是睡成了下午觉！！！

打开手机，本想着逛一会B站，但是看了看日历

今天距离省选还有——20天啊。

算了，学习吧。

熟悉的洛谷，熟悉的味道

ST表的原理以及实现

今天搞了一下快忘掉的一些数据结构和算法

众所周知，在维护区间最值的时候，我们常用两种算法，一种叫ST表，一种叫线段树

这里主要说下ST表(Sparse Table)

预处理时间复杂度O(nlogn)

查询时间复杂度O(1)

我们首先定义一个初始数据数组和二维的ST表数组

//n为数据大小
int a[n]    存初始数据
//21后面具体再解释,其实当你看完原理也就懂了
int st[n][21]    存ST表

\(st[ i ][ j ]表示的是区间[ i , i+2^j-1 ]里的最大值\)

\(所以，st[ i ][ j ] = max(st[ i ][ j-1 ] , st[ i+2^(j-1) ][ j-1 ])\)

\(这里以维护区间最大值来举例，最大值最小值其实都一样，只有\)max\(和\)min\(的区别\)

初始化ST表

怎么来的呢？

个人觉得，简单来说就是一个 二分+分治 的思想

我们要求区间 \([ i , i+2^j-1 ]\) 里的最大值

可以先求区间 \([ i , i+2^(j-1)-1 ]\) 里的最大值

再求区间 \([ i+2^(j-1) , i+2^j-1 ]\) 里的最大值

最后取这两个区间的最大值

所以，\(st[ i ][ j ] = max(st[ i ][ j-1 ] , st[ i+2^(j-1) ][ j-1 ])\)

如果还是不理解的话，再看一下st数组的含义

\(st[ i ][ j ]\)表示的是区间\([ i , i+2^j-1 ]\)里的最大值

初始化最小单元，也就是 \(st[ i ][ 0 ]\) ，也就是区间 \([ i , i ]\) 里的最大值

for(int i=1;i<=n;i++)
    st[i][0]=a[i];

初始化剩余部分，这里用到了位运算节约时间开销

for(int j=1;(1<<j)<=n;j++)
    for(int i=0;i+(1<<j)<=n;i++)
        st[i][j] = max(st[i][j-1],st[i+(1<<(j-1))][j-1]);

查询ST表

ST表的查询许多萌新上来会迷惑的一个操作

比如，我们要查询区间 \([ l , r ]\) 里的最大值

如果这个区间恰好是ST表里的一个区间 \([ i , i+2^j-1 ]\) ，那么我们就可以直接访问 \(st[i][j]\)

可惜大多时候都不是，那么我们怎么做呢？我们可以这样做

int k = log(r-l+1)/log(2));
int ans = max(st[l][k],st[y-(1<<k)+1][k]);

这里的 \(y\) 是什么呢？ \(y\) 是满足 \(y-(1<<k)+1<=r\) 的最大值

\(k\)是什么呢？\(k\) 是满足 \(2^k<=r-l+1\) 的最大值

最后比较的两个区间 \([l,l+2^k]\) 和 \([r-2^k,r]\) 有可能是重合的，但是答案是唯一的

板子还是要自己打，不然怎么才能背会呢？

晚上22：30

刷题的日子总是这么朴实无华且枯燥

写完博客，一看表居然已经12点了

看来我还是太菜，一篇杂记类博客居然要写一个半小时。

今天AK洛谷第一页黄题，明天继续肝吧，绿题蓝题要提上日程了

之前有位大佬建议我刷满2页蓝，……太犇了。

继续加油吧，不忘初心。