一、单项选择题（共20题，每题1.5分，共计30分。每题有且仅有一个正确答案。）
1、 关于图灵机下面的说法哪个是正确的：（ D）
A.图灵机是世界上最早的电子计算机。
B.由于大量使用磁带操作，图灵机运行速度很慢。
C.图灵机是英国人图灵发明的，在二战中为破译德军的密码发挥了重要作用。
D.图灵机只是一个理论上的计算模型。
【解析】所谓的图灵机就是指一个抽象的机器，它有一条无限长的纸带，纸带分成了一个一个的小方格，每个方格有不同的颜色。有一个机器头在纸带上移来移去。机器头有一组内部状态，还有一些固定的程序。在每个时刻，机器头都要从当前纸带上读入一个方格信息，然后结合自己的内部状态查找程序表，根据程序输出信息到纸带方格上，并转换自己的内部状态，然后进行移动。
2、关于计算机内存下面的说法哪个是正确的：（ B）
A.随机存储器（RAM）的意思是当程序运行时，每次具体分配给程序的内存位置是随机而不确定的。
B.1MB内存通常是指1024*1024字节大小的内存。
C.计算机内存严格说来包括主存（memory）、高速缓存（cache）和寄存器（register）三个部分。
D.一般内存中的数据即使在断电的情况下也能保留2个小时以上。
【解析】A项： RAM不是位置随机，而是随时访问。所谓“随机存储”，指的是“当存储器中的消息被读取或写入时，所需要的时间与这段信息所在的位置无关。”
B项：1MB=1024KB , 1KB=1024 B
C项：计算机内存包括严格来说包括只读存储器（RAM）、随机存储器（ROM）和高速缓存（CACHE）。如果不严格来说只包含只读存储器和随机存储器。
D项：内存中的数据断电立即丢失。
3、关于BIOS下面说法哪个是正确的：（A）
A.BIOS是计算机基本输入输出系统软件的简称。
B.BIOS里包含了键盘、鼠标、声卡、显卡、打印机等常用输入输出设备的驱动程序。
C.BIOS一般由操作系统厂商来开发完成。
D.BIOS能提供各种文件拷贝、复制、删除以及目录维护等文件管理功能。
【解析】BIOS是英文”Basic Input Output System”的缩略词，直译过来后中文名称就是”基本输入输出系统。所以A对。
因为是存在主板上（硬件）的一个程序，所以跟操作系统没关系，是电脑生产厂家决定的，C错。
BIOS主要功能：（1）通电自检（2）初始化和检测（3）引导程序。不具备文件拷贝等功能，D错。
4、关于CPU下面哪个说法是正确的：（A ）
A.CPU全称为中央处理器（或中央处理单元）。
B.CPU可以直接运行汇编语言。
C.同样主频下，32位的CPU比16位的CPU运行速度快一倍。
D.CPU最早是由Intel公司发明的。
【解析】
A：CPU（central processing unit）全称中央处理器，
B：CPU不可以直接执行汇编语言，汇编语言虽然是低级语言但也是语言，CPU只认机器码，要编译成以后才可以运行。
C：相比16而言，32位拥有更大的寻址能力，而且能提取比16多一倍的的数据，所以比16位快，更快的执行速度，更大的内存管理（只能说处理字长不同，但速度难说谁快，因为还受到内存等其他条件约束）
D：肯定不是intel。是由晶体管时代一步一步演化而来，查尔斯巴比其、‘巴丁、杰克.基尔比、泰德.霍夫等人对CPU的诞生做出了巨大贡献。泰德.霍夫认为是制成第一块电脑CPU。
5、关于ASCII，下面哪个说法是正确的：（ B）
A.ASCII码就是键盘上所有键的唯一编码。
B.一个ASCII码使用一个字节的内存空间就能够存放。
C.最新扩展的ASCII编码方案包含了汉字和其他欧洲语言的编码。
D.ASCII码是英国人主持制定并推广使用的。
【解析】
Ａ项：ASCII码和键盘没有对应关系。
B项: ASCII码是用一个字节保存的，八位二进制０～１２７编码
C项:扩展的ASCII码用两个字节，汉字编码不是扩展ASCII的内容
D项: ASCII码是美国标准信息交换码。
6、下列软件中不是计算机操作系统的是： （ Ｄ）
A) Windows B) Linux C) OS/2 D) WPS
【解析】
A项：windows 是微软的操作系统
B项：Linux 是一款开源的操作系统
C项: OS/2是苹果的一款操作系统
D项: WPS 是金山公司的一款文字处理系统，模仿微软的office三件套的
7、关于互联网，下面的说法哪一个是正确的：（ C）
A.新一代互联网使用的IPv6标准是IPv5标准的升级与补充。
B.互联网的入网主机如果有了域名就不再需要IP地址。
C.互联网的基础协议为TCP/IP协议。
D.互联网上所有可下载的软件及数据资源都是可以合法免费使用的。
【解析】
A项:IPV6是IPV4的升级，IPV5是一个实验性的资源预留协议。
B项:域名的存在就是为了解决IP不好记的问题，域名会指向一个具体的IP
C项:主要的基础协议是TCP/IP协议，TCP是传输层的文件传输协议，IP是网络层的网际协议。
D项:互联网上有盗版软件，还有共享软件。
8、关于HTML下面哪种说法是正确的：（ B）
A.HTML实现了文本、图形、声音乃至视频信息的统一编码。
B.HTML全称为超文本标记语言。
C.网上广泛使用的 Flash动画都是由HTML编写的。
D.HTML也是一种高级程序设计语言。
【解析】
A项：文本，图形，声音等都是自己各自不同的编码，没有统一
B项:HTML（HyperText Make-up Lauguage）即超文本标记语言，是构成网页文档的主要语言，
C项:Flash是由软件公司Adobe做的，开始逐步退出历史舞台
D项:HTML是一种标记类语言，脚本类与，不是高级编程语言
9、关于程序设计语言，下面哪个说法是正确的：（C）
A.加了注释的程序一般会比同样的没有加注释的程序运行速度慢。
B.高级语言开发的程序不能使用在低层次的硬件系统如：自控机床或低端手机上。
C.高级语言相对于低级语言更容易实现跨平台的移植。
D.以上说法都不对。
【解析】
A项:注释会在编译的时候被忽略掉，不影响程序运行。
B项:高级开发语言可以在低层次的硬件上运行，只不过是不经常用。
C项:一些高级语言像JAVA等都可以跨平台使用。像.net 诞生之初不能跨平台，但是这几年的.net core 已经可以跨平台了
10、已知大写字母A的ASCII编码为65（10进制），则大写字母J的10进制ASCII编码为：（D）
A.71 B) 72 C) 73 D) 以上都不是
【解析】
Ａ是65，B是66，以此类推，J是74，所以选D
11、十进制小数125.125对应的8进制数是（C）
A) 100.1 B) 175.175 C) 175.1 D) 100.175
【解析】
- 间接法：先把十进制转换成二进制，再把二进制转换成八进制
- 直接法：整数部分：除8取余。小数部分，乘8取余。
125/8=15余5； 15/8=1余7； 1 /8=0余1 ； 整数部分：175（反着）
0.125*8=1.000 小数部分1 （正着）
12、有六个元素FEDCBA 从左至右依次顺序进栈，在进栈过程中会有元素被弹出栈。问下列哪一个不可能是合法的出栈序列？ （C）
A.EDCFAB B) DECABF C) CDFEBA D) BCDAEF
【解析】
A项：F进栈，E进栈，E出栈，D进栈，D出栈，C进栈，C出栈，F出栈，B进栈，A进栈，A出栈，B出栈。
B项：F进栈，E进栈，D进栈，D出栈，E出栈，C进栈，C出栈，B进栈，A进栈，Ａ出栈，Ｂ出栈,F出栈。
C项：F进栈，E进栈，D进栈，C进栈，C出栈，D出栈，此时栈顶是E，F无法先出栈。C错。
D:项：F进栈，E进栈，D进栈，C进栈，B进栈，B出栈，C出栈，D出栈，Ａ进栈，A出栈，E出栈,Ｆ出栈。
13、 表达式a*(b+c)-d的后缀表达式是： （B）
A.abcd*+- B) abc+*d- C) abc*+d- D) -+*abcd
【解析】
中缀表达式转后缀，一共三种方法。①画二叉树 ②堆栈法 ③画括号
主要介绍第二种，规则如下：
（1）如果遇到操作数，我们就直接将其输出。
（2）如果遇到操作符，则我们将其放入到栈中，遇到左括号时我们也将其放入栈中。
（3）如果遇到一个右括号，则将栈元素弹出，将弹出的操作符输出直到遇到左括号为止。注意，左括号只弹出并不输出。
（4）如果遇到任何其他的操作符，如（“+”， “*”，“（”）等，从栈中弹出元素直到遇到发现更低优先级的元素(或者栈为空)为止（即把优先级高的弹出）。弹出完这些元素后，才将遇到的操作符压入到栈中。有一点需要注意，只有在遇到” ) “的情况下我们才弹出” ( “，其他情况我们都不会弹出” ( “。
（5）如果我们读到了输入的末尾，则将栈中所有元素依次弹出。
| 读入字符 | 栈内 | 栈外 | 说明 |
| ａ | 空 | ａ | 操作数，直接输出 |
| ＊ | ＊ | ａ | 操作符，入栈 |
| （ | ＊（ | ａ | 左括号，入栈 |
| ｂ | ＊（ | ａｂ | 操作数，直接输出 |
| ＋ | ＊（＋ | ａｂ | 操作符，入栈 |
| ｃ | ＊（＋ | ａｂｃ | 操作数，直接输出 |
| ） | ＊ | ａｂｃ＋ | 遇到右括号，一直输出直到左括号 |
| － | － | ａｂｃ＋＊ | 操作符，＊号的优先级比－号高，输出优先级高的，把优先级低的入栈 |
| ｄ | － | ａｂｃ＋＊ｄ | 操作数，直接输出 |
| ａｂｃ＋＊ｄ－ | 没有符号，按照顺序把栈内符号输出 |
14、一个包含n个分支结点（非叶结点）的非空二叉树，它的叶结点数目最多为：（D）
A) 2n + 1 B) 2n-1 C) n-1 D) n+1
【解析】
根据二叉树的性质３：对于任何一棵二叉树，如果其叶结点数为N0(N0表示度为0的点也就是叶子结点)，而度为2的结点为N2，则N0=N2+1。
推算过程如下：
已知树的分支结点总数为n，（分支结点就是指度为1或者度为2点），则有N1+N2=N;
将N0=N2+1带入得N1+N0-1=N
移项得：N0=N+1-N1。当N1为0时，N0有最大值为N+1
也可以用特殊值带入求解。
15、快速排序最坏情况下的算法时间复杂度为： （D）
A) O(log2n) B) O(n) C) O(nlog2n) D) O(n2)
【解析】
快排平均时间复杂度O(nlog2n)，最好O(nlog2n)，最坏O(n2)
16. 有一个由4000个整数构成的顺序表，假定表中的元素已经按升序排列，采用二分查找定位一个元素。则最多需要几次比较就能确定是否存在所查找的元素： （B）
A) 11次 B) 12次 C) 13次 D) 14次
【解析】
首先要记住2^10= 1024
2^11-1=2047, 2^12-1=4095 , 2047<4000<4095,所以为12。
17、排序算法是稳定的意思是关键码相同的记录排序前后相对位置不发生改变，下列哪种排序算法是不稳定的：（D）
A) 冒泡排序 B) 插入排序 C) 归并排序 D) 快速排序
【解析】
ABC都是稳定的排序。
A项：冒泡就是把小的元素往前调，比较的是相邻的两个元素，交换也是发生在两个元素之间，即使两个元素相等，也不会进行交换，所以相同元素的前后顺序没有改变，是一种稳定排序的算法。
B项：插入排序是在一个已经有小序列的基础上，一次插入一个元素。碰到相等的元素就把想插入的元素插入到相等元素的后面，所以相同元素的前后顺序没有改变，是一种稳定的排序算法。
C项：归并排序就是把序列有序的分成短序列（最终1个或者2个）。然后把各个有序的短序列合并成有序的长序列。在有1个元素或者2个元素时，1个元素不会交换，2个元素大小相等也可以不交换。短序列合并成长序列过程中，保证两个元素相等时，把处在前面的序列元素保存在结果序列的前面，这样就保证了稳定性。
D项：快排的思想是选定一个基准，比基准小的就往左放，比基准大的就往右放。实际上，在交换a[i]和基准时，很有可能把前面元素的稳定性打乱。例如：5 3 3 4 3 8 9 10 11。如果基准元素5和3交换，就会把元素3的稳定性打乱。所以快速排序是一个不稳定的排序算法。
18、已知n个顶点的有向图，若该图是强连通的（从所有顶点都存在路径到达其他顶点），则该图中最少有多少条有向边？（A）
A) n B) n+1 C) n-1 D) n*(n-1)
【解析】
性质：有n个顶点的有n个顶点的强连通图最多有n（n-1）条边，最少有n条边。
最多的情况：即n个顶点两两相连。
最少的情况：即n个顶点围城一个圈。
19、全国信息学奥林匹克的官方网站为参与信息学竞赛的老师同学们提供相关的信息和资源，请问全国信息学奥林匹克官方网站的网址是：（C）
A) http://www.noi.com/ B) http://www.noi.org/
C) http://www.noi.cn/ D) http://www.xinxixue.com/
【解析】
C项：不做解释。官网。com结尾的一般表示商业公司。org结尾的一般表示教育组织。
20、在参加NOI系列竞赛过程中，下面哪一种行为是 不 被严格禁止的：（B）
A.携带书写工具，手表和不具有通讯功能的电子词典进入赛场。
B.在联机测试中通过手工计算出可能的答案并在程序里直接输出答案来获取分数。
C.通过互联网搜索取得解题思路。
D.在提交的程序中启动多个进程以提高程序的执行效率。
【解析】
A项：比赛中，有时候会允许带书写工具和手表等的。
C项：不会连外网
D项：会造成服务器宕机。
二．问题求解（共2题，每空5分，共计10分）
1．小陈现有2个任务A，B要完成，每个任务分别有若干步骤如下：A=a1->a2->a3，B=b1->b2->b3->b4->b5。在任何时候，小陈只能专心做某个任务的一个步骤。但是如果愿意，他可以在做完手中任务的当前步骤后，切换至另一个任务，从上次此任务第一个未做的步骤继续。每个任务的步骤顺序不能打乱，例如……a2->b2->a3->b3……是合法的，而……a2->b3->a3->b2……是不合法的。小陈从B任务的b1步骤开始做，当恰做完某个任务的某个步骤后，就停工回家吃饭了。当他回来时，只记得自己已经完成了整个任务A，其他的都忘了。试计算小陈饭前已做的可能的任务步骤序列共有 70 种。
【解析】排列组合
A=a1->a2->a3，
B=b1->b2->b3->b4->b5
从b1开始，而且完成了任务A，b1—a1—a2—a3–， 剩余四个空，就是从剩余的空中往里插入元素即可。
方式1：
可以推论，n个物体要放到m个位置上，并满足a[1]<a[2]<a[3]…<a[n],可以推论出，a[1]<a[2]<a[3]<…<a[n]<n+1; 实际上就是在n+m-1个位置中选n个位置。
方式2：
b1在第一个位置，其前方没有任何数，但a1,a2,a3前方可以有数字，就可以理解成，B中的某些任务和a1,a2,a3一共需要占多个空，只要把B中任务挑选位置放好，剩余的自然是A的任务。
所以分类讨论
(1)假设完成任务A：只有1种（顺序选择B剩余任务）
(2)假设完成任务A和b2。则(a1,a2,a3,b2)四种，已知a1,a2,a3顺序不能颠倒，所以用插空法，b2插到a1,a2,
a组成的4个空中，C(4,1)=4种
(3)假设完成任务A和b2,b3。C(5,2)=10种。可以按照方式1，2个物体放到4个位置上，也可也理解，a1,a2,a3,b1,b2一共组成5个位置，从中选出2个位置给b1,b2。剩余的A只有一种方法。
(3)假设完成任务A和b2,b3,b4。 C(6,3)=20种
(4)假设完成任务A和b2,b3,b4,b5。C(7,4)=35种
一共1+4+10+20+35=70种
2．有如下的一段程序：
1. a=1;
2. b=a;
3. d=-a;
4. e=a+d;
5. c=2*d;
6. f=b+e-d;
7. g=a*f+c;
现在要把这段程序分配到若干台（数量充足）用电缆连接的PC上做并行执行。每台PC执行其中的某几个语句，并可随时通过电缆与其他PC通讯，交换一些中间结果。假设每台PC每单位时间可以执行一个语句，且通讯花费的时间不计。则这段程序最快可以在 5 单位时间内执行完毕。注意：任意中间结果只有在某台PC上已经得到，才可以被其他PC引用。例如若语句4和6被分别分配到两台PC上执行，则因为语句6需要引用语句4的计算结果，语句6必须在语句4之后执行。
【解析】
需要画图，注意引用顺序。
| a=1 | ||||
| b=a | ||||
| d=-a | ||||
| e=a+d | ||||
| c=2+d | ||||
| f=b+e-d | ||||
| g=a*f+c | ||||
例如，b的执行需要a，则至少需要1个单位时间；因为要做并行执行所以b和d可以同步完成，e的执行需要a,在第一步已经有值，不需要耗费时间，只需要计算d到e的时间。
三．阅读程序写结果（共4题，每题8分，共计32分）
1．
#include <iostream>
using namespace std;
int a,b;
int work(int a,int b){
if (a%b)
return work(b,a%b);
return b;
}
int main(){
cin >> a >> b;
cout << work(a,b) << endl;
return 0;
}
输入：20 12
输出：___4____
【解析】简单的函数递归调用。
if(),括号中表示条件表达式，如果条件表达式成立就执行下面的语句，也就是括号中不为零就继续。如果a对b取余的结果不为0，那么就返回(b,a%b)。否则返回b
传入20，12后，20%12=8，return(12,8)
传入12，8后，12%8=4，return(8,4)
传入8，4后，12%4=0，结果为0，return b;
2．
#include <iostream>
using namespace std;
int main()
{
int a[3],b[3];
int i,j,tmp;
for (i=0;i<3;i++)
cin >> b[i];
for (i=0;i<3;i++)
{
a[i]=0;
for (j=0;j<=i;j++)
{
a[i]+=b[j];
b[a[i]%3]+=a[j];
}
}
tmp=1;
for (i=0;i<3;i++)
{
a[i]%=10;
b[i]%=10;
tmp*=a[i]+b[i];
}
cout << tmp << endl;
return 0;
}
输入：2 3 5
输出：__416__
【解析】数组加循环
b[a[i]%3] 这个要记住数组的只是，不论怎样中括号中是个数字，表示数组的下标，先计算最里面括号中的。
过程如下：
b[0]=2,b[1]=3,b[2]=5
| b[j] | a[i]+=b[j]; | a[j] | a[i]%3 | b[a[i]%3]+=a[j]; | ||
| i=0 | j=0 | 2 | 2 | 2 | 2 | b[2]=5+2=7 |
| i=1 | j=0 | 2 | 2 | 2 | 2 | b[2]=7+2=9 |
| | j=1 | 3 | 5 | 5 | 2 | b[2]=9+5=14 |
| i=2 | j=0 | 2 | 2 | 2 | 2 | b[2]=14+2=16 |
| | j=1 | 3 | 5 | 5 | 2 | b[2]=16+5=21 |
| | j=2 | 21 | 26 | 26 | 2 | b[2]=21+26=47 |
第二个for循环
| a[i] | a[i]%10 | b[i] | b[i]%10 | a[i]+b[i] | tmp*=a[i]+b[i] | |
| i=0 | 2 | 2 | 2 | 2 | 4 | 4 |
| i=1 | 5 | 5 | 3 | 3 | 8 | 32 |
| i=2 | 26 | 6 | 47 | 7 | 13 | 416 |
3．
#include <iostream>
using namespace std;
const int c=2009;
int main()
{
int n,p,s,i,j,t;
cin >> n >> p;
s=0;t=1;
for(i=1;i<=n;i++)
{
t=t*p%c;
for(j=1;j<=i;j++)
s=(s+t)%c;
}
cout << s << endl;
return 0;
}
输入：11 2
输出： 782
【解析】
| i | t | j | s |
| 1 | 2 | 1 | 2 |
| 2 | 4 | 1 | 6 |
| | | 2 | 10 |
| 3 | 8 | 1 | 18 |
| | | 2 | 26 |
| | | 3 | 34 |
| 4 | 16 | 1 | 50 |
| | | 2 | 66 |
| | | 3 | 82 |
| | | 4 | 98 |
| 5 | 32 | 1 | 130 |
| | | 2 | 162 |
| | | 3 | 194 |
| | | 4 | 226 |
| | | 5 | 258 |
| 6 | 64 | 1 | 322 |
| | | 2 | 386 |
| | | 3 | 450 |
| | | 4 | 514 |
| | | 5 | 578 |
| | | 6 | 642 |
| 7 | 128 | 1 | 770 |
| | | 2 | 898 |
| | | 3 | 1026 |
| | | 4 | 1154 |
| | | 5 | 1282 |
| | | 6 | 1410 |
| | | 7 | 1538 |
| 8 | 256 | 1 | 1794 |
| | | 2 | 41 |
| | | 3 | 297 |
| | | 4 | 553 |
| | | 5 | 809 |
| | | 6 | 1065 |
| | | 7 | 1321 |
| | | 8 | 1577 |
| 9 | 512 | 1 | 80 |
| | | 2 | 592 |
| | | 3 | 1104 |
| | | 4 | 1616 |
| | | 5 | 119 |
| | | 6 | 631 |
| | | 7 | 1143 |
| | | 8 | 1655 |
| | | 9 | 158 |
| 10 | 1024 | 1 | 1182 |
| | | 2 | 197 |
| | | 3 | 1221 |
| | | 4 | 236 |
| | | 5 | 1260 |
| | | 6 | 275 |
| | | 7 | 1299 |
| | | 8 | 314 |
| | | 9 | 1338 |
| | | 10 | 353 |
| 11 | 39 | 1 | 392 |
| | | 2 | 431 |
| | | 3 | 470 |
| | | 4 | 509 |
| | | 5 | 548 |
| | | 6 | 587 |
| | | 7 | 626 |
| | | 8 | 665 |
| | | 9 | 704 |
| | | 10 | 743 |
| | | 11 | 782 |
可以看出s变化的值每次都是加上t的值。这期间不论s和t谁大于2009，就要变小
4．
#include <iostream>
using namespace std;
const int maxn=50;
void getnext(char str[])
{
int l=strlen(str),i,j,k,temp;
k=l-2;
while(k>=0&&str[k]>str[k+1]) k--;
i=k+1;
while(i<l&&str[i]>str[k]) i++;
temp=str[k];
str[k]=str[i-1];
str[i-1]=temp;
for(i=l-1;i>k;i--)
for(j=k+1;j<i;j++)
if(str[j]>str[j+1])
{
temp=str[j];
str[j]=str[j+1];
str[j+1]=temp;
}
return ;
}
int main()
{
char a[maxn];
int n;
cin >> a >> n;
while(n>0)
{
getnext(a);
n--;
}
cout << a << endl;
return 0;
}
输入：NOIP 3
输出： NPOI
【解析】
变化过程如下（按执行顺序）：
| n | a | k | str[k] | str[k+1] | i | str[k] | str[k+1] | a输出 |
| 3 | NOIP | 2 | I | O | 3 | P | I | NOPI |
| 2 | NOPI | 2 | P | O | 2 | P | O | NPIO |
| 1 | NPOI | 2 | I | P | 3 | O | I | NPOI |
实际上就是每次传入四个字母，按照要求把字母进行位置调换。
四．完善程序 (前8空，每空3分，后2空，每空2分，共28分)
1.（最大连续子段和）给出一个数列（元素个数不多于100），数列元素均为负整数、正整数、0。请找出数列中的一个连续子数列，使得这个子数列中包含的所有元素之和最大，在和最大的前提下还要求该子数列包含的元素个数最多，并输出这个最大和以及该连续子数列中元素的个数。例如数列为4，-5，3，2，4时，输出9和3；数列为1 2 3 -5 0 7 8时，输出16和7。
#include <iostream>
using namespace std;
int a[101];
int n,i,ans,len,tmp,beg;
int main() {
cin >> n;
for (i=1; i<=n; i++)
cin >> a[i]; //4,-5,3,2,4
tmp=0;
ans=0; //结果
len=0; //长
beg= ① ;
for (i=1; i<=n; i++) {
if (tmp+a[i]>ans) { //
ans=tmp+a[i]; //很明显，ans是用来存储一段最大的和
len=i-beg;
}
else if ( ② && i-beg>len)
len=i-beg
if (tmp+a[i] ③ ) {
beg= ④ ;
tmp=0;
}
else
⑤ ;
}
cout << ans << ” ” << len << endl;
return 0;
}
【整体思路】
选择一个新数，如果比原来大，那么就赋值给最大值，如果和原来一样，原值保留。如果加起来后比原来还小，则抛弃掉此值，同时把 “前面数的和“ 还有 “个数“ 全部重置（和重置为0，个数变为当前的i），其余情况保留当前值即可。
【①】 0 ； 很明显，变量初始化，赋值为0，送分题
【②】 tmp+a[i]==ans 或者 a[i]+tmp==ans 或者ans==a[i]+tmp ； 已知ans初值为0，根据上个if的条件，判断的是tmp+a[i]和tmp的大于关系
那么此空判断的应该是tmp+a[i]和tmp的等于关系。
【③】 <0 ; 上面的填完了大于和等于的情况，这里应该填小于的情况，但是不能填ans。因为ans有赋值，这里的意思就是如果出现了负数，
【④】 i； 下方tmp重置为0，所以beg这个时候也是重置，但是重置为i
【⑤】tmp+=a[i] 或者 tmp=temp+a[i] ； 其余情况把a[i]累加到tmp中，让tmp在循环中起作用
2. (国王放置) 在n*m的棋盘上放置k个国王，要求k个国王互相不攻击，有多少种不同的放置方法。假设国王放置在第(x,y)格，国王的攻击的区域是:(x-1,y-1), (x-1,y),(x-1,y+1),(x,y-1),(x,y+1),(x+1,y-1),(x+1,y),(x+1,y+1)。读入三个数n,m,k，输出答案。题目利用回溯法求解。棋盘行标号为0~n-1，列标号为0~m-1。
【整体思路】
跟八皇后类型类似，递归回溯。
递归回溯法两种结构：
结构1： int Search(int k)
{
for (i=1; i<=算符种数; i++)
if (满足条件) {
保存结果
if (到目的地) 输出解;
else Search(k+1);
恢复：保存结果之前的状态 {回溯一步 }
}
}
结构2： int Search(int k) {
if (到目的地) 输出解;
else
for (i=1; i<=算符种数; i++)
if (满足条件)
{
保存结果;
Search(k+1);
恢复：保存结果之前的状态{回溯一步}
}
}
这个题目采用的结构2的方法，此题需要对递归和回溯法有了解。
| x-1,y-1 | X-1,y | X-1,y+1 | ||
| X,y-1 | X,y | X,y+1 | ||
| X+1,y-1 | X+1,y | x+1,y+1 | ||
#include <iostream>
using namespace std;
int n,m,k,ans;
int hash[5][5]
void work(int x,int y,int tot){ // 函数参数，x和y表示坐标，tot表示国王总数量
int i,j;
if (tot==k){ //如果检测到放完了8个国王，数量加1，递推停止
ans++;
return;
}
do{
while (hash[x][y]){ // 这里的意思是当hash[x][y]不为0的时候继续下面的循环，可以猜想，下面的代码肯定会有让 hash[x][y] 不为0的。
y++;
if (y==m){
x++;
y= ① ;
}
if (x==n)
return;
}
for (i=x-1;i<=x+1;i++) //遍历行的左侧和右侧
if (i>=0&&i<n) //如果没有到边界
for (j=y-1;j<=y+1;j++) //遍历列的上下两侧
if (j>=0&&j<m) //如果没有到边界
② ;
③ ;
//下面的代码是回溯过程
for (i=x-1;i<=x+1;i++)
if (i>=0&&i<n)
for (j=y-1;j<=y+1;j++)
if (j>=0&&j<m)
④ ;
y++;
if (y==m){
x++;
y=0;
}
if (x==n)
return;
}
while (1);
}
int main(){
cin >> n >> m >> k; //n和m表示范围，k表示国王数量
ans=0; //ans 表示多少种方法
memset(hash,0,sizeof(hash));
⑤ ;
cout << ans << endl;
return 0;
}
【①】0；这段while代码实际上是在遍历hash数组，y到了m后，x增加1，同时y重置为0，下面的x如果到头了，直接返回。
【②】 hash[i][j]++ 或者 hash[i][j] = hash[i][j]+1 或者++ hash[i][j] ； 上面的嵌套for循环实际上在标记某个点的八个方向，把这个点进行加1操作，这样下次遍历的时候就可以认为这个已经访问过了，从而访问别的点。
【③】work(x,y,tot+1) ； 上面表示放置了一个国王，所以这个地方开始放置下一个国王，递推做法，开始放置下一个国王。
【④】hash[i][j]– 或者 hash[i][j] = hash[i][j]-1 或者– hash[i][j] ； 【解析】后退一步，所以hash[i][j]– 。也可以看出下方的代码和上面的部分代码一致，表示回溯一步之后的下一个点看其是否符号条件。
【⑤】work(0,0,0) ；主函数内，初始化之后，是函数的调用，而且本文定义了一个函数，从来没用过，这个地方是函数调用。根据后面函数参数猜想，这个地方应该是x和y坐标，还有国王的数量。
返回目录：NOIP/CSP信息学奥赛初赛