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^kmod p eq x^{kmod 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}^nlfloor frac{n}{i} floor$$
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.