NOIP考前划水

2024-08-25 20:18:32

NOIP考前划水

君指先跃动の光は、私の一生不変の信仰に、唯私の超電磁砲永世生き！

要开始背配置了?

3行不谢.

(setq c-default-style "awk")

(global-linum-mode t)

(global-set-key (kbd "RET") 'newline-and-indent)

蒯一些别人写的联赛考点：

基础算法

[x] 快速幂(矩阵快速幂)
[x] 模拟(高精度,高斯消元)
[x] 倍增
[ ] 搜索(dfs,bfs,记忆化搜索,剪枝)
[ ] 贪心(堆优化贪心)
[ ] 动态规划(背包,线性递推,区间dp,概率期望dp,状压dp,树形dp,数位dp,前缀和优化,单调队列优化)
[ ] 分治(二分答案,归并排序,三分法)
[x] 差分,前缀和

基础数据结构

[ ] 栈
[ ] 队列
[ ] 线段树,树状数组
[ ] 并查集&带权并查集
[ ] 链表
[x] ST表

树

[ ] 二叉树(堆,splay)
[ ] 树链剖分
[ ] LCA

基础图论

[x] 图的遍历(dfs,bfs)
[x] 最小生成树(Prim,Kruscal)
[x] 最短路(堆优化Dij,spfa)
[x] tarjan(缩点,点双,边双)
[x] 拓扑排序
[ ] 欧拉路,哈密顿路
[x] 二分图匹配(匈牙利算法)
[ ] 差分约束系统

基础字符串

[x] kmp
[ ] hash
[ ] manacher算法

基础数论

[x] 欧几里德算法
[x] 扩展欧几里德算法
[x] 线性筛素数
[ ] Catalan数
[x] 线性求逆
[x] BSGS&扩展BSGS
[x] 费马小定理
[x] 欧拉函数
[x] CRT&扩展CRT

基础博弈论

[ ] NIM游戏

考试注意事项

如果读入long long,记得修改读优
inf根据题目设置
数组大小(邻接表,网络流点数)
注意不要偷懒把re()直接传参,先开变量存下来
注意单调队列进出队的判断条件都是l<=r而不是l<r,初始化l=1,r=0
Dinic连边时反边的初始边权为0,计边数的cnt初值为1!!!
费用流双向边不可缩
注意二分边界
线段树的区间赋值可能赋值成0,注意懒标记要初始化为-1
分块扫左端边角块时注意枚举的右端点与r取min!!!
倍增注意先进行统计(距离,答案...)操作再u=f[i][u]!!!(锅了无数次了...)
取模(读入取模,三个累加也要模两遍)!!!!!!!!!!!
图论注意起点的设置,不一定都是1为起点
记住随机树表示树高链长期望log
lower_bound(大于等于);upper_bound(大于);--lower_bound(小于);--upper_bound(小于等于)
要处理有关区间去重的问题时,常用到离线算法
注意\(x^k\mod p\neq x^{k\mod p}\mod p\),所以不要不小心把指数模掉了
\[1^2+2^2+..+n^2=\frac{n(n+1)(2n+1)}{6}
\]
\[1^3+2^3+...+n^3=\frac{n^2(n-1)^2}{4}
\]

高级方法

枚举子集

for(int i=s;;i=(i-1)&s){

  //do sth

  if(!i)break;

}

整除分块

求$$\sum_{i=1}^n\lfloor \frac{n}{i}\rfloor$$

for(int l=1,r;l<=n;l=r+1){

  r=n/(n/l);

  ans+=(r-l+1)*(n/l);

}

啃锅计划(去年联赛考题任务)

[x] 10.16a.m.
[x] 10.16p.m.
[x] 10.17a.m.

最新文章

热门文章