又是一年省选时，昨天比赛了一天，比较累，但是结局还好。
比赛的成绩wyfenger第一，我第二，认识的人中进入省队的还有 省实验中学的3个（王梦迪（初三），王宇飞，常跃如），郑外的陈科。
结果出来前比较忐忑，因为毕竟这可能是OI生涯的结尾，不过即使可以参加Noi，也只剩下3个月了。
上午的比赛
前两题很简单，简直是NOIP普及组水平，以至于刚开始看到第2题还以为是最小费用最大流，但问题是没有搞到200的人很多，也许河南真的是没有多少人好好学Oi吧！至于第三题，是和牛棚的灯一摸一样原题！（比赛前我还看到了这题，但是没有写）其实 我已经写出 Gauss-Jordan消元法，但是没有考虑多解的情况，检查了半天不对，所以最后还是写了个暴力，总共230
下午的比赛
下午的比赛比上午难一些，第一个问题可以用线段树Ac，但是形式不太一样，不过不是很难想，想了10分钟，加之看到第二题像是个恶心的搜索……所以就决心搞第一题，写了1h，调试+对拍了1.5h（手动对拍），最后还好100分，否则就很悲剧了，（无力吐槽这题的数据，最裸的暴力算法就可以搞到60分）
而第二题其实可以用最短路做，甚至也有模拟Ac的办法，而我在第一题上花了大部分时间，最后仅仅交了个骗分（输出-1能得30……）
总共130
去年省选比今年质量高多了，难度也大多了。。
今后恐怕就不能用win8了，
第一
还有大约5天就到期了
第二，Noi是在Linux下的，所以只能乖乖的用Ubuntu了。
时间已经很少了，水平还差得很远。
又是一年省选时，这是最后一次省选了。
接下来一个星期就复习已学算法吧。。
（只搞下划线的）
1 搜索（...）
2 动态规划
2.1 普通数据结构的动态规划 (按方式)
2.2 记忆化搜索(树形动态规划) (按方式)
2.3 实现博弈问题的求解类型 (按类型)
2.4 状态压缩 (按类型)
3 构造模拟
4 离散数学
4.1 图论
4.1.1 短路径问题
4.1.1.1 单源最短路 MC
4.1.1.1.1 迪杰斯特拉
4.1.1.1.2 有负权回路 Bellman-ford 或 SPFA
4.1.1.2 每个顶点的最短路
4.1.1.2.1 类似传递闭包的floyd算法
4.1.1.3 次短路径
4.1.2 拓扑排序算法
4.1.2.1 DFS求序
4.1.2.2 每次删去没有入度的点
4.1.3 生成树
4.1.3.1 最小生成树
4.1.3.1.1 Prim
4.1.3.1.2 Kruscal
4.1.3.2 次小生成树
4.1.4 连通性
4.1.4.1 强连通分支
4.1.4.2 割,桥算法
4.1.5 网络流
4.1.5.1 最大流流算法:
4.1.5.1.1 福德福克森
4.1.5.1.2 压入与重标号
4.1.5.1.3 Dinic
4.1.5.2 最大流的变种
4.1.5.2.1 有容量下限的网络流
4.1.5.2.2 可行流
4.1.5.2.3 二分图匹配
4.1.5.2.3.1 二分图匹配算法
4.1.5.2.3.1.1 匈牙利算法
4.1.5.2.4 对平面图求最大流(转化为求最短路问题)
4.1.6 回路 通路
4.1.6.1 欧拉回路 通路
4.1.6.1.1 普通的套圈算法
4.1.6.1.2 混合图的算法 NL
4.1.6.2 哈密顿回路 通路
4.1.6.2.1 算法(NP) NL
4.2 组合数学
4.2.1 计数
4.2.1.1 乘法/加法 原理
4.2.1.2 组合计数
4.2.1.2.1 排列组合
4.2.1.2.1.1 有重复的排列与组合,将物体放进盒子里的计数问题
4.2.1.3 数列
4.2.1.3.1 递推关系
4.2.1.3.1.1 求解递推关系
4.2.1.3.2 数列极限求和
4.2.1.4 容斥原理
4.2.1.5 矩阵运算
4.2.1.6 自动机
4.2.1.6.1 有限自动机
4.3 序的应用(见2005国际集训队队员龙凡论文
4.4 数据结构
4.4.1 基本数据结构,Stack,Queue,HASH
4.4.2 树
4.4.2.1 各种平衡树 RBT,SBT,Splay,AVL,Treep
4.4.2.2 线段树
4.4.2.3 堆
4.4.2.3.1 二项堆 斐波那契堆
4.4.2.3.2 Trie
4.4.2.3.3 后缀树
4.4.3 并查集
5 线性代数
5.1 向量
5.2 矩阵
5.2.1 行列式
5.2.1.1 基尔霍夫矩阵(求行列式值)
6 数论
6.1 素数
6.1.1 质因数分解
6.1.2 检查质数
6.1.2.1 筛法
6.1.2.2 O(N0.5)检查
6.2 用高斯消元法求解线性方程组
6.3 二分快速幂
6.4 同余模方程
7 计算几何
7.1 线段,点的位置关系
7.1.1 检查线段是否相交
7.1.2 凸包
7.1.2.1 寻找点集S的凸包算法
7.1.2.2 ???
7.1.3 最小圆覆盖
8 字符串
8.1 字符串匹配
8.1.1 KMP算法
8.1.2 RP算法
8.1.3 O(L|∑|)的字符串匹配自动机
8.1.4 AC自动机
8.1.5 后缀自动机
8.1.6 ???
9 其他
9.1 分块算法(O(n0.5))
标签云
最新评论
最新留言
链接
RSS
