@OceanEye7年前
08/5
16:12
近来的训练暴露了很多的问题
我已经不会打暴力了
可能是OI比赛玩少了，就不会打暴力了？
但是更心寒的是我的知识点的欠缺
一下是待补的坑：
LCT
SA
数学姿势
DP优化姿势
考试的姿势……
心情复杂
@OceanEye7年前
08/4
15:27
题目放出来不是很好……就不放题目和代码了
稍微记录一下考试时候的一些记录
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码农题写个皮皮虾
8.4 小测1
@OceanEye7年前
04/28
20:07
如题……
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
事后
严重怀疑自己被毒奶致死，，明年再战