联赛前的记录

upd 9.14

1.代码能力不行,比代码能力更不行的是数学能力

2.要认真读题不要读错了

3.看到数据规模(递推次数)特别大的递推要想到矩阵.

4.数学式子要敢于推,然后要细心一点

upd 9.16

1.最值分治可以考虑笛卡尔树,因为有一个性质,设一个区间[l,r]按最值位置pos切开来,[l,pos-1],[pos+1,r]在笛卡尔树上联通

2.如果需要反转操作,要以下标为第二关键字

3.线段树上的赋值标记不能以标记0作为没有标记!!!(因为可能要清空)

4.线段树维护等差数列可以看成维护一次函数y = k * x + b,懒惰标记分别维护k,b

5.线段树上二分不一定要很死板,可以参见kdt玄学剪枝

upd 9.18

1.可以区间合并的问题可以考虑线段树维护(如树的直径),维护时要考虑除了左右儿子外本身有没有多出来的权值
2.对P取模做乘法或次方可以考虑用原根变成加法和乘法(对(P-1)取模)

upd 9.21

1.单射常常要考虑倍增

upd 9.23

一个自我监督

训练计划

已完成:HNOI2015,SDOI2015,TJOI2015,SCOI2015

9.24 JSOI2015D1(已完成)

9.25 JSOI2015D2(已完成)

9.26 SHOI2015D1(因为博主太菜了所以今天去补网络流了)(已完成)

9.28 SHOI2015D2(除计算几何外已完成)

9.29 FJOI2015D1

9.30 线段树分治 FJOI2015D2(争取)(完成)

9.30 ~ 10.01 ZJOI2015(实在肝不动了)

upd 9.24

JSOI2015D1(其实就是随便选了几题,JSOI2015居然有15题....)

1.套娃:一个不是很复杂的贪心,明明思路完全对了,做法也是正解,却不敢写看题解,要把题目的性质写出来吧

2.最大公约数:一个简单的分治(序列问题要考虑分治)

3.字符串树:做过原题,可持久化Trie

4.非诚勿扰(伪装成期望DP的数据结构入门题,不过还是有几个点要注意的,概率要推公式不要靠迭代,注意精度问题)

summary:独立切了二题,还是太过于拘谨还有思维不够灵活

upd 9.25

JSOI D2

1.送礼物分式常常用分数规划解决.(对序列最值分治时间复杂度不总是正确的!)

2.圈地发现我对于最小割的题目,不管多么简单,基本都不会......

3.串分割记住可以在后缀数组上二分字典序的方法

总结:字符串和网络流方面异常薄弱(似乎我什么都薄弱)

upd 9.27

SHOI D1

1.聚变反应炉,一道有难度的树形DP,2h切了,以后做树形DP时想想能不能把自己和父亲拉出来单独考虑

2.零件组装机,分治+人类智慧.....实在不会做(做完了)

3.自动刷题机,sb二分

upd 9.28

网络流学习笔记:

SHOI2017寿司晚宴:最大权闭合子图不一定要拆成类二分图(即内部可能有连边但不干涉答案)的形式,不要思维定式

AHOI2009最小割
最小割可行边:充要1.满流,2.x,y不在一个强连通分量内

必须边:充要1.满流,2,x与S在同一个强连通分量内,y与T在同一个强连通分量内

SHOI D2

1.超能粒子炮.改(一道Lucas定理的较简单题,注意Lucas定理成立条件p is prime,还有注意C(0,0) = 1)
upd 10.3

来一中集训(颓废)七天,想回家...

mex可转化为补集的最小值

upd 10.7 从一中回来啦!

FJOI题真的,好可怜自己是FJ人

upd 10.10

大概是梁静茹给我的勇气去肝ZJOI吧

还剩一道醉醺醺的幻想乡实在肝不动了....

1.地震后的幻想乡,有时要考虑将连续的数学期望转化成离散的,这样可以避开积分,如果f(x)很难求可以考虑将定义改为<=x的所有答案然后通过差分得到答案

初赛前的最后一题吧,最近几天无限颓废

初赛完把之前模拟赛的题补一补.

upd 10.12

几个细节的地方

1.很大的一阶常系数递推数列如果有模数一定会有循环节

2.背包问题要注意如果压缩一维空间就不能转移体积为0的物品(或者需要特判)

upd 10.19

字符串题常见两个套路:相等的传递性,所有情况包含在最大情况的子串中

基础字符串加强训练 (放在题单内,争取这几天要完成).

上周模拟题还有两题没补完....

upd 10.22