写在NOIP之前-蒟蒻我到底会什么
发布日期:2022-02-07 06:39:34 浏览次数:1 分类:技术文章

本文共 1767 字,大约阅读时间需要 5 分钟。

明天就是DAY1了吗。。。好快。不过也到了检验自己实力的时候了!现在闲的蛋疼,不妨整理一下我会什么。

考试经验\技巧

必须对拍!!!否则就是作死。

先看题把控一下全局。

数论\数学

欧拉线性筛:在O(n)时间内得到n以内的所有素数,常用来预处理。另外也很容易求解积性函数。

欧拉函数:phi(n)表示不大于n的正整数中与n互质的数的数目。单独求的话,直接分解质因数用容斥原理计算。求一大堆的话,利用欧拉线性筛。

欧几里得算法及其拓展:求最大公约数以及二元一次方程ax+by=1之类的绝对值最小的整数解。时间复杂度均为O(logn).

中国剩余定理:求解最小的非负整数解x满足x%Bi=Ai.若Bi之间均两两互质,则在剩余系下存在唯一解。可以通过构造。

求逆元:用来除法取模的。若最大公约数不为1则没有逆元。否则直接套用拓展欧几里得算法构造方程求解。若模的数是质数则可以简单套用费马小定理。

离散对数及其拓展:给定A,B,C,求A^x%B=C的最小非负整数解.直接套用大步小步算法。可以证明若存在解x,最小解必定小于B.比较熟练这里就不多说了。

二项式定理:直接上递推,或者画出杨辉三角模拟。

组合数取模:大概有以下几种方法:

(1)暴力分解质因数。这个大概都是用高精来算精确值了。。

(2)求一大堆的话,直接利用O(N^2)递推.C(n,m)=C(n-1,m-1)+C(n-1,m).注意边界。

(3)单独求一个的话,(由于有逆元模的数最好是质数),利用O(n)递推,从C(n,i)->C(n,i+1),可以自己手推。

 (4)将模数分解质因数分别处理,最后用中国剩余定理合并。

(5)上面的(4)基本上是万能了,可是常数比较大。。这时候如果模数是质数,我们可以利用卢卡斯定理递归求解。预处理出p以内阶乘的余数,利用以下递归式:

Lucas(n,m)=Lucas(n/p,m/p)*C(n%p,m%p).

一些重要的递推数列:

卡特兰数:h(0)=h(1),h(i)=h(0)*h(i-1)+h(1)*h(i-2)+...+h(i-1)*h(0),此外h(n)=C(2n,n)/(n+1)=C(2n,n)-C(2n,n+1).这个通过打表看一下。。。

斯特灵数:第一类:n个元素划分为k个非空有向环方案数:f(n,k)=f(n-1,k-1)+(n-1)f(n-1,k)

                    第二类:n个元素划分为k个非空等价类方案数:f(n,k)=f(n-1,k-1)+k*f(n-1,k)

构造递推关系思想:考虑最后一个加入的元素的影响。

组合数学:目前的经典模型就是隔板法。。。

图论

1.最短路

SPFA算法:

  单源最短路:存在多种优化。去写DIJ?

  负环判定:只会一种不是非常脑残的方法。

  差分约束系统:利用三角不等式建模。最小值跑最长路,最大值跑最短路。

Dijkstra算法:

  单源最短路:利用堆优化O(mlogn).这种利用优先队列处理距离标号的思想可以拓展到其他题目。不能处理负权值的边。

Folyd算法:

  全局最短路:只可以利用邻接矩阵。O(n^3).主要思想是:f[i][j]表示循环到k时,只中途经过标号不超过k的点时i,j的最短路。那么就容易转移了。

  最小环:已阅。

2.图连通性

有许多贪心技巧。

  强连通分量:利用Tarjan缩点后可成为拓扑图。

  双连通分量:边双连通分量:记录一下上一次走的是那一条边。然后将桥割开就成了许多双连通分量。

                          点双连通分量:将路过的边入栈,每次当low[end[j]]>=dfn[x],就依次处理边,将边上的点加入一个分量,直到遇到边(x,end[j])退出。

3.树的模型

重心:一遍树形dp.

直径:两遍bfs.或树形dp.

Lca:在线倍增算法O(logn).或者离线Tarjan.

4.生成树算法

Prim+heap;Kruskal

动态规划

最难也就是加一点数据结构优化或利用单调性吧。

单调队列?斜率优化?CDQ分治?

数据结构

一大把随便写。。。

贪心

拟阵:想办法证明遗传性、交换性。另外就是元素的权值具有可加性,这样就可以直接贪心。不过这样显然比较复杂。

YY一下然后暴力对拍验证。

一些别的东西

先写这些吧。。略微有一些困了。祝所有OIer在NOIP2014中RP++,再续辉煌!

转载地址:https://blog.csdn.net/wyfcyx_forever/article/details/40899603 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:BZOJ3362 [Usaco2004 Feb]Navigation Nightmare 导航噩梦
下一篇:BZOJ3786 星系探索 蒟蒻出题人给跪

发表评论

最新留言

初次前来,多多关照!
[***.36.149.37]2022年08月05日 03时52分38秒

关于作者

    喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!

最新文章