Aspe's Blog

CSP-S 2019

安心啦，退役啦！

day 若干天前停课 2 周逃避期中考。狂做贪心题。 day 前 1 周学农！然后回家休息。 day 1 t1 格雷码刚开始以为奇数位取反即可，发现不行，又加了个 swap tag。过了大样例，然后不管了丢 1 边。 t2 括号树怎么有人会想本质不同？刚开始想了下前缀和+什么数据结构维护的东西，可做，等等，适当“贪心” 1 下，把合法的括...

Posted by Aspe on November 21, 2019

APIO 2019

打暴力没人权啊！

来补 1 下上古游记。都是 5 月份的事了。前言 APIO 跟期中考狼狈为奸。果断放弃期中考。然后卒。北京天气先是爆嗮！（但那些本地学生都穿长袖外套啊为什么？）然后下了点雨，就变冷了… 最后是刮大风，真搞不懂。昼夜温差大，适合我们晚上乱走的。感觉我们去的地方中老年人和学生居多？老龄化？为了到处走连公交卡都办了…… 比赛分析在后面的那个 day2，不想看流水账就...

Posted by Aspe on February 22, 2019

FJOI 2019 年算法冬令营暨基

祝大家身体健康！

前言来福州一看天地，踏凉雨寄托幽情。与仙人同游天际，枕星宿共度良宵。就在 $2019$ 年的 $2.11$ 到 $2.17$ 日，我们 $\times 10$ $+$ 老师兼家长 $\times 1$，参加了 $FJOI$ 的冬令营，来到了有福之州福州的福师大附中。用 $1$ 句话总结：祝大家身体健康。 day0 赶路天。 day1 白天没安排yes 下午图灵机？？...

Posted by Aspe on February 22, 2019

后缀自动机的实现及应用

假装写完

写在前面将世界终结前最后的画面，配上的将会是怎样的旁白。 ——《世末积雨云》开始了后缀自动机，就是 $1$ 个可以识别字符串的所有子串的有限状态自动机。我们要学的是最简状态后缀自动机。不是最简的就不如暴力了。然后我们可以对子串问题说 bye bye 啦。（雾有限状态自动机终于理解了这玩意。性(gan)感(xing)理解。就是字符串集(状态)的转移。 ...

Posted by Aspe on February 22, 2019

后缀数组的实现 hash&倍增

只有实现

写在前面此文，仅，谈，后缀数组的实现。应用什么的不存在的。后缀数组后缀数组，就是把 1 个字符串的所有后缀排序后的排名数组。也就是帮字符串的所有后缀排个序。最后需要求出 1 个 rank 数组，rank[p] 代表，以 p 开头的后缀的排名几何。这样做有什么用？本文尚且不谈。怎么去做这个事？ hash 大法好就理解成 n 个字符串排序呗。怎么快速比较...

Posted by Aspe on November 16, 2018

NOIp 2018，再见 2018

废了 1 年

突然发现初 3 之后，札记，就负面负面负面。 1 年不如 1 年。写在后面雾，厚雾，裹住我如死水般的心海。风，热风，蒸腾着血液。干，干涸，内心，理想。湿，看不见的对岸，高楼。 day -14 ~ -3 赛前停课集训。练习，模拟，比赛。转圈转圈。终于有 1 点点 feel ，终于…… day -2 ~ -0 ...

Posted by Aspe on November 12, 2018

最短路的 1 点延伸

还是最短路

随谈做了几题最短路题吧，随便写点什么。 SPFA 是真的会被卡，当成平方算法用叭。 dijkstra 强推胜者树实现。优化连边把 1 点连到多点，那就再新建 1 个中间点，把中间点与多点连边，再把那 1 点与中间点连边即可。这个中间点就象征了这个点集，与该点连边，就是 1 点到多点。把 1 点与 1 行/列连边，行/列即为点集把 1 ...

Posted by Aspe on October 19, 2018

胜者树的简单实现

用来写 dijkstra

何为胜者树？先会线段树再会胜者树的都是越俎代庖。不知道胜者树的而会线段树的都是大佬。胜者树是线段树的前置知识。胜者树用于维护固定区间的最大值，且只支持单点修改，完全可以用线段树代替。也可以这样理解，1 个静态的堆。但是进日貌似发现这个有个好实现的写法，并且希望大家不要忘了有这个东西，所以写了此 blog 并且用胜者树去做 1 些问题会比较贴切，因为堆...

Posted by Aspe on September 23, 2018

Digit_DP

与数无关

背景求区间 L~R 之间的数中，满足某些条件的数的个数。条件 1 般有 2 种，对数字 “形” 的要求，比如数字要成山谷型，或不包含某段数字。对数字 “数” 的要求，比如能被什么东西整除，每位之和怎么怎么样。常规套路先把区间转成 1~R-1~L ，然后我们只用求出 1~N 满足条件的数的个数。这时，我们 1 位 1 位推过去。我们注意有两个让我...

Posted by Aspe on August 29, 2018

树型DP

小知识点

树上 01背包例题：最佳团体又是 1 种时间复杂度看起来立方，实则均摊是平方的方法。在树上选 k 个点，使点权和最大，选每个点必须要选他的父亲。 f[u][k]=f[son][k’] 的 01背包我们设 f[u] 是前 i 个孩子合并后的背包，现在要把第 i+1 个孩子 f[v] 合并进去设背包推到的最大容量是 size 那么我们这 1 步的耗...

Posted by Aspe on August 29, 2018

Aspe's Blog

CSP-S 2019

安心啦，退役啦！

APIO 2019

打暴力没人权啊！

FJOI 2019 年算法冬令营暨基

祝大家身体健康！

后缀自动机的实现及应用

假装写完

后缀数组的实现 hash&倍增

只有实现

NOIp 2018，再见 2018

废了 1 年

最短路的 1 点延伸

还是最短路

胜者树的简单实现

用来写 dijkstra

Digit_DP

与数无关

树型DP

小知识点

ABOUT ME

FRIENDS