OceanEye's Blog

很多人即使只见过一面,已经算见过了最后一面。

I’m back

如果要是认真的算起来的话,我应该实在高一下学期AFK的……主要是高二那段时间实在是太浪太浪了……玩的飞起。

现在回首当年要是少玩一点说不定就进省队了【笑】

现在要重新开始捡起当年学过的知识,准备备战ACM了,目标先在学校里面参加的考试都屠个榜吧,毕竟现在给新大一的练习都不算难。

而且而且,我还没到我的巅峰时期的状态,还记得我曾经是一个数据结构选手【唯一搞不懂的就是LCT【太菜了】】,数学题摸奖选手,部分分选手,但是就是这样还是在高一的时候rush到了全省81名的位置【差一名进Day3】,大概那个时期就是我的巅峰吧。

那段时间其实自己会的算法说多不多,说少也不少了。能想到的都会,甚至还搞过一点点人工智能的东西。不过随着高三的到来,那些算法都被抛之脑后了。

现在再见到算法竞赛,要我现在给自己定下复习顺序的话,应该是

DP动态规划

区间DP,背包问题,数位DP

树形DP

DP的四边形优化,斜率优化

数据结构

线段树,可持久化线段树

平衡树,可持久化平衡树,替罪羊树

树套树

KD树

字符串

KMP,拓展KMP,AC自动机

后缀数组,后缀自动机

回文树,回文自动机

路径压缩

数学

图论

川行随笔

我是早上上的飞机,从广州出发,前往成都参加自主招生考试。
READ MORE →

过去一段时间的记事感想

这里是一枚蒟蒻的博客
READ MORE →

10.16 & 10.17

10.16

一如既往的日子。

READ MORE →

10.15

平淡的一天。

READ MORE →

10.14

今天是成人礼仪式举行的日子。
READ MORE →

第一次的科创

零日目

READ MORE →

心情复杂

近来的训练暴露了很多的问题

我已经不会打暴力了

可能是OI比赛玩少了,就不会打暴力了?

但是更心寒的是我的知识点的欠缺

一下是待补的坑:

LCT

SA

数学姿势

DP优化姿势

考试的姿势……

心情复杂

 

8.4 小测1

题目放出来不是很好……就不放题目和代码了
稍微记录一下考试时候的一些记录
T1

dp[i][j][0/1]

pos : i
cnt : j
Connecting : 0/1

可以留意到最大字典序的子串一定包含了答案
而且一定是从开头包含
可以考虑利用这一点瞎搞
比如我们二分它这条最长串的长度,之后尝试构造?
这里的构造是我们要造出最大串是二分得到串的,且个数尽量小
可以考虑用kmp解决
kmp 匹配之后 在匹配结束的地方砍一刀
没有匹配就继续
这样子就是nlogn的

但是怎么找到最长的子串还是个问题……
我想到的是用SAM
好烦啊不想用SAM啊

T2
F(0,n) = n+1
F(m,0) = F(m-1,1)
F(m,n) = F(m-1,F(m,n-1))

打个表找找规律吧
日哦……真的烦

有点像是

F[0,n]=n+1
F[1,n]=n+2
F[2,n]=2*n+3
F[3,n]=F[2,F[3,m-1]]
F[3,0]=2+3
F[3,1]=4+3*(1+2)
F[3,2]=8+3*(1+2+4) = 29
F[3,3]=2*29+3

打完表
应该是30分
回去看T1
思路没什么错……就是代码量比较大

 

T3还剩五十分钟看出来是一个树链剖分套四tag线段树

mdzz码农题写个皮皮虾

READ MORE →

GDOI记

如题……

DAY 0

[8:00 p.m.]

颠了一个下午的车来到了东莞。

天气很好,基本上就是太阳太阳太阳……果然天气预报一直都是不准的呢。然后在酒店里面就呆了一会,就去东华高中吃饭。跟着某mhx一起看神奇宝贝精灵宝可梦。饭后和mhx一起被一排老师奶炸……还被爆出机房打机的黑历史……心塞

[11:35 p.m.]

临睡前A了两道题,心情愉悦。

GDOI 2017 Bless All.

DAY 1

[11:56 p.m.]
进考场的时候没什么感觉,先拍了一下自己的vim配置……然后发现没有背全?[茫然.jpg]

接下来开考看题。一上来看第一题五分钟,这不是裸一道KMP签到题吗……然后拍了一个半小时= =确认无误之后看了看T2……题面太长跳过了。 看着T3想着这题不可做啊,就写了个35分的暴力,自己过了样例和自己的几个数据时候就没有接着看了。
回头看T2,发现自己会一个n根号n的莫队算法,就开始写……写到考试结束还是有一个小bug,但是无奈还是交了

中午吃饭和其他人交流的时候突然脑子好了……想到T3应该使用广义SAM来跑跑跑接着按照dep深度来过一遍就能做的题目。 T2 whj大神给了个nlogn的神做法……后来被他自己叉掉了。
后来听评讲,第一题不想听,第二题出题人给了O(nlogn)和O(n)的做法[真·神做法]。第三题就是广义SAM。T4是NTT套路题,但是没碰过NTT所以理所应带的没有分了。zawedx还给了个nlogn的做法……很可取的做法

后来出成绩的时候发现只有五十,T1完全没分,全是RE。第一反应是数组开小了,赶紧去复评。
……数组真开小了,直接丢了一百分

睡觉了……明早还有一场考试……看看能不能翻盘吧233
[看脸+看实力的考试啊qwq]

 

DAY2

实力作死吧T3搞炸了

T1签到题分层图SPFA随便过,然而还是有很多人被卡常数[???]

T2出题人给了个有理有据的暴力算法大力用n平方+优化艹掉了n=1e6的数据……不得不服

T3就是个n方的特殊一点的DP,之后利用树状数组瞎搞就可以了

就可以了……然后我作死把那个N方的改成了nlogn的,于是关键的生成字符串就求不了了,就炸了。

T4场上一看这不是炒鸡码农动态点分治么,果断不写……【事实证明这个决定有一半是错误的】

讲评的时候果真听见出题人在说这个点分树,但是好像码量也不是太大?

说什么只要用到期望线性可加就可以搞出一个log方……果然是我too young

GG

DAY3

bless all

先一步离开了东莞,不过早上睡到十二点还是很爽的:-D

 

事后

严重怀疑自己被毒奶致死,,明年再战