Summary of my ACM trainning in 2017 Winter Vacation

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

划水,杂,断更