OI 知识点汇总
[题解] [CTSC2006] 歌唱王国

[题解] [CTSC2006] 歌唱王国

给定 $n$ ,代表有 $n$ 种字符。再给出多个数组 $a$ ,记其长度为 $m$,$1\le a_i\le n$。每次随机写下出一个字符,求第一次写下这个数组(即写下的字符串后缀为该数组)期望要写多少个字符。

阅读更多
kamet | 基于 LLVM 的编程语言的实现

kamet | 基于 LLVM 的编程语言的实现

摘要

本文阐述了一门基于 LLVM 的编程语言的实现过程,分析并解决了多个实现难点,基于实际问题在现有的知识上进行拓展并得出更好的解决方案和理论知识,进而对编译原理获得更加深入的认识。

阅读更多
[题解] [IOI2008] Island

[题解] [IOI2008] Island

这道题确实非常简单… 只是没有看懂其他题解为什么要用单调队列,明明记两个最大值就可以解决?


题目大意是给出一个基环树森林(每一个点有一条无向边),让你求出所有基环树的直径(即一条不经过重复点的基环树上的最长路径)之和。

阅读更多
[题解] [TJOI2013] 单词

[题解] [TJOI2013] 单词

一篇论文是由许多单词组成,但小张发现一个单词会在论文中出现很多次,问每个单词分别在论文中出现了多少次。

$1\le n \le 200$,单词总长度不超过 $10^6$。

阅读更多
关于广义后缀自动机

关于广义后缀自动机

约束

tar[x][c]:SAM 转移

pre[x]:常用名有 linkfail(反正就那个东西)

len[x]:结点 x 代表的最长字符串的长度


广义后缀自动机(下文用广义 SAM 指代),即用多个字符串的后缀建出的一个后缀自动机,拥有和后缀自动机相似的性质。

有三种较流传广泛的广义后缀自动机写法:

阅读更多
Lena | Cena 的 Linux 客户端

Lena | Cena 的 Linux 客户端

最近几次交题由于是在 Ubuntu 上,所以只能把程序放到 ftp 上面去,并不怎么方便。于是乎把以前的破旧项目拖出来重写了一番。

阅读更多
关于对线
Ubuntu 启动失败?
C++ 代码压行机