首页 > 笔记 > NOIP算法总结

NOIP算法总结

口胡

1、dp

dp总是会出一个的。去年出了个期望和状压。不知道会不会出矩乘。最近一直在写dp,状态的话就是把所有有后效性的东西放在状态里面记下来,状态数很少的话考虑下状压。转移假如非常有规律的话考虑下矩乘(其实看数据范围就能知道了,logn的效率大概就是矩乘了)。要是再出一年期望。。就考虑成加概率权的平均数就可以了。

个人觉得大概率出树形dp。树形dp是不大虚的,最近模拟赛全都是。一种是裸的直接从叶子一层一层的递推上来。一种是先dfs一次求出子树对点的贡献,再dfs一次求出父亲和兄弟对它的贡献。一直树上随机游走的模型还出了两边,结论用了两次:向上的贡献=度数+所有儿子向上的贡献。向下的贡献=2*n-2-(向上的贡献)

数位dp啥的应该不大考吧= =也没有重点的复习,至今也就会做点裸题。

各种优化的话,比较有可能的是前缀和。有可能斜率会给个10分。平行四边形?不存在的。

2、图论

最短路啥的应该不会考了吧(平面图最小割?初赛已经考过了)分层图最短路也做过很多好题,也很资瓷。

最小生成树也有点裸了。最近出的一套题里面有个最大生成树上二分的思路。感觉很资瓷。

觉得可能考考缩点啥的,点双,边双什么的也没有写过,考前看看板子吧。感觉缩点完DAG上dp是很资瓷的。

在cf上做过很多二分图染色的好题。有时候图/树没方向就可以朝这个方面想想。

欧拉回路就是判一下出度入度。感觉很好搞。

查分约束建完图跑spfa。也挺裸的。

树上的东西也就是lca,要是再有就链剖艹。去年刚考过。

dsu on the tree?感觉能写部分分。

3、数论

组合数刚考了。lucas不看了。

线筛很有可能考一发。反演?不存在的

卡特兰数/斯特林数?有可能,但是太tm难想了。

欧拉函数很有可能。有时间看看性质。

扩欧?有可能求逆元用。

CRT?有毒

容斥?二进制随便艹。

FFT?大概会考NTT(大雾)但是做过一道题DP用NTT思想转移,但是暴力n^2多项式乘,听说也是NOIP难度。

4、数据结构

关于维护数列类的,想想线段树。但是大概都是xjb操作或者查询,那就想想分块。要是分块艹不了就想想查分数组。

链表有时候能艹些部分分。也很好写。

5、字符串

要是裸一点的就kmp,Trie树。AC自动机大概不会考,要是用也是艹部分分用的。后缀数组?感觉不会出。

再难一点exkmp求border?这是上次省选二轮了。

但是kmp上搞事情非常难想啊= =遇到就弃疗吧。

SDOI考过字符串上DP的,好像blog里有题解。

马拉车不学了。要考直接暴力艹


如果你觉的这篇文章不错,分享给朋友吧!

打开微信“扫一扫”,打开网页后点击屏幕右上角分享按钮

×