OceanEye's Blog

是时候表演真正的技术了!

@OceanEye3月前

08/5
16:12
OI 日常

心情复杂

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

我已经不会打暴力了

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

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

一下是待补的坑:

LCT

SA

数学姿势

DP优化姿势

考试的姿势……

心情复杂

 

心情复杂

@OceanEye3月前

08/4
15:27
OI 日常

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 →

8.4 小测1

@OceanEye6月前

04/28
20:07
OI 日常

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

 

事后

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

GDOI记