YALI集训小记 2019-06-28

生成函数相关

\[ \frac{1}{(1-x)^n}=\sum_i C_{i+n-1}^{n-1} \]

考虑\(n=1\)\(\frac{1}{1-x}\)是一个无限长的每项为1的生成函数,那么\(n\)次方以后是一个可空的隔板法。

计算\(\sum_{i=1}^n(1-x^i)=\sum_{S\in{\{1,2,3….\,n\}}}[sum(S)=i](-1)^i\)

可以用dp解决,\(f[i][j]\)表示\(i\)个数和为\(j\)的方案,但是有一个小于等与\(n\)的限制。

转移:

  • 把所有数都加一
  • 把所有数加一然后添加一个一
  • 减去大于\(n\)的贡献

\(f[i][j]=f[i-1][j-i]+f[i][j-i]-f[i-1][j-n-1]\)

复杂度是根号级别的

线段树区间修改,维护历史版本和

在线段树中记录sum,addv,sumh,addvh。

相当于维护了两个线段树,每颗线段树支持区间加。

那么修改第\(i\)个版本的时候把修改的区间加上\(x\),对应线段树中

\[sum+=(r-l+1)*x,addv+=x,sumh+=(r-l+1)(i-1)*x,addvh+=(i-1)*x\]

也就是说历史版本中加上版本号减一乘上加了的值。

询问历史版本和的时候返回[sum*(现在问的版本号)-sumh]

容斥

遇到不会算的先想容斥!


总结


Day1

今天上午是做题。但是没能想出来任何一题,打完了三题所有暴力分。

预计得分60+57+71=188。

结果第一题错了一个小地方,第三题错了好几个地方,得分59+57+13=129,排在三十几名。

后来发现第三题有一部分的分是因为调试的代码没有改回来,还有一个地方想的有点问题,少考虑了一个情况。

如果没有挂分188分排在14名。

下午安排的是讲题和难题选讲。

讲题的时候发现上午的三题都是之前接触不多或者不太熟悉的题目,有一些必要的结论都不会,所以没做出来,不过这次了解了之后以后碰到就会好很多。

Day2

今天安排的是一天的讲课。

上午8点到11点半讲了树和数据结构,从一些题目中讲了一些数据结构的高级用法,基本上都能听懂,了解了一些比较优秀的算法。

下午讲的是图论,讲了一些比较套路的思想和一些重要的定理。讲的一些关于图论的题目也非常有价值。前面一部分都能听懂,后面几题由于没有学过一些前置知识所以听起来有些吃力,不过还是有些收获。

Day3

今天安排的是上午做题,下午讲课。

上午三题还是打了三题的部分分,54+25+3=82分,排在二十几名。虽然还是没能做出一题,但是相比于上次有了一些进步。

下午讲题的时候发现这些题都是比较经典的套路,别人的人可能都非常熟悉了,而我之前却没有接触过,直接导致做不出题目。除此之外,一些思考问题的角度还是值得学习的。

讲完考试题以后是难题选讲;因为讲的比较快所以听的不是非常理解,还需要巩固学习。

Day4

上午做题。预计得分100+(30~40)+22。实际得分100+30+0。第三题由于是捆绑测试,有一个细节地方打错了一个变量错了一个数据,结果就零分了。排名上还是排在二十几名,如果没有挂分应该在十几名。

下午是讲题和难题选讲。觉得上午的题目都是比较考验思路题目,不像前面几天都是套路的数据结构或者多项式,有些地方确实是没有想到,但是听了题解后发现非常简单并且巧妙,值得学习。

Day5

上午做题。预计得分100+44+100。实际得分100+0+100。因为第二题在做题的时候脑袋一热反了一些低级错误,导致最暴力的题写错了,白丢最简单的44分。本来应该是第七名的,但因为这个暴力分有44分,200分还是排在二十几名。

下午讲题。感觉这次比之前的考试还是要简单一些的。上午不会做的第二题确实比较复杂,是个不太好想不太好打的数据结构。我认为我数据结构方面还是有一些薄弱,需要加强。

Day6

今天一天安排的是讲课。

上午讲课的主题是概率与期望。其中讲解了比较多关于概率期望的巧妙的题目,设计到比较多的方法和一些独特的思路,一些动态规划的方程设计都不太好想,值得学习。还讲了贝叶斯公式和连续密度函数,涉及到积分的一些知识,大部分都可以听懂,有些关于生成函数的知识理解的不是很完善。

下午是难题选讲,也是其他学校的学生来讲解一些他们做过的难题,难度还是比较大,只能听懂部分,剩下的部分还需要更多的消化和理解。

Day7

早上考试,三道题都没没想出正解,打了一些部分分,60+20+20=100。

下午是讲题和难题选讲,上午将的题都需要高级算法和一些套路的思路,我接触过一点但是基本上全部忘记了,虽然可以听懂,但是由于之前没有写过这方面的题目,所以上午没有做出来。这些高级算法和思路还是要多做题开阔眼界。

Day8

今天本来是考试,早上临时换成了讲课。

上午将的是dp,主要分为两个部分,讲了状态方程的设计和DP优化。讲了一些经典题,基本上全部都能听懂。

下午和晚上安排的是杂题/难题选讲。主要是讲一些比较考验思维,有意思的题目。讲到了一些有意义的做法,收获还是比较多的。

Day9

今天安排的是做题。

得分100+40+0,发挥的比较不错,排在第9名。

下午是讲题和难题选讲。发现上午虽然过了第一题,但是方法还是比题解复杂,需要学习题解做法;第二题是三个容斥,做题的时候只想到两个,还是差了一点。

难题选讲的难题难度比较大,有一些知识没有了解过,只听懂了部分,还需要加强。

Day10~12

咕咕咕咕