Question

NOIP 如果想得全国一等奖的话需要学习那些知识？

现在已经上高一了 之前只学过一点C语言的皮毛 所以今年只过了初赛 我很想明年或后年 得奖 麻烦 参加过的童鞋详细说一下需要什么书 以及需要学哪些方面的知识

Answer 1

　　必备：【模拟】高精度加、减、乘

　　【图论】图的表示：邻接矩阵，邻接表，边表
　　传递闭包和floyd
　　最小生成树算法(至少会一种)
　　单源最短路dijkstra（O(n2)）或者bellman（spfa优化，O(km)）
　　拓扑排序

　　【树】 树的先序、中序、后序遍历
　　树中的最长路（两遍bfs或者dfs）
　　并查集
　　【搜索】深搜、宽搜
　　【排序】冒泡排序、快速排序 选择排序 记数排序（又称“桶排”）
　　【动态规划】
　　01背包，无限背包
　　【数论】
　　最大公约数和最小公倍数，进制转换

　　需要：【模拟】
　　表达式求值（中缀转后缀，栈的操作）、前缀表达式、中缀表达式、后缀表达式之间的相互转化
　　【树】线段树 字母树
　　【搜索】迭代深搜
　　【动态规划】
　　树形动态规划、最长不下降子序列、最长公共子序列和最长公共子串
　　【排序】归并排序、堆排序

　　【串】 KMP（字串匹配）
　　【数论】 判断质数（sqrt式与筛法求素数）
　　【有序表】顺序表、链表、线段树及其基本操作
　　【图论】
　　Dijkstra算法的堆优化、求割点、求割边、强连通分量、欧拉路（边一次）、汉密尔顿回路（点一次）、差分约束系统
　　【动态规划】
　　状态压缩的动态规划
　　【分治】二分查找、二分答案、最近点对
　　【树】 归并树(逆序对)
　　【其他】
　　Hash、矩形切割（与线段树的比较）
　　【数论】欧拉函数
　　【几何】线段相交
　　【有序表】树状数组
　　【树】 Lca（最近公共祖先）与rmq（区间最值）

　　【图论】匹配算法（最大匹配，最小点覆盖，最小路径覆盖，最大独立集)
　　网络流算法（最大流dinic，最小费用流spfa）
　　【动态规划】动态规划的优化（快速幂，改变状态，优化转移，单调性，四边形不等式）
　　【串】 Kmp扩展、AC自动机
　　【数论】 中国剩余定理、概率与期望
　　【几何】 最远点对（旋转卡壳） 、凸包（水平序和极角序）
　　、半平面交
　　【有序表】平衡树（sbt、treap、splay）后缀数组
　　【其他】随机化算法、高斯消元

　　书：算法导论
　　《Free Pascal语言与基础算法》（第三版）
　　《全国青少年信息学奥林匹克竞赛辅导丛书（中学高级本）》
　　《青少年信息学奥林匹克竞赛实战辅导丛书》系列（《数学与程序设计》和《数据结构与应用》）

Answer 2

C语言的书也很多啊，例如《C语言入门演练100例》就很不错啊，实录呢！

Answer 3

LZ还没学就想拿全国一等奖？应该说是全省一等奖吧？noip是省里的，noi是全国的比赛。难度差别就像中考和高考。省一等奖很容易，需要的知识楼上说的挺全。入门的书嘛，首先把c语言学会，这个你买书或者自学都行。然后要学基础算法，随便买一本讲算法的基础书，你翻翻里面有讲图论啊、排序啊就行了，然后把它学掉。这些学完之后就去网上做题自学，OI不用看什么书，网络是最好的工具。快的话明年得奖没问题，甚至可能在后年冲进国家赛里，不过劝LZ珍惜时间。