2017寒假个人冬训总结
2017-1-13
完成CodeForces #385-Div2的ABCD,E题目前问题(标程记忆化,本人DP会WA,初步归纳为上界的处理)
C题是一个贪心的并查集求解连通分量
D题启发较大,利用二进制位的不同进行批量覆盖,精准规避某一给定值
2017-1-14
打完玲珑杯Round#8,rank11
当场做出D(模拟水题,DFS暴搜+map查找),E(离线查询排序)
事后补做B(求树上对于每一点,距离其最远的点的个数)
做出kattis-tractor—二叉树节点数求解结合网格图的经典题
2017-1-15
今日有点浪= =
搞定了1-13剩下的那道DP,过的人非常少,这个题比较恶心。
不过感觉是个贪心与DP结合的不错的题目啊
学习了一下字符串hash,BKDRhash据说很优秀啊?(雾)
有些明白字符串hash的前缀性质原理了,明天继续学习一下。
2017-1-16
初步理解字符串哈希(还是雾)
看了看雨神直播233333
补完#386-Div2
写完解题报告
有时候数据结构无法维护的话可以尺取+贪心去做,还是有点启发
2017-1-17
补了#387-Div2的ABCDE
感觉切水题能力进一步增长?(超级雾)
需要注意的是string类的写法
s+=str[i]复杂度O(1)
s=s+str[i]复杂度O(|s|)
2017-1-18
F已经生无可恋,放弃治疗
写了1-17的解题报告
AK了一套水题堆,对区间右端点排序的贪心有了新的认识(左端点是否排序,在存在左右端点相等的区间的时候会产生影响)
思考问题的时候可以从小数据规模开始思考,然后用某种方法将大数据规模缩小(一个排队先二分逼近,再优先队列小规模枚举)
2017-1-19
AK了JXUFE的一套题,题目质量还可以
需要动脑子吧
感觉自己的乱搞能力显著提升,毕竟一个log被我玩成了2个log还能过
参加了CF,四题滚粗,其实F可做的233333
2017-1-20
补完CF 758(#392-Div2)
得出了题解真傻比的结论
树上的贪心,还是挺有启发意义的
自顶向下,自下而上?23333333
2017-1-21
写了CF 758的题解
做了一下ZZULI的校赛题,嗯大概对字符串蛤习和LCP,SA有了点新的认识
其实知识是死的,主要是要会活用啊
2017-1-22
看了一下某到离线题的题解,感觉离线之后对全局的掌控果然厉害
打了打atcoder,感觉不太想打,于是挂机
WannaflyUnion的题目没补,似乎四个一眼题和两个不可做题目啊
upd= =
A想一想还是可做的,不过又卡常了啊???
F尚不会
2017-1-23
补出了CF #393-Div2的ABCDE
包括
C
对于排列的连通性和有向环的关系
D
$O(1)$的DP转移,通过二分确定前项位置,总复杂度$O(nlogn)$
E!!!
通过差分维护状态,通过区间修改维护差分值,通过线段树以及二分查询最值
需要好好思考,总复杂度$O(nlog^2n)$
2017-1-24
写完CF 760(#393-Div2)解题报告
F题给了大启发
包括通过最小表示对题目进行简化
通过dp求出不同长度子序列个数
通过交叉维护dp进行常数优化
学到了LICS(最长公共上升子序列)的$O(nm)$做法
维护了一个MAX让整个问题都变得简单了呢
想数学题ing。。。
2017-1-25
班聚,划水ing2333333
2017-1-26
学习了一下叉姐的视频
四边形不等式以及完全单调性在DP等问题中的应用和优化
自己推导并写出了CodeForces 321E
目前只会将一维优化到log
据说可以省去这一维,我还是要学习一个233333
2017-1-27
给校赛出题ing,仅写好题面,划水23333
2017-1-28
学会掼蛋233333
给校赛把题出好了,距离十一题目标还有两题
2017-1-29
十一题GET!!!
对于LCA结论题理解的更深了,好想把自己的程序卡掉换航腿的啊,毕竟少一个log23333
原来开了读入外挂差距这么大23333,万万没想到
2017-1-30
斜率优化入门GET!斜率优化
对于DP有了整体而又系统的理解
对于平方型的斜率优化可以直接套模板,模板GET!
2017-1-31
打了CodeForces #394-Div2
感觉还行,一眼看出差分匹配,证明这个trick学到了233333
D是个贪心,感觉出的不错
2017-2-1
补完昨天的F,正式AK #394-Div2
二维前缀和的差分学到了
对二维前缀和的理解加深了不少呢
2017-2-2
打了CodeForces #395-Div2
很多时候对树上的问题,不仅可以以点为主题
也可以从边的角度去看看
不要丢了找特征的思想
2017-2-3 TO 2017-2-11
划水,杂,断更