Ⅰ NOIP 适用范围最广的排序算法 和求最短路的算法
快排：
Procere Qsort(l,r:Longint);
var
a,b,mid,t : Longint;
begin
a:=l;b:=r;mid:=which[(l+r) shr 1];
Repeat
while which[a]<mid do inc(a);
while which[b]>mid do dec(b);
If a<=b then
begin
t:=which[a];which[a]:=which[b];which[b]:=t;
inc(a);dec(b);
end;
Until a>=b;
if a<r then Qsort(a,r);
if l<b then Qsort(l,b);
end;
最短路：SPFA
见http://ke..com/view/682464.htm
Ⅱ noip2011准备
可以按照下表复习算法，查漏补缺：
1、排序算法（快排、选择、冒泡、堆排序、二叉排序树、桶排序）
2、DFS/BFS 也就是搜索算法，剪枝务必要学！
学宽搜的时候再复习一下哈希表
3、树
①遍历
②二叉树
③二叉排序树（查找、生成、删除）
④堆（二叉堆、左偏树、堆排序）
⑤线段树（与RMB、树状数组的比较）
6.Trie树
4、图（图论建模）
①最小生成树
②最短路径
③计算图的传递闭包
④连通分量（其中要掌握并查集技术）
强连通分量
⑤拓扑排序、关键路径
⑥哈密尔顿环
⑦欧拉回路
⑧Bell-man Ford、SPFA（能解决负权回路）
⑨二分图（匈牙利算法）
5、动态规划（背包问题只是其中一种）
①线性动规
②区间动规
③树形动规
④图形动规
6、分治（掌握了动规分治就好学了）
7、贪心
8、位运算（可以用来进行优化）
9、网络流
Ⅲ noip初赛选择题会考些什么内容
NOIP初赛考的知识点，大纲上有3块：计算机基本常识、计算机基本操作、程序设计基本知识。具体来说：选择题考查的是计算机基本常识、基本操作和程序设计中的一些基本数据结构与基本算法；而填空题更加重视能力（尤其是队列、栈、二叉树等数据结构、数学问题、归纳法、数列和逻辑推理等）的考查；读程序写运行结果考察的是对程序的理解和跟踪，重在分析推理能力。读程序的4条题目往往有一定的层次，试卷中给出程序的并不复杂，语句的含义容易明白，但是悟性好的选手总是很快就能体会到程序的设计思路并得出正确的答案，机械模仿计算机手工逐步算出结果的同学往往做的很慢，造成时间不够，而且容易失误；完善程序更是考察程序设计能力，尤其是在明确算法和数据结构的条件下，如何编程。读程序和完善程序，需要在平时的学习中提高，经常阅读、讨论和研究别人的优秀程序，提高自己的理解力和速度。
Ⅳ noip要用到哪些算法
前言
离NOIP还有一个星期，匆忙的把寒假整理的算法补充完善，看着当时的整理觉得那时还年少。第二页贴了几张从贴吧里找来的图片，看着就很热血
的。旁边的同学都劝我不要再放PASCAL啊什么的了，毕竟我们的下一级直接学C++。即便我本人对C++也是赞赏有加，不过PASCAL作为梦的开始终
究不能忘记。不像机房中其余的OIERS，我以后并不想学计算机类的专业。当年来学这个竞赛就是为了兴趣，感受计算机之美的。经过时迁，计划赶不上变化，
现在尚处于迷茫之中，也很难说当时做的决定是对是错。然而我一直坚信迷茫的时候选择难走的路会看见更好的风景。
这篇文章简单的说了一下NOIP考试中会常用的算法，可能难度掌握的不是太好，有一部分内容不是NOIP考查范围，然而随着难度的增加，看一些更高级的算法也没有坏处。还有一些非常非常基础的比如链表啊什么的就直接没有写上（别问我为什么整理了那么多的排序算法）。
最后祝大家在NOIP中取得理想的成绩！
搜索
DFS
框架
procere dfs(x);
var
begin
if 达到目标状态 then 输出结果并退出过程;
if 满足剪枝条件 then exit;
for i:=1 to 搜索宽度 do
begin
备份现场；（注意如果现场使用了全局变量，则需要使用局部变量备份）
dfs(参数+增量)；
恢复现场；
end;
优化
（1） 最优化剪枝：求最优值时，当前的状态无论如何不可能比最优值更优，则退出，可与展望结合剪枝
（2） 可行性剪枝：提前判断该状态是否能得到可行解，如不能则退出
（3） 记忆化搜索：对于已经搜索过的状态直接退出
（4） 改变搜索顺序：对于看起来希望更大的决策先进行搜索
（5） 优化搜索策略
（6） 预处理找到大体搜索翻译
（7） 改写成IDA*算法
（8） 卡时（注意现在联赛中禁止使用meml掐时）
BFS
框架
初始化；把初始布局存入
设首指针head=0； 尾指针tail:=1；
repeat
inc(head)，取出队列首记录为当前被扩展结点；
for i：=1 to 规则数 do {r是规则编号}
begin
if 新空格位置合法 then
begin
if 新布局与队列中原有记录不重复
tail增1，并把新布局存入队尾；
if 达到目标 then 输出并退出；
end；
end；
until head>=tail； {队列空}
优化
判重的优化：hash，二叉排序树
双向广搜或启发式搜索
改写成A*算法
二分优化
排序
冒泡排序
var a:array[1..100] of longint;t,n,i,j:longint;
procere sort;
begin
for i:=1 to n-1 do{与每个数都进行比较}
for j:=1 to n-i do
if a[j]>a[j+1] then
begin
t:=a[j];
a[j]:=a[j+1];
a[j+1]:=t;
end;
end;
选择排序
var a:array[1..100] of longint;t,n,i,j:longint;
procere sort;
begin
for i:=1 to n-1 do
for j:=1+i to n do{大数沉小数浮}
if a[j]>a[i] then
begin
t:=a[j];
a[j]:=a[i];
a[i]:=t;
end;
end;
插入排序
var a:array[0..100] of longint;n,i,j,t:longint;
procere sort;
begin
for i:=2 to n do
for j:=1 to (i-1) do
begin
if (a[i]<a[j]) then
begin
t:=a[j];
a[j]:=a[i];
a[i]:=t;
end;
end;
end;
桶排序
var a,b:array[0..100] of longint;r,i,j,t,k,n:longint;
procere sort;
begin
for i:=0 to 100 do b[i]:=0;{为B数组清零，小桶内容清零}
for i:=1 to n do b[a[i]]:=b[a[i]]+1;
{桶的序号就是那个要排序的东西；出现一次，桶里得旗数加一}
for i:=0 to 100 do{扫描所有的桶}
begin
if b[i]<>0 then{桶里有旗}
for j:=1 to b[i] do write(i,' ');{桶的序号就是那个数}
end;
end;
快速排序
var a:array[1..100] of longint;
n,i,h,g:longint;
procere kp(l,r:longint);{变量不能与全局变量相同，否则会被抹去}
var b,m,i,j,t:longint;
begin
i:=l;
j:=r;
m:=a[(l+r) div 2];{基准数最好从中间取}
repeat
while a[j]>m do dec(j);
while a[i]<m do inc(i);{两侧的哨兵移动}
if i<=j then
{哨兵未碰面}{“=”利用repeat循环的性质，使repeat循环得以结束}
begin
t:=a[j];
a[j]:=a[i
a[i]:=t;{交换两个哨兵的值}
inc(j);
dec(j);{哨兵继续运动}
end;
until i>j;
if j>l then kp(l,j);
if i<r then kp(i,r);{都是循环不结束后进行的动作}
end;
begin
read(n);
for i:=1 to n do read(a[i]);
kp(1,n); {“一”位置与“N”位置}
for i:=1 to n-1 do write(a[i],' ');
write(a[n]);{防止多输出空格使程序结果出错}
end.
堆排序
var a:array[1..100] of longint;
n,i,b:longint;
procere jianshu(i:longint);
begin
while ((a[i]>a[i*2])or(a[i]>a[i*2+1]))and(i<=n div 2) do
{当父亲数大于子女数时并且他有孩子时进行}
begin
if a[i*2]<=a[i*2+1]{左儿子小于右儿子}
then
begin
b:=a[i*2]; a[i*2]:=a[i];a[i]:=b;{左右儿子的值互换}
jianshu(i*2);{继续为左儿子建树}
end
else
begin
b:=a[i*2+1];a[i*2+1]:=a[i];a[i]:=b;
jianshu(i*2+1);{上同，不过是为右儿子建树}
end;
end;
end;
procere tiao;
begin
while n<>0 do
begin
write(a[1]);
a[1]:=a[n];
n:=n-1;
for i:=(n div 2) downto 1 do
jianshu(i);
end;
end;
begin
read(n);
for i:=1 to n do
read(a[i]);
for i:=(n div 2) downto 1 do
jianshu(i);
tiao;
end.
数学定理
中国剩余定理
若有一些两两互质的整数m1, m2,… mn，则对任意的整数： a
1, a
2,... an
，以下联立同余方程组对模数m1, m2,… mn 有公解：
康托展开
a[i]为当前未出现的元素中是排在第几个（从0开始）
把一个整数X展开成如下形式：
X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[2]*1!+a[1]*0!
其中a[i]为当前未出现的元素中是排在第几个（从0开始），并且0<=a[i]<i(1<=i<=n)
错排通项
考虑一个有n个元素的排列，若一个排列中所有的元素都不在自己原来的位置上，那么这样的排列就称为原排列的一个错排。
f[1]=0;f[2]=1;
f[n] =(n-1)(f[n-2) + f[n-1])
f[n]:=n![1-1/1!+1/2!-1/3!……+(-1)^n*1/n!]
f[n] = (n!/e+0.5)，其中e是自然对数的底，[x]为x的整数部分。
费马大定理
费马大定理，又被称为“费马最后的定理”，由法国数学家费马提出。它断言当整数n >2时，关于x, y, z的方程 xn + yn = zn 没有正整数解。
被提出后，经历多人猜想辩证，历经三百多年的历史，最终在1995年被英国数学家安德鲁·怀尔斯证明。
费马小定理
假如a是一个整数，p是一个素数，那么 ap ≡a (mod p)。
如果a不是p的倍数，这个定理也可以写成ap-1 ≡1 (mod p)。----这个更加常用
逆元
由费马小定理：假如p是质数，且gcd(a,p)=1，那么ap-1≡1（mod p）
逆元：如果ab≡1（mod p），那么在模p意义下，a、b互为逆元。
所以，假如p是质数，且gcd(a,p)=1，那么a的逆元是ap-2
逆元的作用：在模意义下进行除法。乘a的逆元等同于除以a。
欧拉函数
在数论中，对正整数n，欧拉函数是小于或等于n的正整数中与n互质的数的数目。此函数以其首名研究者欧拉命名，它又称为φ函数、欧拉商数等。
若m,a为正整数，且m,a互素，(gcd(a,m) = 1)，则aφ(m)≡1，其中为φ(m)欧拉函数，mod m为同余关系。
欧拉定理实际上是费马小定理的推广。
Stirling数
第一类s(p,k)的一个的组合学解释是：将p个物体排成k个非空循环排列的方法数。
s(p,k)的递推公式： s(p,k)=(p-1)*s(p-1,k)+s(p-1,k-1) ,1<=k<=p-1
边界条件：s(p,0)=0 ,p>=1 s(p,p)=1 ,p>=0
递推关系的说明：
考虑第p个物品，p可以单独构成一个非空循环排列，这样前p-1种物品构成k-1个非空循环排列，方法数为s(p-1,k-1)；
也可以前p-1种物品构成k个非空循环排列，而第p个物品插入第i个物品的左边，这有(p-1)*s(p-1,k)种方法。
第二类S(p,k)的一个组合学解释是：将p个物体划分成k个非空的不可辨别的（可以理解为盒子没有编号）集合的方法数。
k!S(p,k)是把p个人分进k间有差别(如：被标有房号）的房间(无空房）的方法数。
S(p,k)的递推公式是：S(p,k)=k*S(p-1,k)+S(p-1,k-1) ,1<= k<=p-1
边界条件：S(p,p)=1 ,p>=0 S(p,0)=0 ,p>=1
递推关系的说明：
考虑第p个物品，p可以单独构成一个非空集合，此时前p-1个物品构成k-1个非空的不可辨别的集合，方法数为S(p-1,k-1)；
也可以前p-1种物品构成k个非空的不可辨别的集合，第p个物品放入任意一个中，这样有k*S(p-1,k)种方法。
PS：第一类斯特林数和第二类斯特林数有相同的初始条件，但递推关系不同。
Stirling's approximation
快速求阶乘，不推荐用于竞赛。
数论
GCD&LCM
//GCD
function gcd(a,b:longint):longint;
begin
if b=0 then gcd:=a
else gcd:=gcd (b,a mod b);
end ;
//LCM
function lcm(a,b:longint):longint;
begin
if a<b then swap(a,b);
lcm:=a;
while lcm mod b>0 do inc(lcm,a);
end;
素数
//单个判断
function prime (n: longint): boolean;
var i longint;
begin
for i:=2 to trunc(sqrt(n)) do
if n mod i=0 then exit(false)
exit(true);
end;
//筛法打表
procere main;
var i,j:longint;
begin
fillchar(f,sizeof(f),true);
f[0]:=false;f[1]:=false;
for i:=2 to trunc(sqrt(maxn)) do
if f[i] then
begin
j:=2*i;
while j<= maxn do
begin
f[j]:=false;
inc(j,i);
end;
end;
end;
快速幂
{a^b mod n}
function f(a,b,n:int64):int64;
var t,y:int64;
begin
t:=1;
y:=a;
while b<>0 do
begin
if(b and 1)=1 then t:=t*y mod n;
y:=y*y mod n;
{这里用了一个很强大的技巧,y*y即求出了a^(2^(i-1))不知道这是什么的看原理}
b:=b shr 1;{去掉已经处理过的一位}
end;
exit(t);
end;
模运算法则
(A+B) mod C = (A mod C + B mod C) mod C
(A-B) mod C = (A mod C - B mod C) mod C
(A * B) mod C = (A mod C) * (B mod C) mod C
(A / B) mod C = ???
Ⅳ Noip主要是考什么普及组的C++，主要考什么
一、试题形式
每次NOIP的试题分四组：普及组初赛题A1、普及组复赛题A2、提高组初赛题B1和提高组复赛题B2。其中，A1和B1类型基本相同，A2和B2类型基本相同，但题目不完全相同，提高组难度高于普及组。
（一）初赛
初赛全部为笔试，2小时，满分100分。试题由四部分组成：1、选择题：共20题，每题1.5分，共计30分。每题有5个备选答案，前10个题为单选题（即每题有且只有一个正确答案，选对得分），后10题为不定项选择题（即每题有1至5个正确答案，只有全部选对才得分）。普及组20个都是单选题。
2、问题求解题：共2题，每题5分，共计10分。试题给出一个叙述较为简单的问题，要求学生对问题进行分析，找到一个合适的算法，并推算出问题的解。考生给出的答案与标准答案相同，则得分；否则不得分。
3、程序阅读理解题：共4题，每题8分，共计32分。题目给出一段程序（不一定有关于程序功能的说明），考生通过阅读理解该段程序给出程序的输出。输出与标准答案一致，则得分；否则不得分。
4、程序完善题：共2题，每题14分，共计28分。题目给出一段关于程序功能的文字说明，然后给出一段程序代码，在代码中略去了若干个语句或语句的一部分并在这些位置给出空格，要求考生根据程序的功能说明和代码的上下文，填出被略去的语句。填对则得分；否则不得分。
（二）复赛
复赛的题型和考试形式与NOI类似，全部为上机编程题，但难度比NOI低。每天3.5小时。普及组考一天，共4题，每题100分，共计400分；提高组考两天，每天3题，共6题，每题100分，共计600分。每一试题包括：题目、问题描述、输入输出要求、样例描述及相关说明。测试时，测试程序为每道题提供了5-10组测试数据，考生程序每答对一组得10－20分，累计分即为该道题的得分。
五、试题的知识范围
（一）初赛内容与要求：
计 基 算 本 机 常 的 识
1．计算机和信息社会（信息社会的主要特征、计算机的主要特征、数字通信网络的主要特征、数字化）
2．信息输入输出基本原理（信息交换环境、文字图形多媒体信息的输入输出方式）
3．信息的表示与处理（信息编码、微处理部件MPU、内存储结构、指令，程序，和存储程序原理、程序的三种基本控制结构）
4．信息的存储、组织与管理（存储介质、存储器结构、文件管理、数据库管理）
5．信息系统组成及互连网的基本知识（计算机构成原理、槽和端口的部件间可扩展互连方式、层次式的互连结构、互联网络、TCP/IP协议、HTTP协议、WEB应用的主要方式和特点）
6．人机交互界面的基本概念（窗口系统、人和计算机交流信息的途径（文本及交互操作））
7．信息技术的新发展、新特点、新应用等。
计 基 算 本 机 操 的 作
1. Windows和LINUX的基本操作知识
2. 互联网的基本使用常识 （网上浏览、搜索和查询等）
3. 常用的工具软件使用（文字编辑、电子邮件收发等）
程序设计的基本知识数据结构
1．程序语言中基本数据类型(字符、整数、长整、浮点)
2. 浮点运算中的精度和数值比较
3．一维数组（串）与线性表
4．记录类型（PASCAL）/ 结构类型（C）
程序设计
1．结构化程序设计的基本概念
2．阅读理解程序的基本能力
3．具有将简单问题抽象成适合计算机解决的模型的基本能力
4．具有针对模型设计简单算法的基本能力
5．程序流程描述（自然语言/伪码/NS图/其他）
6．程序设计语言（PASCAL/C/C++）
基本 算法 处理
1．初等算法（计数、统计、数学运算等）
2．排序算法（冒泡法、插入排序、合并排序、快速排序）
3．查找（顺序查找、二分法）
4．回溯算法
（二）复赛内容与要求：
在初赛内容的基础上增加以下内容：
数据结构
1．指针类型
2．多维数组
3．单链表及循环链表
4．二叉树
5．文件操作（从文本文件中读入数据，并输出到文本文件中）
程序设计
1．算法的实现能力
2．程序调试基本能力
3．设计测试数据的基本能力
4．程序的时间复杂度和空间复杂度的估计
算法处理
1．离散数学知识的应用（如排列组合、简单图论、数理逻辑）
2．分治思想
3．模拟法
4．贪心法
5．简单搜索算法（深度优先 广度优先）搜索中的剪枝
6．动态规划的思想及基本算法
Ⅵ 极高分求 noip 常用算法 c++源码
什么？是C++……无奈，我手头的程序都是PASCAL的……
1、初等算法
2、高精度的四则运算
3、查找算法（顺序查找、二分法、哈希查找等等）
这三个较简单，在网络上搜索即可
4、排序算法
其实只需要背快排、堆排即可，其他的速度比较慢不推荐
5、分枝限界法
网络搜索
6、图的算法
floodfill：
#include <graphics.h>
#include <stdlib.h>
#include <stdio.h>
#include <conio.h>
int main(void)
{
/* request auto detection */
int gdriver = DETECT, gmode, errorcode;
int maxx, maxy;
/* initialize graphics, local variables */
initgraph(&gdriver, &gmode, "");
/* read result of initialization */
errorcode = graphresult();
if (errorcode != grOk)
/* an error occurred */
{
printf("Graphics error: %s\n",
grapherrormsg(errorcode));
printf("Press any key to halt:");
getch();
exit(1);
/* terminate with an error code */
}
maxx = getmaxx();
maxy = getmaxy();
/* select drawing color */
setcolor(getmaxcolor());
/* select fill color */
setfillstyle(SOLID_FILL, getmaxcolor());
/* draw a border around the screen */
rectangle(0, 0, maxx, maxy);
/* draw some circles */
circle(maxx / 3, maxy /2, 50);
circle(maxx / 2, 20, 100);
circle(maxx-20, maxy-50, 75);
circle(20, maxy-20, 25);
/* wait for a key */
getch();
/* fill in bounded region */
floodfill(2, 2, getmaxcolor());
/* clean up */
getch();
closegraph();
return 0;
}
7、其他：
KMP:
#include<iostream>
#include<time.h>
#include<string>
using namespace std;
void init(string ,string);
void show(char [],int);
int kmp(string ,string,int pos);
void get_next(char*,int *);
string s1,t1;
int m,n;
char *s;
char *t;
int *next;
/*************************MAIN**************************************/
int main(int argc[],char*args[])
{
double t=clock();
cout<<"找到位置为："<<kmp("acbsabcaacabaabaabcacaabc","abaabca",1)<<endl;
delete[] s;
delete[] next;
cout<<"耗时："<<(clock()-t)/1000<<"毫秒！"<<endl;
return 0;
}
/**********************++++NEXT++++********************************/
void get_next(char s[],int ne[])
{
ne =new int[n+1];
next=new int[n+1];
ne[0]=9999;
int i(1),j(0);
ne[1]=0;
while(i<=(int)(t[0]))//数组是字符型的，要转化为整数
{
if(j==0||t[i]==t[j]){++i;++j;ne[i]=j;}
else j=ne[j];
}
for( i=1;i<=n;i++)
{
cout<<"next["<<i<<"]="<<ne[i]<<endl;
next[i]=ne[i];
}
}
/********************++++KMP+++**********************************/
int kmp(string s0,string t0,int pos)
{
init(s0,t0);
int i=pos,j=1;
while(i<=((int)(s[0]))&&(j<=((int)(t[0]))))
{
if((j==0)||(s[i]==t[j])){++i;++j;}
else j=next[j];
}
if(j>(int)(t[0])) return i-((int)(t[0]));
else return 0;
}
/**********************************************************/
void init(string ss,string tt)
{ s1=ss;
t1=tt;
m=s1.length();
n=t1.length();
//if((s=(char*)malloc((m+1)*sizeof(char)))<0){cout<<"failed\n";return;}
s=new char[m+1];
s[0]=m;
//if((t=(char*) malloc((n+1)*sizeof(char)))<0) {cout<<"failed\n";return;}
t=new char[n+1];
t[0]=n;
for(int i=1;i<=m;i++)
s[i]=s1.at(i-1);
for( i=1;i<=n;i++)
t[i]=t1.at(i-1);
cout<<"原字符串"; show(s,m);
cout<<"模式字符串： "; show(t,n);
get_next(t,next);
}
/*******************++++SHOW+++**************************************/
void show(char s[],int n )
{
for(int i=1;i<=n;i++)
cout<<s[i]<<" ";
cout<<endl;
cout<<"length： "<<int(s[0])<<"\n";
}
prim:
#include <stdio.h>
#define INFINITY 32767
#define MAX 4
typedef struct{
int vexnum;
int arcs[MAX][MAX];
}Graph;//图的结构体
//*****************创建图的邻接矩阵 *****************
void Creat_Graph(Graph *g)
{
int i,j,v1,v2,w,num;
printf("please input vertex number:\n");
scanf("%d",&num);
g->vexnum=num;
for(i=0;i<num;i++)
for(j=0;j<num;j++)
if(i==j)
g->arcs[i][j]=0; //无环，对角线为0
else
g->arcs[i][j]=INFINITY;
printf("please input vertex ,vertex ,weight :(end with -1,-1)\n");
do
{ printf("<vertex1,vertex2,weight>:");
scanf("%d,%d,%d",&v1,&v2,&w);
if(v1>=0&&v1<num&&v2>=0&&v2<num)
{
g->arcs[v1][v2]=w;
g->arcs[v2][v1]=w;
}
}while(!(v1==-1&&v2==-1));//循环的条件
}
Kruskal:
#include<iostream>
#include<vector>
#include<algorithm>
#define max 100
using namespace std;
struct Edge{
int vi,vj,w;
};
bool lequal(Edge const* t1, Edge const* t2){
return (t1->w<t2->w);
}
int V,E;
vector <Edge*>edges;
vector <Edge*>mst;
int cicles[max];
int main(){
int i,W,number,c;
Edge *e;
c=1;
while(true){
edges.clear();
mst.clear();
cin>>V>>E;
if(!V && !E) break;
for(i=0;i<E;i++){
e = new Edge;
cin>>e->vi>>e->vj>>e->w;
edges.push_back(e);
}
sort(edges.begin(),edges.end(),lequal);
for(i=0;i<V;i++) cicles[i] = i;
while(mst.size()<(V-1) && edges.size()){
if(cicles[edges[0]->vi]!=cicles[edges[0]->vj]){
number = cicles[edges[0]->vj];
for(i=0;i<V;i++) {
if(cicles[i]==number)
cicles[i] = cicles[edges[0]->vi];
}
mst.push_back(edges[0]);
}
edges.erase(edges.begin(),edges.begin()+1);
}
W = 0;
for(i=0;i<mst.size();i++) {
W+=mst[i]->w;
}
cout<<"Case "<<c++<<":"<<endl;
cout<<"The Minimun Spanning Tree has cost: "<<W<<endl;
}
return 0;
}
floyd:
program floyd;
var st,en,f:integer;
n,i,j,x:integer;
a:array[1..10,1..10]of integer;
path,map1,map2:array[1..10,1..10]of integer;
begin
readln(n);
for i:=1 to n do
begin
for j:=1 to n do
begin
read(a[i,j]);
path[i,j]:=j;
end;
readln;
end;
for x:=1 to n do
for i:=1 to n do
for j:=1 to n do
if a[i,j]>a[i,x]+a[x,j] then
begin
a[i,j]:=a[i,x]+a[x,j];
path[i,j]:=path[i,x];
end;
readln(st,en);
writeln(a[st,en]);
writeln;
f:=st;
while f<> en do
begin
write(f);
write('=>');
f:=path[f,en];
end;
write(en);
end.
完毕
Ⅶ 关于初中的NOIP问题
这是我从
中华信息学竞赛网http://www.100xinxi.com/上
复制过来的NOIP大纲,你自己看看吧,还什么不懂的,你直接去那看吧``(中华信息学竞赛网)
由中国计算机学会负责组织的全国青少年信息学奥林匹克联赛（National Olympiad in Informatics in Provinces, 简称NOIP）是全国信息学奥林匹克竞赛（NOI）系列活动中的一个重要组成部分，旨在向中学生普及计算机基础知识，培养计算机科学和工程领域的后备人才。普及的重点是根据中学生的特点，培养学生学习计算机的兴趣，使得他们对信息技术的一些核心内容有更多的了解，提高他们创造性地运用程序设计知识解决实际问题的能力。对学生的能力培养将注重以下的几个方面：
1.想象力与创造力；
2.对问题的理解和分析能力；
3.数学能力和逻辑思维能力；
4.对客观问题和主观思维的口头和书面表达能力；
5.人文精神：包括与人的沟通能力，团队精神与合作能力，恒心和毅力，审美能力等。
二、命题程序和组织机构
命题是考核和选拔过程中的重要一环，对计算机的普及的内容具有导向性作用。命题应注重趣味性、新颖性、知识性、应用性和中学生的心智特点，不直接从大学专业教材中选题。
在命题和审题工作中，坚持开放和规范的原则。在NOI科学委员会主持下成立的NOIP命题委员会负责命题工作，命题委员会成员主要来自参加NOIP的省（ 包括直辖市、自治区，下同。每个省最多派一名委员），也可来自社会计算机界。NOIP命题委员会的主要职责是提供NOIP的备选题目，并承担对所提供的题目保密的责任。
1. NOIP命题委员会委员应具备如下资格：
从事一线计算机教学或信息学奥赛辅导工作两年（含）以上；
有精力和时间从事该项工作；
对此项工作有兴趣并愿意作为志愿者从事NOIP命题及其相关工作。
2. NOIP命题委员会委员的产生过程：
本人提出申请（填写表格）；
中学教师需得到所在单位同意或省奥赛主管部门同意；
科学委员会批准，由中国计算机学会颁发聘书（每一聘期为两年）。
3. NOIP命题委员会委员的职责：
每年为NOIP提供备选题题目若干，在9月1日之前提交科学委员会；
备选试题的保密期为2年，在该段时间内不得泄密或另作他用；
搜集本省信息学奥赛的有关信息并向科学委员会通报；
4. 题目一经提交，即表明同意授权中国计算机学会科学委员会全权处理，包括使用、修改和出版。试题原型被科学委员会采用后，中国计算机学会将为命题者颁发试题录用证书，并颁发酬金。无论是委员提交的题目还是科学委员会直接提交的题目，试题版权均归中国计算机学会所有。NOIP所用试题由科学委员会确定，这些试题可能从备选题库中选取并做适当修改后成型，也可能直接命题。
三、竞赛形式和成绩评定
NOIP分两个等级组：普及组和提高组。每组竞赛分两轮：初试和复试。
初试形式为笔试，侧重考察学生的计算机基础知识和编程的基本能力，并对知识面的广度进行测试。初试为资格测试，获本省初试成绩在本赛区前
15%的学生进入复赛。
复试形式为上机编程，着重考察学生对问题的分析理解能力，数学抽象能力，编程语言的能力和编程技巧、想象力和创造性等。各省NOIP的等第奖在复试的优胜者中产生。
比赛中使用的程序设计语言是：
初赛：PASCAL或C/C++：
复赛：PASCAL或C/C++。
每年复赛结束后，各省必须在指定时间内将本省一等奖候选人的有关情况、源程序和可执行程序报送科学委员会。经复审和评测后，由中国计算机学会报送中国科协和教育部备案。中国计算机学会对各省获NOIP二等奖和三等奖的分数线或比例提出指导性意见，各省可按照成绩确定获奖名单。
四、试题形式
每次NOIP的试题分四组：普及组初赛题A1、普及组复赛题A2、提高组初赛题B1和提高组复赛题B2。其中，A1和B1类型基本相同，A2和B2类型基本相同，但题目不完全相同，提高组难度高于普及组。
（一）初赛
初赛全部为笔试，满分100分。试题由四部分组成：
1、选择题：共20题，每题1.5分，共计30分。每题有5个备选答案，前10个题为单选题（即每题有且只有一个正确答案，选对得分），后10题为不定项选择题（即每题有1至5个正确答案，只有全部选对才得分）。普及组20个都是单选题。
2、问题求解题：共2题，每题5分，共计10分。试题给出一个叙述较为简单的问题，要求学生对问题进行分析，找到一个合适的算法，并推算出问题的解。考生给出的答案与标准答案相同，则得分；否则不得分。
3、程序阅读理解题：共4题，每题8分，共计32分。题目给出一段程序（不一定有关于程序功能的说明），考生通过阅读理解该段程序给出程序的输出。输出与标准答案一致，则得分；否则不得分。
4、程序完善题：共2题，每题14分，共计28分。题目给出一段关于程序功能的文字说明，然后给出一段程序代码，在代码中略去了若干个语句或语句的一部分并在这些位置给出空格，要求考生根据程序的功能说明和代码的上下文，填出被略去的语句。填对则得分；否则不得分。
（二）复赛
复赛的题型和考试形式与NOI类似，全部为上机编程题，但难度比NOI低。题目包括4道题，每题100分，共计400分。每一试题包括：题目、问题描述、输入输出要求、样例描述及相关说明。测试时，测试程序为每道题提供了5-10组测试数据，考生程序每答对一组得10－20分，累计分即为该道题的得分。
五、试题的知识范围
（一）初赛内容与要求：
计基
算本
机常
的识 1．计算机和信息社会（信息社会的主要特征、计算机的主要特征、数字通信网络的主要特征、数字化）
2．信息输入输出基本原理（信息交换环境、文字图形多媒体信息的输入输出方式）
3．信息的表示与处理（信息编码、微处理部件MPU、内存储结构、指令，程序，和存储程序原理、程序的三种基本控制结构）
4．信息的存储、组织与管理（存储介质、存储器结构、文件管理、数据库管理）
5．信息系统组成及互连网的基本知识（计算机构成原理、槽和端口的部件间可扩展互连方式、层次式的互连结构、互联网络、TCP/IP协议、HTTP协议、WEB应用的主要方式和特点）
6．人机交互界面的基本概念（窗口系统、人和计算机交流信息的途径（文本及交互操作））
7．信息技术的新发展、新特点、新应用等。
计基
算本
机操
的作 1. Windows和LINUX的基本操作知识
2. 互联网的基本使用常识 （网上浏览、搜索和查询等）
3. 常用的工具软件使用（文字编辑、电子邮件收发等）
程
序
设
计
的
基
本
知
识
数
据
结
构 1．程序语言中基本数据类型(字符、整数、长整、浮点)
2. 浮点运算中的精度和数值比较
3．一维数组（串）与线性表
4．记录类型（PASCAL）/ 结构类型（C）
程
序
设
计 1．结构化程序设计的基本概念
2．阅读理解程序的基本能力
3．具有将简单问题抽象成适合计算机解决的模型的基本能力
4．具有针对模型设计简单算法的基本能力
5．程序流程描述（自然语言/伪码/NS图/其他）
6．程序设计语言（PASCAL/C/C++）- 2003仍允许BASIC
基本
算法
处 理 1．初等算法（计数、统计、数学运算等）
2．排序算法（冒泡法、插入排序、合并排序、快速排序）
3．查找（顺序查找、二分法）
4．回溯算法
（二）复赛内容与要求：
在初赛内容的基础上增加以下内容：
数
据
结
构 1．指针类型
2．多维数组
3．单链表及循环链表
4．二叉树
5．文件操作（从文本文件中读入数据，并输出到文本文件中）
程
序
设
计 1．算法的实现能力
2．程序调试基本能力
3．设计测试数据的基本能力
4．程序的时间复杂度和空间复杂度的估计
算
法
处
理 1．离散数学知识的应用（如排列组合、简单图论、数理逻辑）
2．分治思想
3．模拟法
4．贪心法
5．简单搜索算法（深度优先 广度优先）搜索中的剪枝
6．动态规划的思想及基本算法
六、试题保密纪律
关于保密以及考试的纪律见NOI条例。NOIP主办单位中国计算机学会负责NOIP的纪律监察工作并接受投诉，加强过程监管，防止赛题泄漏、考场舞弊、弄虚作假等现象的发生。一旦查实命题委员会委员泄密备选试题，考场泄题或舞弊，或篡改试卷和考试成绩者，主办单位将根据NOI条例及其有关规则予以惩罚。
Ⅷ 关于NOIP
NOIP级别中，普及组和提高组的要求不同。
但是这几类动规的题目掌握了，基本也就可以了：
1、背包问题：01背包、完全背包、需要构造的多维01背包
详见背包九讲
2、最大降序：例如打导弹
3、矩阵相乘：例如能量珠子
4、买股票
5、方格取数：单向的、双向的
6、三角取数
这些都是简单的动规的应用，必须掌握，背也要背出来，还要会套用。
至于排序，本人认为基本的选择排序大家都会，快速排序是一定要会的，当数据规模<500时用选择排序，当数据规模在500和100000之间是用快速排序，但是NOIP中经常考到基数排序，例如划分数线等，数据规模会达到1000000，用其他的排序法可能会超时一两个测试点。
至于搜索，那是必须掌握的深搜、广搜都要会，主要是深搜，当提高组碰到一下子想不出动规的状态转移方程式，深搜穷举也是可行的，一般都能拿到不少的分数。个人之间广搜的用处不大，程序复杂而且爆机率很高。当然n个for的穷举法在不得已的时候也能得不少分，只要if剪枝的好，对付八后问题等问题时，时间效率比很高。
另外就是图的遍历，有关图的最小生成树、图的单源最短路径，也是需要很好地掌握，一直会考。当然，深搜的本事高的人可以用深搜搞定。
总结如下：要得一等，必须对模拟法和穷举法有深刻的体会，并知道很多变通的手段；对快排要背的滚瓜烂熟；对深搜要做到不管是贪心还是动规的题，都能用深搜实现，只不过少量点超时而已；动规要记住六大模型，然后背包要理解透彻；数学很重要，数学分析的题要做对，例如排组合、凸包、计算几何近几年常考。有了这些，一等可以稳拿。
Ⅸ 学C语言的NOIP问题
一．选择一个正确答案代码（A/B/C/D/E）,填入每题的括号内 (每题1.5分, 共30分)
1. 美籍匈牙利数学家冯·诺依曼对计算机科学发展所做出的贡献是（ ）。
A. 提出理想计算机的数学模型，成为计算机科学的理论基础。
B. 是世界上第一个编写计算机程序的人。
C. 提出存储程序工作原理，并设计出第一台具有存储程序功能的计算机EDVAC。
D. 采用集成电路作为计算机的主要功能部件。
E. 指出计算机性能将以每两年翻一番的速度向前发展。
2. 下列哪个不是CPU（中央处理单元）（ ）。
A. Intel Itanium B. DDR SDRAM C. AMD Athlon64
D. AMD Opteron E. IBM Power 5
3. 下列网络上常用的名字缩写对应的中文解释错误的是（ ）。
A. WWW（World Wide Web）：万维网。
B. URL（Uniform Resource Locator）：统一资源定位器。
C. HTTP（Hypertext Transfer Protocol）：超文本传输协议。
D. FTP（File Transfer Protocol）：快速传输协议。
E. TCP（Transfer Control Protocol）：传输控制协议。
4. 下面哪个部件对于个人桌面电脑的正常运行不是必需的（ ）。
A. CPU B. 图形卡（显卡） C. 光驱 D. 主板 E. 内存
5. 下列哪个软件属于操作系统软件（ ）。
A. Microsoft Word B. 金山词霸 C. Foxmail D. WinRAR E. Red Hat Linux
6. 下列哪个不是计算机的存储设备（ ）。
A. 文件管理器 B. 内存 C. 高速缓存 D. 硬盘 E. U盘
7. 下列说法中错误的是（ ）。
A. CPU的基本功能就是执行指令。
B. CPU访问内存的速度快于访问高速缓存的速度。
C. CPU的主频是指CPU在1秒内完成的指令周期数。
D. 在一台计算机内部，一个内存地址编码对应唯一的一个内存单元。
E. 数据总线的宽度决定了一次传递数据量的大小，是影响计算机性能的因素之一。
8. 彩色显示器所显示的五彩斑斓的色彩，是由红色、蓝色和（ ）色混合而成的。
A. 紫 B. 白 C. 黑 D. 绿 E. 橙
9. 用静电吸附墨粉后转移到纸张上，是哪种输出设备的工作方式（ ）。
A. 针式打印机 B. 喷墨打印机 C. 激光打印机 D. 笔式绘图仪 E. 喷墨绘图仪
10. 一台计算机如果要利用电话线上网，就必须配置能够对数字信号和模拟信号进行相互转换的设备，这种设备是（ ）。
A. 调制解调器 B. 路由器 C. 网卡 D. 网关 E. 网桥
11. 下列哪个不是数据库软件的名称（ ）。
A. MySQL B. SQL Server C. Oracle D. 金山影霸 E. Foxpro
12. 下列哪个程序设计语言不支持面向对象程序设计方法（ ）。
A. C++ B. Object Pascal C. C D. Smalltalk E. Java
13. 由3个a，1个b和2个c构成的所有字符串中，包含子串“abc”的共有（ ）个。
A. 20 B. 8 C. 16 D. 12 E. 24
14. 某个车站呈狭长形，宽度只能容下一台车，并且只有一个出入口。已知某时刻该车站状态为空，从这一时刻开始的出入记录为：“进，出，进，进，出，进，进，进，出，出，进，出”。假设车辆入站的顺序为1，2，3，……，则车辆出站的顺序为（ ）。
A. 1, 2, 3, 4, 5 B. 1, 2, 4, 5, 7 C. 1, 3, 5, 4, 6 D. 1, 3, 5, 6, 7 E. 1, 3, 6, 5, 7
15. 二叉树T，已知其前序遍历序列为1 2 4 3 5 7 6，中序遍历序列为4 2 1 5 7 3 6，则其后序遍历序列为（ ）。
A. 4 2 5 7 6 3 1 B. 4 2 7 5 6 3 1 C. 4 2 7 5 3 6 1 D. 4 7 2 3 5 6 1 E. 4 5 2 6 3 7 1
16. 满二叉树的叶结点个数为N，则它的结点总数为（ ）。
A. N B. 2 * N C. 2 * N – 1 D. 2 * N + 1 E. 2N – 1
17. 十进制数2004等值于八进制数（ ）。
A. 3077 B. 3724 C. 2766 D. 4002 E. 3755
18. (2004)10 + (32)16的结果是（ ）。
A. (2036)10 B. (2054)16 C. (4006)10 D. (100000000110)2 E. (2036)16
19. 在下图中，从顶点（ ）出发存在一条路径可以遍历图中的每条边一次，而且仅遍历一次。
A. A点 B. B点 C. C点 D. D点 E. E点
20. 某大学计算机专业的必修课及其先修课程如下表所示：
课程代号 C0 C1 C2 C3 C4 C5 C6 C7
课程名称 高等数学 程序设计语言 离散数学 数据结构 编译技术 操作系统 普通物理 计算机原理
先修课程 C0, C1 C1, C2 C3 C3, C7 C0 C6
请你判断下列课程安排方案哪个是不合理的（ ）。
A. C0, C6, C7, C1, C2, C3, C4, C5 B. C0, C1, C2, C3, C4, C6, C7, C5
C. C0, C1, C6, C7, C2, C3, C4, C5 D. C0, C1, C6, C7, C5, C2, C3, C4
E. C0, C1, C2, C3, C6, C7, C5, C4
二．问题求解 （每题5分，共10分）
1. 一个家具公司生产桌子和椅子。现在有113个单位的木材。每张桌子要使用20个单位的木材，售价是30元；每张椅子要使用16个单位的木材，售价是20元。使用已有的木材生产桌椅（不一定要把木材用光），最多可以卖 元钱。
2. 75名儿童到游乐场去玩。他们可以骑旋转木马，坐滑行铁道，乘宇宙飞船。已知其中20人这三种东西都玩过，55人至少玩过其中的两种。若每样乘坐一次的费用是5元，游乐场总共收入700，可知有 名儿童没有玩过其中任何一种。
三．阅读程序 （每题8分，共32分）
1．#include <stdio.h>
int main(){
int a = 79, b = 34, c = 57, d = 0, e = -1;
if (a < c || b > c) d = d + e;
else if (d + 10 < e) d = e + 10;
else d = e - a;
printf("%d\n", d);
return 0;
}
输出： 。
2．#include <stdio.h>
int main(){
int i, j;
char str1[] = "pig-is-stupid";
char str2[] = "clever";
str1[0] = 'd'; str1[1] = 'o';
for (i = 7, j = 0; j < 6; i++, j++)
str1[i] = str2[j];
printf("%s\n", str1);
return 0;
}
输出： 。
3．#include <stdio.h>
int main(){
int u[4], a, b, c, x, y, z;
scanf("%d %d %d %d",&(u[0]), &(u[1]), &(u[2]), &(u[3]));
a = u[0] + u[1] + u[2] + u[3] - 5;
b = u[0] * (u[1] - u[2] / u[3] + 8);
c = u[0] * u[1] / u[2] * u[3];
x = (a + b + 2) * 3 - u[(c + 3) % 4];
y = (c * 100 - 13) / a / (u[b % 3] * 5);
if ((x + y) % 2 == 0) z = (a + b + c + x + y) / 2;
z = (a + b + c – x - y) * 2;
printf("%d\n", x + y - z);
return 0;
}
输入：2 5 7 4
输出： 。
4．#include <stdio.h>
char c[3][200];
int s[10], m, n;
void numara(){
int i, j, cod, nr;
for (j = 0; j < n; j++){
nr = 0; cod = 1;
for (i = 0; i < m; i++){
if (c[i][j] == '1'){
if (!cod){cod = 1; s[nr]++; nr = 0;}
}
else{
if (cod){nr = 1; cod = 0;}
else nr++;
}
}
if (!cod) s[nr]++;
}
}
int main(){
int i;
scanf("%d %d\n", &m, &n);
for (i = 0; i < m; i++) gets(c[i]);
numara();
for (i = 1; i <= m; i++)
if (s[i] != 0) printf("%d %d ", i, s[i]);
return 0;
}
输入：
3 10
1110000111
1100001111
1000000011
输出： 。
四、完善程序 (前4空，每空2分，后5空，每空4分，共28分)
1．三角形内切圆的面积
题目描述:
给出三角形三边的边长，求此三角形内切圆（如下图所示，三角形的内切圆是和三角形三边都相切的圆）的面积。
输入:
三个正实数a、b、c（满足a+b>c，b+c>a，c+a>b）, 表示三角形三边的边长。
输出:
三角形内切圆的面积，结果四舍五入到小数点后面2位。
输入样例:
3 4 5
输出样例:
3.14
程序：
#include <stdio.h>
#include <math.h>
int main(){
float a, b, c, r, s, t;
scanf("%f %f %f", &a, &b, &c);
s = ( ① ) / 2;
t = ② (s * (s - a) * (s - b) * (s - c));
r = t / s;
printf(" ③ \n", 3.1415927 * r * ④ );
return 0;
}
2．Joseph
题目描述:
原始的Joseph问题的描述如下：有n个人围坐在一个圆桌周围，把这n个人依次编号为1，…，n。从编号是1的人开始报数，数到第m个人出列，然后从出列的下一个人重新开始报数，数到第m个人又出列，…，如此反复直到所有的人全部出列为止。比如当n=6，m=5的时候，出列的顺序依次是5，4，6，2，3，1。
现在的问题是：假设有k个好人和k个坏人。好人的编号的1到k，坏人的编号是k+1到2k。我们希望求出m的最小值，使得最先出列的k个人都是坏人。
输入:
仅有的一个数字是k（0 < k <14）。
输出:
使得最先出列的k个人都是坏人的m的最小值。
输入样例:
4
输出样例:
30
程序：
#include <stdio.h>
long k, m, begin;
int check(long remain){
long result = ( ① ) % remain;
if ( ② ){
begin = result; return 1;
}
else return 0;
}
int main(){
long i, find = 0;
scanf("%ld", &k);
m = k;
while( ③ ) {
find = 1; begin = 0;
for (i = 0; i < k; i++)
if (!check( ④ )){
find = 0; break;
}
m++;
}
printf("%ld\n", ⑤ );
return 0;
}
赛区 市 学校 姓名
========================== 密 封 线 =======================
第九届全国青少年信息学奥林匹克联赛初赛试题
普及组答卷纸
阅 卷 记 录
总阅卷人 总 得 分
第 一 大 题 得 分 第二大题得分
题号 1 2 3 4 5 6 7 8 9 10 第三大题得分
得分 1) 2) 3) 4)
题号 11 12 13 14 15 16 17 18 19 20 第四大题得分
得分 (1) (2)
============================ 以下由考生填写 ==============================
答卷部分
一. 选择一个正确答案代码（A/B/C/D）,填入每题的括号内 (每题1.5分,多选无分, 共30 分)
题号 1 2 3 4 5 6 7 8 9 10
选择
题号 11 12 13 14 15 16 17 18 19 20
选择
二．问题解答 （每题5分，共10分）
1. 答：
2. 答：
三. 阅读程序，并写出程序的正确运行结果：（每题8分，共32分）
（1） 程序的运行结果是:
(2) 程序的运行结果是:
赛区 市 学校 姓名
========================== 密 封 线 =======================
（3） 程序的运行结果是:
（4）程序的运行结果是:
四.根据题意, 将程序补充完整 (前4空，每空2分，后5空，每空4分，共28分)
C 语言
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
1.
①
②
③
④
2.
①
②
③
④
⑤
第九届全国青少年信息学奥林匹克联赛初赛试题
普及组参考答案
一. 选择一个正确答案代码（A/B/C/D/E）,填入每题的括号内 (每题1.5分,多选无分, 共30 分)
题号 1 2 3 4 5 6 7 8 9 10
选择 C B D C E A B D C A
题号 11 12 13 14 15 16 17 18 19 20
选择 D C D E B C B D E D
二．问题解答 （每题5分，共10分）
1. 答： 160
2. 答： 10
三. 阅读程序，并写出程序的正确运行结果：（每题8分，共32分）
（1）程序的运行结果是: -80
(2) 程序的运行结果是: dog-is-clever
（3）程序的运行结果是: 263
（4）程序的运行结果是: 1 4 2 1 3 3
四.根据题意, 将程序补充完整 (前4空，每空2分，后5空，每空4分，共28分)
C 语言
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
1.
① a+b+c
② sqrt
③ %.2f
④ r
2.
① begin+m-1
② result>=k (或者k<=result)
③ !find (或者 find==0)
④ 2*k-i
⑤ m-1
参考资料：www.noi.cn