NOIP模拟 3
序列
以为自己很对然后光荣T20
(路丽姐姐原谅我吧)果然是把等比数列的定义记错了,一直没发现等比数列里的项是互成倍数的
正解首先就跟据上点初步判断两项能否成为子段的开头
然后处理出可能的最小公比(用质因数分解的次数除以次数gcd)往后扫
可以利用公比<=1000的hint判掉一堆区间
记得判q=1
收获:
等比数列的定义
如果代价不大,预处理出简单易行的判断合法的标准
游乐场建造https://www.cnblogs.com/antiquality/p/10467704.html
这是T3,然后砸了1h在上面,然后丢人的爆炸了
貌似考场上只有xuefeng拿了分(跪倒就是一%)
又是一道看的懂题解考试做不出的题
题解构造了一种函数g 表示所有点度为偶数的图的数量
然后用非常巧妙的容斥加去重技巧把f表示出来了
收获
构造函数:尝试定义一种好求的函数(当然判断是否好求也是考验思维的事)表示出一种难求的函数
上述行为往往用到容斥,例如此题减去不符合特征(联通)的g中方案
记得去重,有一种技巧是钦定一个特殊点,因为它在每个方案中只可能存在于一个闭包里(传递闭包类)
熟练剖分
压轴T2
题解没懂,但是收获了更优秀的知识
wq学长的思路:期望=总数据/总方案数 避免了dp分数的恶心情况
而且总方案数易于求出,只需要dp每种情况的方案数就行了
dp的时候用到了一类dp的方法,基本情况是
dp框架与dfs相结合
从下往上转移,保证dp父亲时儿子所有数据已经正确求出
父亲的dp与所有儿子有关,按顺序遍历儿子,每个儿子对答案的贡献与前方已经遍历的所有儿子有关(sz,或d,etc)
答案的求出与两类数据有关,存放在两个数组里,单次dp中,这两类数组可以求出有意义的上下界,优化时间复杂度
(skyh:把有价值的信息拿出来组合,给dp送过去)
假如一种dp,父亲从儿子转移,每枚举到一个儿子要遍历前方所有儿子的整棵子树,如何分析这个dp的复杂度呢?
(skyh:考虑点对啊!)
本dp中,一个点,在dp它子孙,或其他深度大于它的点时与他无关
在dp他父链上节点时与他无关
但在dp深度小于他,dp顺序比他父辈靠后的节点时都会遍历到他,最坏情况下此点被计算n次
所以此类dp的复杂度是类似N^2的,上边举的例子是与前方儿子的sz有关,还有的与d有关,例如此题。
只考了35分,考试时真的是一个题都不会
T1是大多数人拿分的题,我因为高考都没学明白而(数据删除)
以为T2能拿很多特判分....(完全二叉树!=完美二叉树)其实是我期望高了
T3由于实力原因和经验不足,连表都没打
要和别人学习的东西太多了...
(另外今早被查违纪了,一上午都心神不宁的...)
(感谢动动的检讨书模板)
最新文章
- Spring+SpringMvc+Mybatis整合注意事项
- OpenBSD内核之引导MBR
- notepad++ 配置Python 调试环境 实用版
- JavaScript寄生组合式继承分析
- Ad-Hoc命令不熟悉的选项
- 每天一个linux命令(38):vmstat命令
- JavaScript 类定义常用方法(转)
- Dijkstra最短路径算法
- vijosP1319 数列
- javascript新的原生态API
- cf B Inna and Candy Boxes
- hdu 4746 Mophues
- Dreamweaver层使用八定律
- python LeetCode 两数相除
- python成功之道
- 我的母校zbvc试做
- Python.tornado.2.tornado.options
- 移动端font-size适配方案(续)
- 雷林鹏分享:Ruby 安装 - Unix
- 反应器(Reactor)模式