发表于

前置知识：后缀树，后缀自动机

问题导入：有一个长度为$5·10^5$的字符串，对这个字符串建立后缀树，后缀树一条边的权值为这条边所代表的字符串中本质不同的子串个数，求这个后缀树边的权值和

来源：$opentrains1464\ Petrozavodsk\ Summer-2015.\ Moscow\ IPT\ Contest\ H.Sasha\ and\ swag\ strings$

今天我们要介绍：压缩后缀自动机$CSAM$:$compacted\ suffix\ automaton$

网上关于压缩后缀自动机的资料极少，本文大部分来自作者思考的结果，发现了很多有意思的小性质。

阅读全文 »

发表于 | 更新于

$cyy$的五一第三天。。。。。

第一天搞了搞视频并写了一坨化学作业，第二天补了一坨题和一坨$tuosh$物理，第三天终于能开训练了

wangbadan队友@nocriz@yangdavid吃喝嫖赌欠下了三点五个亿，带着他们的小姨子跑了

只能自己训练。

当场会了ABCEG，过了BCEG，A是写了一坨发现$mle$，然后发现得改一坨东西才能卡进空间懒得写了

其实有些题场上根本就没看，补题的时候发现大部分题还是可想可做的，但是场上花在码上的时间太多了

再给我点时间J大概率也能想出来，这就六题了。。。。

要是我们三个人的话怎么着也能写七题吧。。。。

突然发现七题是咖啡鸡去年11月的水平。。有点小激动

感觉单人训练的话，果然题会做也写不完

这场难度略大，但也不是特别自闭

感觉效果不错

$task\ lists$：

$F$:想清楚

阅读全文 »

发表于 | 更新于

最近好多题没补，慢慢来吧。包括一些开火车和一些$atcoder$，有一些题队友@yangdavid已经写过了，我就不用再浪费时间了。由于不是训练实录，有些水题就不写了

待补任务：

1.$opentrains1538GJ$啃$std$

阅读全文 »

发表于

opentrains1474题解

分类 有趣 启发性 思维难度 代码难度（*） 总难度（*） 感受 总评价（17）
A 线性代数 4 4.5 3.5 2 5.5 2 14
B 计算几何 2 2 1.5 3 4.5 0 5.5
C 几何 2 2.5 2.5 1.5 4 1 8
D 后缀自动机/树链剖分/主席树和线段树 3.5 4 4 5 9 2 13.5
E trie树 4 2 1 1 2 1 8
F 树上莫队/链表 3 3.5 2.5 3.5 6 1 10
G 构造 4.5 4 4 1 5 2 14.5
H 概率/微积分/数学归纳法 4 4.5 4.5 2 6.5 2 15
I 线段树/单调栈 3 3.5 3.5 3.5 7 2 12
J 树dp 2.5 2 1 1.5 2.5 1 6.5
K 图论 4.5 4.5 4.5 2.5 7 2 15.5
阅读全文 »

发表于

图的可视化问题、havel-hakimi算法、Erdős–Gallai定理

简单无向图的可视化问题：

给定一个度数序列$D={a_1……a_n},a\subset Z^+，a_i$表示$i$号点在某个简单无向图中的度数，问是否有一个简单无向图满足这个给定的度数序列$D$，若有，构造一个，称其为$D$的可视化

阅读全文 »

发表于 | 更新于

opentrains 1498训练记录

Petrozavodsk Winter-2017. Asia-Tsukuba 2016

2019.4.19打，2019.4.21补：

自补，由于网上貌似没人写过题解，我就写一个

阅读全文 »

发表于

Welcome to Hexo! This is your very first post. Check documentation for more info. If you get any problems when using Hexo, you can find the answer in troubleshooting or you can ask me on GitHub.

Quick Start

Create a new post

1
$ hexo new "My New Post"

More info: Writing

Run server

1
$ hexo server

More info: Server

Generate static files

1
$ hexo generate

More info: Generating

Deploy to remote sites

1
$ hexo deploy

More info: Deployment