7
2
2015
1

NOI2015湖南集训

day1

被虐傻。

A根本没往回文自动机上想,学了还不想真是有些结论还是不敢大胆的猜QAQ

B根本没往LCT上想,好吧  我的锅。显然如果与LCT联想起来的话就是道傻逼题。就是不知道考场上能不能写出LCT 

C出的有点儿慢。刚开始一直在想二分什么的,然后又在想能不能搞出一个二维的前缀权值线段树。 事实证明 我想多了

后来才注意到k这么小一定有鬼,那就是和超级钢琴差不多的做法了,然而。。。。用优先队列和setT掉了20分。 还能不能和$STL$愉快的玩耍了啊

UPD:A的话首先需要注意到其实只要求出所有的回文串最少需要多少次能得到就能得到最后的ans,然后所有的回文串又很容易联想到回文自动机。然后再dpdpdp上午脑袋是不是进翔了   只需要求回文串的答案者很显然是正确的但是如果没有往这方面想也是做不出来

晚上和TKD看了一晚上红枣切片机感觉节奏不对啊

day2

看到A题就想肯定是回文自动机, 昨天刚考今天又考 

想的是先用PAM求出所有本质不同的回文子串,然后来个马拉车manacher,因为中心是确定的,然后给最外层的那个字符串打个标记然后一路沿着fa上传上去即可。然后发现找到最长的回文串在PAM中对应的节点不太好搞。先开始写了个fail树上的倍增,发现会T心一狠换成暴力。结果快的飞起当然这样复杂度是没保证的,并不能均摊。后来讲题的时候忽然发现我们直接hash就好了

B题感觉好困难的说,5000W的数据std居然带个log仿佛在刻意逗我笑。我看到这个数据范围就虚的不行,感觉带个log根本不行,也就没有想O(logn)的转移,一直想怎么搞到O(1)。然而无果无奈直接选附近的100个点更新dp值! 下来居然有60

C题看完题目弃疗。好难啊。讲题的时候发现如果是棵树的话我做过这题啊 当然是转化之后的。。。

day3

CJ出题这么照抄原题真的好么?

A题CF#300E

B题傻逼KD-tree或者树套树 跪树爷

C题逗比之星初赛第二场租最后一题

下午好像是停课以来第一次运动

妈蛋暑假减肥8月10号开学你还有暑假么

day4

今天真是跪惨了

A题强行把两道题凑到一起,第一题平衡树随便做,比较新奇的是RHL大神的线段树做法,时光倒流即可。有的时候能写线段树就写线段树,因为线段树写的最多不容易出错。第二题的话其实就是个凸包,然而因为插入是单调的所以直接插就行了我比较二 写了个CDQ,下来发现被艹成傻逼。幸好评测机跑得飞快,本机3s一点儿也不虚。

B题一直yy了半天的分块结果无果,因为求一个前缀和都是求不出来的。。。妈蛋 居然是找规律题。把$S(n,m)$的值打出来发现是个乘法表 应该往这方面想的,答案一定不会复杂,因为这个范围也就求个n和m的欧拉函数QAQ 推导的过程其实也值得思考,感觉数学题还是不太知道该从哪里下手TATAQQQ。这题就是把一个复杂的式子变成了一个暴力的求和然后就是喜闻乐见的套公式什么的了。以后一定要打表!

C题好神,暴力50分走人。准备get一下类欧几里得的正确姿势。以前写的太丑了。

尼玛谁把HN集训的题目放BZ上了,BZ你混腿子啊

day5

A,C一眼秒。A题傻逼SAM+倍增NTT。傻逼题你还写挂中间调了好久NTT最后才发现是没有清空没用的地方QAQ

C题傻逼最小割不多说

B题数论题依旧在数论题面前变傻逼。如果知道那一个推论的话加上了$O(n^{\frac{2}{3}})$的求$μ$函数的前缀和就行了。复杂度很玄学但是跑的飞起。

day6

妈蛋HN集训都喜欢出原题么?

A题傻逼题。

时间基本都花在C上。yy到了正解然后一直卡在奇怪的地方。。。最后1h终于拍对了C的小数据。

忽然看B感觉也是傻逼题,看看trie图上可行边能不能构成环,能的话一定是Yes,否则求个最长链然后比较一下就好了。

12:58的时候过了样例?

考完虚死了,感觉B题绝对炸了。

C题也可能挂精度?

下午去看成绩居然AK了?RP是厉害

day7

题目看起来很有趣的样子。

看到B题n<=20以及位运算的样子,心想一定是FWT什么的。于是决定先去搞B。然后打表猜公式终于到2h的时候写了一个不知道从哪里冒出来的式子然后过对拍了

C题发现我不会删只会加,那就大分治一发,像线段树一样插入。本着骗暴力分的。结果A了果真人还是该有信仰啊

A题没时间了暴力打错

day8

A题傻逼斜率优化。

B,C毒瘤题全不会。早早弃疗去玩红心大战,结果忘了检查内存了爆零了

day9

这场题目也很简单。 脑洞大点其实也可以AK的。

C题公式题,可是我考试的时候脑子进翔了半天推不出来,后来听说是傻逼题于是用了好几种姿势打表发现了规律

A题大傻逼题,比水位这题不知道低到哪里去了。

B题行列式期望QAQ数学渣给跪了 想了半天搞了个O(1)O(10^7)的做法,还以为很高明结果 发现每个设为平均数直接求一发就好了。

因为E(x×y)=E(x)×E(y)于是被一堆AK爷怒艹

哎 我当时为什么不猜一下平均数然后拍一下呢QAQAQQQ

day10

彭多项(雾 的题

毒瘤的题能做?T3傻逼题,T2计算几何30分都写不出来,于是来了个枚举斜率和点,居然有30.第一题直接输出-1.没想到又是找规律题

膜r_64大爷打表找出规律

好像2h就弃疗了 然后玩了3h 4399?

于是湖南集训就这样结束了。

Category: 湖南集训 | Tags: | Read Count: 1561

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

| Theme: Aeros 2.0 by TheBuckmaker.com