下载文档原格式
信息学竞赛初赛试题及答案一、选择题（每题2分，共10题）1. 在计算机科学中，以下哪个选项不是数据结构？A. 数组B. 链表C. 函数D. 栈答案：C2. 以下哪种排序算法的时间复杂度为O(n^2)？A. 快速排序B. 归并排序C. 插入排序D. 冒泡排序答案：D3. 在计算机网络中，TCP/IP协议栈的第四层是什么？A. 应用层B. 传输层C. 网络层D. 数据链路层答案：B4. 下列哪种编程语言不是面向对象的？A. JavaB. C++C. PythonD. C答案：D5. 在关系型数据库中，用于创建新表的SQL语句是？A. SELECTB. INSERTC. CREATED. DROP答案：C6. 在HTML中，用于定义文档标题的标签是？A. <h1>B. <title>C. <header>D. <head>答案：B7. 在Python中，以下哪个关键字用于定义一个函数？A. defB. ifC. forD. while答案：A8. 在操作系统中，用于管理内存的机制是？A. 进程B. 线程C. 分页D. 虚拟内存答案：D9. 在计算机系统中，以下哪个选项不是操作系统的功能？A. 进程管理B. 设备驱动C. 网络通信D. 数据加密答案：D10. 在计算机视觉中，用于识别图像中物体的算法是？A. 卷积神经网络B. 决策树C. 支持向量机D. 随机森林答案：A二、填空题（每题2分，共5题）1. 在计算机科学中，算法的时间复杂度是指算法执行时间与输入数据量之间的关系，通常用大O符号表示，例如O(1)表示______。
答案：常数时间复杂度2. 在编程中，______是一种将数据结构和操作这些数据的方法封装在一起的编程范式。
答案：面向对象编程3. 在网络协议中，HTTP协议默认使用的端口号是______。
答案：804. 在数据库设计中，______是一种用于确保数据完整性和避免数据冗余的策略。
信息竞赛试题及答案1. 题目：请简述什么是二进制数。
答案：二进制数是一种用0和1表示的数制，它在计算机科学中被广泛使用，因为计算机内部的逻辑电路只能表示两种状态：开（1）和关（0）。
2. 题目：在HTML中，如何创建一个无序列表？答案：在HTML中，可以使用`<ul>`标签来创建一个无序列表，列表项则使用`<li>`标签表示。
3. 题目：请解释什么是算法的时间复杂度。
答案：算法的时间复杂度是指算法执行时间随输入数据规模增长的变化趋势。
它用来描述算法在最坏情况下的运行时间。
4. 题目：在Python中，如何实现一个函数，该函数接受一个字符串列表作为参数，并返回一个新列表，其中包含原列表中每个字符串的第一个字符？答案：可以通过列表推导式实现，代码如下：```pythondef first_char_of_each(words):return [word[0] for word in words if word]```5. 题目：请解释什么是数据库事务的ACID属性。
答案：ACID属性是数据库事务的四个基本特性，包括原子性（Atomicity）、一致性（Consistency）、隔离性（Isolation）和持久性（Durability）。
原子性保证事务要么完全执行，要么完全不执行；一致性确保事务执行后，数据保持一致状态；隔离性保证并发执行的事务之间不会互相干扰；持久性确保一旦事务提交，其结果就是永久性的。
6. 题目：在C语言中，如何声明一个指向整型的指针变量？答案：在C语言中，声明一个指向整型的指针变量可以使用以下语法：```cint *ptr;```这里`ptr`是一个指向整型的指针变量。
7. 题目：请解释什么是TCP/IP协议。
答案：TCP/IP协议是一组用于网络通信的协议，其中TCP（传输控制协议）负责确保数据的可靠传输，而IP（互联网协议）负责数据的寻址和路由。
8. 题目：在JavaScript中，如何使用while循环打印出1到10的数字？答案：可以使用以下代码实现：```javascriptlet i = 1;while(i <= 10) {console.log(i);i++;}```9. 题目：请解释什么是区块链技术。
信息学竞赛习题解答5（模拟）《算法与程序实践》习题解答5――模拟现实中的有些问题，难以找到公式或规律来解决，只能按照一定步骤，不停地做下去，最后才能得到答案。
这样的问题，用计算机来解决十分合适，只要能让计算机模拟人在解决此问题的行为即可。
这一类的问题可以称之为“模拟题”。
比如下面经典的约瑟夫问题：CS51：约瑟夫问题（来源： 2746，程序设计导引及在线实践（李文新）例6.1 P141）问题描述：约瑟夫问题：有ｎ只猴子，按顺时针方向围成一圈选大王（编号从１到ｎ），从第１号开始报数，一直数到ｍ，数到ｍ的猴子退出圈外，剩下的猴子再接着从1 开始报数。
就这样，直到圈内只剩下一只猴子时，这个猴子就是猴王，编程求输入ｎ，ｍ后，输出最后猴王的编号。
输入：每行是用空格分开的两个整数，第一个是 n，第二个是m ( 0 < m, n < 300) 。
最后一行是：0 0 输出：对于每行输入数据（最后一行除外)，输出数据也是一行，即最后猴王的编号。
样例输入： 6 2 12 4 8 3 0 0样例输出：5 1 7解题思路：初一看，很可能想把这道题目当作数学题来做，即认为结果也许会是以n和m为自变量的某个函数f(n,m)，只要发现这个函数，问题就迎刃而解。
实际上，这样的函数很难找，甚至也许根本就不存在。
用人工解决的办法就是将n个数写在纸上排成一圈，然后从1开始数，每数到第m个就划掉一个数，一遍遍做下去，直到剩下最后一个。
有了计算机，这项工作做起来就会快多了，我们只要编写一个程序，模拟人工操作的过程就可以了。
用数组anLoop来存放n个数，相当于n个数排成的圈；用整型变量 nPtr指向当前数到的数组元素，相当于人的手指；划掉一个数的操作，就用将一个数组元素置0的方法来实现。
人工数的时候，要跳过已经被划掉的数，那么程序执行的时候，就要跳过为0的数组元素。
需要注意的是，当nPtr指向anLoop中最后一个元素（下标n-1）时，再数下一个，则nPtr要指回到数组的头一个元素（下标0），这样anLoop才象一个圈。
求int的上限与下限#include <stdio.h>//运行时间长,请等待.int main(){int min ,max;FILE *fin,*fout;fin=fopen("min of int.out","wb");fout=fopen("max of int.out","wb");for(min=-1;min<0;){min-- ;}fprintf(fin,"%d\n",min+1);for(max=1;max>0;){max++ ;}fprintf(fout,"%d\n",max-1);fclose(fin);fclose(fout);return 0;}1-1#include <stdio.h>int main(){int a,b,c;scanf("%d%d%d",&a,&b,&c);double average;average=(a+b+c)/3.0; //一定要将int型转为浮点型printf("Average=%.3lf",average );system("pause");return 0;}1-2#include <stdio.h>int main(){double f,c;printf("请输入华氏温度f\n");scanf("%lf",&f);c=(f-32)*5/9 ;printf("摄氏温度c=%.3lf\n",c);return 0;}1-3#include <stdio.h>int main(){int n;scanf("%d",&n);printf("%d\n",(1+n)*n/2) ;system("pause");return 0;}1-4#include <stdio.h>#include <math.h>int main(){const double pi =4.0*atan(1.0);int n;scanf("%d",&n);while(n>=360){printf("请输入小于360°的角\n");scanf("%d",&n);}printf("正弦:%lf\n余弦:%lf",sin(n*pi/180),cos(n*pi/180));system("pause");return 0;}1-5#include <stdio.h>#include <math.h>int main(){double x1,y1,x2,y2;printf("请输入点A的坐标\n");scanf("%lf%lf",&x1,&y1);printf("请输入点B的坐标\n");scanf("%lf%lf",&x2,&y2);double d;d=sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));printf("%.3lf\n",d);return 0;}1-6#include <stdio.h>int main(){int a;scanf("%d",&a);if(a%2==0)printf("该数是偶数");else printf("该数非偶数");system("pause");return 0;}1-7#include <stdio.h>int main(){const int a=95;int n;printf("你要买多少件衣服\n");scanf("%d",&n);if(a*n>=300)printf("需要%.2lf元\n",a*n*0.85);else printf("需要%.2lf元\n",(double)a*n); //由于输出是小数%.2lf,故一定要将int型转化为浮点型system("pause");return 0;}1-8#include <stdio.h>#include <stdio.h>int main(){double a;scanf("%lf",&a);if(a>0)printf("%.2lf",a);else printf("%.2lf",-a);system("pause");return 0;}1-9(方法一)#include <stdio.h>int main(){int a,b,c,max,min,middle;scanf("%d%d%d",&a,&b,&c);while(a<0||b<0||c<0){printf("三边必须都是大于零的正整数");scanf("%d%d%d",&a,&b,&c);}min=a;if(a>b)min=b;if(a>c)min=c;max=a;if(a<b)max=b;if(a<c)max=c;middle=a+b+c-min-max;if(min+middle>max)printf("yes");else printf("no");system("pause");return 0;}1-9(方法二) #include <stdio.h>int main(){int a,b,c,t=0;scanf("%d%d%d",&a,&b,&c);while(a<0||b<0||c<0){printf("三边必须都是大于零的正整数");scanf("%d%d%d",&a,&b,&c);}if(a>b){t=a;a=b;b=t;}if(a>c){t=a;a=c;c=t;}if(b>c){t=b;b=c;c=t;}if(a+b>c)printf("yes");else printf("no");system("pause");return 0;}1-10#include <stdio.h>int main(){int n;scanf("%d",&n);if(n%4==0){if(n%100==0){if(n%400==0){printf("yes");}else printf("no");}else printf("yes");}else printf("no");system("pause");return 0;}3n+1解决篇1#include <stdio.h>int main(){int count=0;double i,m;scanf("%lf",&i);for(;i>1;){m=i/2;if(floor(m+0.5)!=m){i=3*i+1;i/=2;count+=2;}//floor(x)取x的整数部分.else {i/=2;count++;}}printf("%d\n",count);system("pause");return 0;}3n+1解决篇2#include<stdio.h>int main(){long long n, count = 0;//long long 的取值范围:-2^63~2^63-1scanf("%I64d", &n);while(n > 1) {if(n % 2 == 1) n = n*3+1;else n /= 2;count++;}printf("%I64d\n", count);return 0;}数据统计解决篇#include <stdio.h>int main(){int x,n=0,s=0,min,max;while(scanf("%d",&x)==1){if(n==0){min=max=x;}//读取第一个数的时候将第一个数赋值给min和max s+=x;if(x<min)min=x;if(x>max)max=x;n++;}printf("%d %d %.3lf\n",min,max,(double)s/n);system("pause");return 0;}2-1(fin)#include <stdio.h>int main(){FILE *fin,*fout;fin=fopen("digit.in","rb");fout=fopen("digit.out","wb");/*fin=stdin;fout=stdout;*/int a,i=0;fscanf(fin,"%d",&a);while(1){a/=10;i++;if(a<1)break;}fprintf(fout,"%d\r\n",i);fclose(fin);fclose(fout);//system("pause");return 0;}2-1(freopen)#include <stdio.h>//#define LOCAL//在编译选项中定义LOCALint main(){#ifdef LOCALfreopen("digit.in","r",stdin);freopen("digit.out","w",stdout);#endifint a,i=0;scanf("%d",&a);while(1){a/=10;i++;if(a<1)break;}printf("%d\n",i);return 0;}2-2(freopen)#include <stdio.h>//#define LOCAL//编译选项中定义int main(){#ifdef LOCALfreopen("daffodil.out","w",stdout);#endifint a,b,c,m;for(a=1;a<=9;a++){for(b=0;b<=9;b++){for (c=0;c<=9;c++){m=a*100+b*10+c;if(m==a*a*a+b*b*b+c*c*c)printf("%d\n",m);}}}//system("pause");return 0;}2-2(fin)#include <stdio.h>int main(){FILE *fout;fout=fopen("daffodil.out","wb");int a,b,c,m;for(a=1;a<=9;a++){for(b=0;b<=9;b++){for(c=0;c<=9;c++){m=a*a*a+b*b*b+c*c*c;if(m==a*100+b*10+c)fprintf(fout,"%d\r\n",m);}}}fclose(fout);return 0;}2-3(fin)#include<stdio.h>int main(){FILE *fin,*fout;fin=fopen("hanxin.in","rb");fout=fopen("hanxin.out","wb");//fin=stdin;//fout=stdout;int a,b,c,x,temp=0;//temp用来判断是否在10到100内存在这样的数fscanf(fin,"%d%d%d",&a,&b,&c);for(x=10;x<=100;x++){if(x%3==a&&x%5==b&&x%7==c){fprintf(fout,"%d\r\n",x);temp=1;break;}}if(!temp)fprintf(fout,"No answer\r\n");fclose(fin);fclose(fout);return 0;}2-3(freopen)#include<stdio.h>{//会在编译选项中定义LOCAL#ifdef LOCALfreopen("hanxin.in","r",stdin);freopen("hanxin.out","w",stdout);#endifint a,b,c,x,temp=0;scanf("%d%d%d",&a,&b,&c);for(x=10;x<=100;x++){if(x%3==a&&x%5==b&&x%7==c){printf("%d\n",x);temp=1;break;}}if(!temp)printf("No answer\n");return 0;}2-4(fin)#include<stdio.h>int main(){FILE *fin,*fout;fin=fopen("triangle.in","rb");fout=fopen("triangle.out","wb");//fin=stdin;//fout=stdout;int n,i,j,k;fscanf(fin,"%d\r\n",&n);for(i=1;i<=n;i++){for(j=1;j<i;j++)fprintf(fout," ");for(k=-2*i+2*n+1;k>=1;k--)fprintf(fout,"*");fprintf(fout,"\r\n");}fclose(fin);fclose(fout);return 0;}2-4(freopen)#include<stdio.h>{//在编译选项内定义LOCAL#ifdef LOCALfreopen("triangle.in","r",stdin);freopen("triangle.out","w",stdout);#endifint n,i,j,k;scanf("%d",&n);for(i=1;i<=n;i++){for(j=1;j<i;j++)printf(" ");for(k=2*n+1-2*i;k>=1;k--)printf("*");printf("\n");}return 0;}2-5(fin)#include<stdio.h>int main(){FILE *fin,*fout;fin=fopen("stat.in","rb");int n,a,i,m,count=0;fscanf(fin,"%d",&n);for(i=1;i<=n+1;i++){fscanf(fin,"%d",&a);if(i==n+1)m=a;}fclose(fin);fin=fopen("stat.in","rb");for(i=0;i<=n;i++){fscanf(fin,"%d",&a);if(i!=0){if(a<m)count++;}}fclose(fin);fout=fopen("stat.out","wb");fprintf(fout,"%d\r\n",count);fclose(fout);return 0;}2-5(freopen) #include<stdio.h>int main(){freopen("stat.in","r",stdin);freopen("stat.out","w",stdout);int n,a,i,m,count=0;scanf("%d",&n);for(i=1;i<=n+1;i++){scanf("%d",&a);if(i==n+1)m=a;}freopen("stat.in","r",stdin);for(i=0;i<=n;i++){scanf("%d",&a);if(i!=0){if(a<m)count++;}}printf("%d\n",count);return 0;}2-6(fin) #include<stdio.h>int main(){FILE *fin,*fout;fin=fopen("harmony.in","rb");int n,i;double H=0;fscanf(fin,"%d",&n);for(i=1;i<=n;i++){H+=(double)1/i;}fclose(fin);fout=fopen("harmony.out","wb");fprintf(fout,"%.3lf\r\n",H);fclose(fout);return 0;}2-6(freopen) #include<stdio.h>int main(){#ifdef LOCALfreopen("harmony.in","r",stdin);freopen("harmony.out","w",stdout);#endifint n,i;double H=0;scanf("%d",&n);for(i=1;i<=n;i++){H=H+double/i;}printf("%.3lf",H);return 0;}2-7(fin) #include<stdio.h>int main(){FILE *fout;int i;double H=0;for(i=1;2*i-1<1000000;i++){if(i%2==1)H+=(double)1/(2*i-1);else H-=(double)1/(2*i-1);}fout=fopen("approximation.out","wb");fprintf(fout,"%lf\r\n",H);return 0;}2-7(freopen) #include<stdio.h>int main(){#ifdef LOCALfreopen("approximation.in","r",stdin);freopen("approximation.out","w",stdout);#endifint i;double H=0;for(i=1;2*i-1<1000000;i++){if(i%2==1)H+=(double)1/(2*i-1);else H-=(double)1/(2*i-1);}printf("%lf",H);return 0;}2-8(fin,double)#include<stdio.h>#include<time.h>int main(){FILE *fin,*fout;fin=fopen("subsequence.in","rb");fout=fopen("subsequence.out","wb");int n,m,i;double H=0;double ii;fscanf(fin,"%d%d",&n,&m);for(i=n;i<=m;i++){ii=(double)i*i;H+=1/ii;}fprintf(fout,"%.5lf\r\n",H);fprintf(fout,"%.2lf\r\n",(double)clock()/CLOCKS_PER_SEC);//比较double和long long运行效率fclose(fin);fclose(fout);return 0;}2-8(fin,long long)#include<stdio.h>#include<time.h>int main(){FILE *fin,*fout;fin=fopen("subsequence.in","rb");fout=fopen("subsequence.out","wb");int n,m,i;double H=0;fscanf(fin,"%d%d",&n,&m);for(i=n;i<=m;i++){long long ii=1;//定义ii=ii*i*i; //不用ii=i*i也不是ii*=i*i,这样做是为了防止i*i溢出; 可以认为这一步将int型转化为long long 型H+=1/(double)ii;//不是(double)1/ii}fprintf(fout,"%.5lf\r\n",H);fprintf(fout,"%.2lf\r\n",(double)clock()/CLOCKS_PER_SEC); ////比较double和long long运行效率fclose(fin);fclose(fout);return 0;}2-8(freopen)#include<stdio.h>#define LOCALint main(){#ifdef LOCALfreopen("subsequence.in","r",stdin);freopen("subsequence.out","w",stdout);#endifint n,m,i;double H=0,ii;scanf("%d%d",&n,&m);for(i=n;i<=m;i++){H+=1/((double)i*i);}printf("%.5lf\n",H);return 0;}2-9(fin)#include<stdio.h>int main(){FILE *fin,*fout;fin=fopen("decimal.in","rb");fout=fopen("decimal.out","wb");int a,b,c;fscanf(fin,"%d%d%d",&a,&b,&c);fprintf(fout,"%.*lf\r\n",c,(double)a/b);fclose(fin);fclose(fout);return 0;}2-9(freopen)#include<stdio.h>int main(){#ifdef LOCALfreopen("decimal.in","r",stdin);freopen("decimal.out","w",stdout);#endifint a,b,c;scanf("%d%d%d",&a,&b,&c);printf("%.*lf",c,(double)a/b);return 0;}2-10(全书看完再看这段代码) #include<cstdio>#include<algorithm>using namespace std;int main(){freopen("permutation.ans","w",stdout);int d[]={1,2,3,4,5,6,7,8,9};do{int a=d[0]*100+d[1]*10+d[2];int b=d[3]*100+d[4]*10+d[5];int c=d[6]*100+d[7]*10+d[8];if(c==3*a&&b==2*a)printf("%d %d %d\n",a,b,c);}while(next_permutation(d,d+9));return 0;}。
编程算法竞赛试题答案编程算法竞赛是一项旨在测试参赛者编程能力和算法理解的竞赛活动。
试题通常包括编程问题、算法设计问题以及数据结构的应用。
以下是一套编程算法竞赛试题的答案示例。
# 问题一：二分查找算法实现问题描述：给定一个升序排列的整数数组 `nums`，以及一个目标值 `target`，如果 `nums` 中存在这个目标值，则返回它的索引；否则返回 `-1`。
算法分析：二分查找是一种在有序数组中查找特定元素的算法。
其基本思想是将目标值与数组中间的元素进行比较，如果目标值等于中间元素，则查找成功；如果目标值小于中间元素，则在数组左半部分继续查找；如果目标值大于中间元素，则在右半部分继续查找。
这个过程将不断重复，直到找到目标值或搜索范围为空。
代码实现：```pythondef binary_search(nums, target):left, right = 0, len(nums) - 1while left <= right:mid = (left + right) // 2if nums[mid] == target:return midelif nums[mid] < target:left = mid + 1else:right = mid - 1return -1```# 问题二：最长公共前缀问题描述：编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀，返回空字符串 `""`。
算法分析：最长公共前缀问题可以通过纵向扫描解决。
首先比较第一个字符串与数组中其他所有字符串的对应位置字符是否相同，然后逐步向左移动，直到找到不匹配的位置。
代码实现：```pythondef longest_common_prefix(strs):if not strs:return ""shortest_str = min(strs, key=len)for i, char in enumerate(shortest_str):for other in strs:if other[i] != char:return shortest_str[:i]return shortest_str```# 问题三：合并K个排序链表问题描述：合并 `k` 个排序链表，返回合并后的排序链表。
信息学竞赛试题题一：编程题给定一个字符串s，求字符串中最长连续重复子串的长度。
输入格式:一行一个字符串s，只包含小写字母，长度不超过100000。
输出格式:一个整数，表示最长连续重复子串的长度。
示例输入：abbbbbccccc示例输出：5题目解析及思路：对于该问题，我们可以使用双指针的方法进行求解。
定义两个指针start和end，start指向当前连续重复子串的起始位置，end指向当前子串的末尾位置，初始化时start和end都指向字符串s的第一个字符。
然后我们不断向右移动end指针，直到当前连续重复子串中出现一个不同的字符，此时我们就找到了一个连续重复子串。
然后我们更新当前子串的长度，并将start指针指向end指针的下一个位置，继续向右移动end指针，直到遍历完整个字符串。
具体实现细节如下：#include <iostream>#include <string>using namespace std;int main() {string s;getline(cin, s);int n = s.length();int start = 0, end = 0, ans = 0; // 初始化start和end指针，并设ans 为0while (end < n) { // 当end指针未到达字符串末尾时while (end < n && s[end] == s[start]) { // 移动end指针，直到出现不同的字符end++;}ans = max(ans, end - start); // 更新ans为当前子串的长度start = end; // 更新start指针为end指针的下一个位置}cout << ans << endl; // 输出最长连续重复子串的长度return 0;}时间复杂度分析：在上述算法中，我们对字符串进行了一次线性扫描，每次在内部循环中对end指针进行了O(1)次移动，因此总的时间复杂度为O(n)，其中n为字符串的长度。
1．已知，按中序遍历二叉树的结果为：abc问：有多少种不同形态的二叉树可以得到这一遍历结果，并画出这些二叉树。
2．有2×n的一个长方形方格，用一个1×2的骨牌铺满方格。
例如n=3时，为2×3方格。
此时用一个1×2的骨牌铺满方格，共有3种铺法：试对给出的任意一个n（n>0），求出铺法总数的递推公式。
3．设有一个共有n级的楼梯，某人每步可走1级，也可走2级，也可走3级，用递推公式给出某人从底层开始走完全部楼梯的走法。
例如：当n=3时，共有4种走法，即1+1+1,1+2,2+1,3。
4.在a,b,c,d,e,f六件物品中，按下面的条件能选出的物品是：(1)a,b两样至少有一样(2)a,d不能同时取(3)a,e,f中必须有2样(4)b,c要么都选，要么都不选(5)c,d两样中选一样(6)若d不选，则e也不选5.平面上有三条平行直线，每条直线上分别有7，5，6个点，且不同直线上三个点都不在同一条直线上。
问用这些点为顶点，能组成多少个不同三角形？6.已知一棵二叉树的结点名为大写英文字母，其中序与后序遍历的顺序分别为：CBGEAFHDIJ与CGEBHFJIDA则该二叉树的先序遍历的顺序为：7.平面上有三条平行直线，每条直线上分别有7，5，6个点，且不同直线上三个点都不在同一条直线上。
问用这些点为顶点，能组成多少个不同四边形？8.如下图,有一个无穷大的的栈S,在栈的右边排列着1,2,3,4,5共五个车厢。
其中每个车厢可以向左行走,也可以进入栈S让后面的车厢通过。
现已知第一个到达出口的是3号车厢，请写出所有可能的到达出口的车厢排列总数(不必给出每种排列)。
出口←← 1 2 3 4 5S↓9..将N个红球和M个黄球排成一行。
例如:N=2,M=3可得到以下6种排法:红红黄黄黄红黄红黄黄红黄黄红黄黄红红黄黄黄红黄红黄黄黄黄红红问题:当N=4,M=3时有多少种不同排法?(不用列出每种排法)10．在书架上放有编号为1 ，2 ，．．．，n的n本书。
信息学竞赛中问题求解常见题分析排列组合问题一、知识点：1． 分类计数原理：做一件事情，完成它可以有n 类办法，在第一类办法中有m 1种不同的方法，在第二类办法中有m 2种不同的方法，……，在第n 类办法中有m n 。
种不同的方法，那么完成这件事共有N=m 1+m 2+…+m n 。
种不同的方法。
2． 分步计数原理：做一件事情，完成它需要分成n 个步骤，做第一步有m 1种不同的方法，做第二步有m 2种不同的方法，……，做第n 步有m n 种不同的方法，那么完成这件事有N=m 1*m 2*…m n 。
种不同的方法。
3． 排列的概念：从n 个不同元素中，任取m(m ≤n)个元素(这里的被取元素各不相同)，按照一定的顺序排成一列，叫做从n 个不同元素中取出m 个元素的一个排列。
4． 排列数的定义：从n 个不同元素中，任取m(m ≤n)个元素的所有排列的个数叫做从n 个元素中取出m 个元素的排列数，用符号m n A 表示。
5． 排列数公式：m n A =n(n-1)(n-2)…(n-m+1)(m ，n ∈N ，m ≤n)6． 阶乘：n!表示正整数l 到n 的连乘积，叫做n 的阶乘规定0!=l 。
7． 排列数的另一个计算公式：)!(!m n n A m n -= 8． 组合的概念：一般地，从n 个不同元素中取出m(m ≤n)个元素并成一组，叫做从n 个不同元素中取出m 个元素的一个组合．9． 组合数的概念：从n 个不同元素中取出m(m ≤n)个元素的所有组合的个数，叫做从n 个不同元素中取出m 个元素的组合数．用符号mn C 表示．10． 组合数公式：!)1)...(2)(1(m m n n n n A A C m m m n m n +---==，或)!(!!m n m n C m n -= (n ，m ∈N ，且m ≤n)11． 组合数的性质1：m n n m n C C -=，规定：0n C ：=1； 2：11-++=m n m n m n C C C 。
2.5.1 最公平路从小到大枚举最小边，则最大边不减。
每次用O(m)的时间判连通即可。
的时间判连通即可。
2.5.3 最小圈初始时设置d[i,i]=无穷大，再套用floyd-warshall 算法即可。
算法即可。
2.5.6 路的最小公倍数单独考虑每个素数a ，那么一条路p 的s(p)值中a 的指数就是p 上的权中a 的最小指数，即路的“瓶颈”。
所有s(p)的最小公倍数就是所有路的瓶颈最大值。
的最小公倍数就是所有路的瓶颈最大值。
把把“求和”“求和”操作改成操作改成操作改成“取“取最小值”操作，然后套用dijkstra 即可。
即可。
2.5.7 货币兑换这道题目的本质是判断加权有向图是否有正圈，套用bellman-ford 算法即可。
如果迭代n-1次以后标号仍然会改变，则有正圈。
为了找到正圈，需要记录每个标号变化最后一次是由那个结点引起的。
由那个结点引起的。
2.5.8 速度限制如果每条道路都有限速标志，如果每条道路都有限速标志，那么此问题只是最普通的最短路径。
那么此问题只是最普通的最短路径。
那么此问题只是最普通的最短路径。
基于此，基于此，我们尝试给每条道路标上限速标志。
每条道路标上限速标志。
无标志路径的速度由上一条道路的速度决定；如果上一条道路亦无标志，那么它们的速度又由上两条道路的速度决定；如果上两条道路亦无标志，那么它们的速度又由上三条道路的速度决定……如此向前追溯，直至遇到有标志路径或者起点。
直至遇到有标志路径或者起点。
所以逆向思维，所以逆向思维，我们从每一条有标志路径或者起点出发，在它们的后面接上所有单独的或者一串连续的无标志路径，使之成为一条有限速标志的新路。
之成为一条有限速标志的新路。
这样，此问题就转化为普通最短路径。
这样，此问题就转化为普通最短路径。
这样，此问题就转化为普通最短路径。
当然，如何求出所有当然，如何求出所有单独的或者一串连续的无标志路径可以用O(n 3)的Floyd 算法。
算法。
1.1节习题1.1.1对；不对1.1.2提示：考虑规模增长时的时间开销，可以对比运行时间，也可以在程序中统计基本操作数目1.2节习题1.2.1不一定。
这要看枚举量和枚举时间1.2.3枚举即可。
需要注意的是要保证每个问题只有一个正确答案而不是有个答案。
本题有唯一解cdebeedcba。
1.2.5注意行有很多但是列不太多。
硬币翻两次等于不翻，所以所有行/列最多翻一次。
枚举每列是否翻有2^9=512种情况，此时可以用O(n)的时间计算每行是否翻（注意：列确定以后每行独立）。
1.2.6只需要枚举横坐标相邻的点1.2.7设S1的长度为n。
注意用串匹配来做的话时间复杂度至少为O(10^n)，不是有效算法。
应该枚举S1的“分段方式”。
例如231241，如果分段方式为23|124|1，则124为完整的一段，前面必为123，后面必为125，经检验这是可行的。
因此如果有一个完整段的情况可以用O(n^2)次枚举来判定。
剩下只需要解决没有完整段的情况，即被分成两段。
如2312，如果被分为2|312，则需要枚举位数。
如果是3位，有方程??2 + 1 = 312，无解；如果是4位，有方程???2 + 1 = 312?，有解3122 + 1 = 3123。
基本思想如此，但是需要注意有进位的情况。
建议读者自己写程序并提交到ural在线题库检查自己的程序是否考虑周全。
1.2.12首先可以证明：覆盖整个草坪当且仅当覆盖草坪的上边界。
这样每个圆的作用范围是一条线段，问题转化为用最少的线段覆盖整个区间。
先预处理再贪心，具体方法留给读者思考。
1.2.14本题较难，需要先推出n=4时的两种可能最优策略（用代数方法容易推导出），然后用递归的思想把n>4的情况转化为n<=4的情况加以解决。
提示：考虑四人速度为1,3,4,5和1,2,5,6的情况，最优时间分别为16和13。
1.2.17本题答案不唯一。
例如：解方程组。
1.2.23枚举去掉的数字位置后，几乎就可以直接解方程了（需要分类讨论和少量附加枚举）。
具体方式留给读者思考1.2.24把袋子编号为0,1,2...n-1，如果没有1717克的限制，就是第0,1,2...n-1个袋子依次取豌豆0,1,2...n-1颗，把称得的重量和0+1+2+...+(n-1)比较，重了几克就是第几个袋子是魔法豌豆！可是现在有总重量限制，因此只有当0+1+2+...+n-1<=1717时才能一次称出。
记M(1)为能保证一次称出的最大n值，则解不等式得n<=59。
二次称可以用以下策略：59个袋子为一组，第0组不取，第1组每个取1颗，第2组每个取2颗...只要总重量<=1717，则多了几克就是第几组的。
由于每组只有59个，所以再称一次就可以了。
解不等式可以求出保证二次称出的最大n，记为M(2)。
这样递推出M(10)发现M(10)>10000，因此用我们刚才的策略就可以在10次内称出了。
1.2.27如果某张纸上只有一个程序，则可以在其他顺序恢复后再单独把它插入；如果某张纸上有至少三个程序，则除了头尾之外的中间程序都只会出现一次，也可以最后处理，因此只需要保留恰好有两个程序的纸张。
剩下的工作就不难了，留给读者思考。
1.3节习题1.3.6自上而下的读取各行，可以用本节介绍的floodfill方法来作，但是更节省空间的方法是1.4节介绍的并查集。
需要注意的是要正确的处理新块开始、旧块结束、不同块合并、相同块再次合并（形成“洞”）等几种情况。
1.3.7下确界可以简单的通过求轮廓线的并来实现。
交就没有这么简单了，因为在求轮廓线交以后可能形成非矩形的区域，即出现“凹角”。
先作一次floodfill后删除有三侧属于同一个区域的角，直到不存在这样的角。
1.3.24设电路对应的函数是f(i)，其中i是一个n进制数，n为输入个数。
如果f(000..0)=f(111..1)，则所有x设置为0即可。
否则考虑序列：000..000,000..001,000..011,000...111, ... 011..1, 111..1，每相邻两项只相差一个字符。
显然一定存在相邻两项的f值不同，不同的字符保留为x，其他设置为相同值即可。
可以二分查找，总时间复杂度为O(mlogn)，m为门的数目。
1.4节习题1.4.1先作标记，等到浪费空间大于一半时重构树。
可以证明均摊时间复杂度不变。
另外还有保持每个操作最坏情况时间复杂度不变的算法，非常巧妙。
1.4.7设s[0]=0，s[i]=a[1]+a[2]+...+a[i]，则信息i j even等价于a[i]+...+a[j]为偶数，即s[j]-s[i-1]为偶数，即s[j]与s[i-1]同奇偶。
这样，每条信息都可以变为某两个s[i]和s[j]是否同奇偶的信息。
记same[i]为当前和s[i]同奇偶的s[j]集合，diff[i]为当前和s[i]不同奇偶的s[j]集合，则一条信息i j even将导致same[j]和same[i-1]合并，diff[j]和diff[i-1]合并；信息i j odd将导致same[j]和diff[i-1]合并；diff[j]和same[i-1]合并。
具体细节留给读者思考。
1.4.12和标准的Young Tableau查找算法很类似，稍微修改一下即可。
1.4.16先按照x坐标排序，然后建立一棵静态的BST用于统计。
需要记录附加信息。
建议读者写写程序，要写得尽量简单，很少几行即可写完。
1.5节习题1.5.8先作减法，把两个权变成一个。
可以进一步发现如果矩形有重叠，可以把重叠部分去掉和权和保持不变。
这样问题变成了即找出k个不重叠的矩形使得权和最大。
们用区域(i,j)来表示在矩阵W中的“第一行第i个格子右边所有元素加上第二行第j个格子右边的所有元素”这个区域，用d[s,i,j]来表示在这个区域中选择s 个子矩阵，它们的元素总和的最小值。
看作多阶段决策问题，则决策有五种：决策一：第一行第i个格子不用的情况，这种决策转移到状态d[s,i+1,j]；决策二：第二行第j个格子不用的情况，这种决策转移到状态d[s,i,j+1]；决策三：第一行从第i个格子放一个矩形，则大小L有O(n)种选择；转移到d[s,i+L,j]决策四：第二行从第j个格子放一个矩形，则大小L有O(n)种选择；转移到d[s,i,j+L]决策五：两行一起放宽度为2的矩形，也有O(n)种选择。
1.5.10如果是求利益最大的方案，显然可以定义状态d[i]为考虑前i个订单并接受订单i的最大利润。
但是第k的方案呢？这种状态表示是不行的。
它的一个重要问题在于：问题不具备最优子结构！第k大方案所对应的决策的子决策不一定是第k大的。
无奈之下，我们只好增加一维状态参量，用d[i,j]表示考虑前i个订单并介绍订单i的第j大利润，而状态转移时也必须考虑所有前趋状态各自的第1,2,3…j大利润（想一想，为什么不考虑第j+1,j+2…k大利润？），然后加以比较。
需要注意的是可以利用堆来降低时间复杂度，请读者思考。
1.5.11注意到命令序列长度不超过50，机器人不可能走得太远。
所以可以先枚举终止位置，然后单独考虑每个机器人，让每个机器人删除的指令数都最少。
用d[x,y,i]表示要让前i条指令被执行（或被删除）后机器人处于位置(x,y)所需要删除的最少指令数，请读者列出状态转移方程。
1.5.12首先，我们直观的猜测：任意一副筷子中A和B一定是长度相邻的两只筷子。
证明如下：对于某副筷子(A1,B1,C1)和另一副筷子(A2,B2,C2)，如果A1<=A2<=B1<=B2，那么交换一下筷子重新组合成(A1,A2,C1)和(B1,B2,C2)质量和会更优。
对于某副筷子(A,B,C)和闲置的筷子D，如果A<=D<=B，那么交换一下重新组合成(A,D,C)质量和也会更优。
这样，我们得到了一个线性结构，只需要从左往右或从后往左递推。
在本题中，由于第3根筷子比另2根长，所以我们从长筷子往短筷子递推。
在递推之前，首先将N只筷子从小到大排序，Li是第i只筷子的长度。
用d[i,j]表示用i..n的单只筷子组成j副筷子的最小质量值之和，则当且仅当n-i+1>=3j的时候状态是合法的。
请读者自己写出状态转移方程。
1.5.13这道题目有一个很讨厌的条件：“只要有任务是可以完成的，那么工人不能闲着没事做”。
如果工人必须按照任务序号递增的顺序，那么本题可以用简单的动态规划解决，但是本题没有规定任务完成的顺序，如果我们用d[i]代表i时刻以后还需要的最少时间，那么我们做状态转移的时候会很为难：我们似乎无法知道那么任务是已经完成了的（它们不能被重复执行），因此决策集合无法确定。
即：问题有后效性！真是这样吗？（解决后效性的通常办法是增加状态参量，即记录已经有哪些任务完成了，但是这样做状态量会大增，并不是一个好办法）我们需要避免重复选择任务，但是细心的读者一定已经发现了：根本不会重复选择任务。
原因在于一个容易被忽略的条件：t<=di-ai<2ti。
当完成一个任务以后，严格的时间期限已经不可能允许工作再重复选择这个任务了。
接下来的任务就十分简单了，请读者自己思考。
1.5.17提示：本题很容易想到O(n^3)的直接动态规划，但是时间复杂度还可以降低。
先连接各点和圆心，把面积最大转化为正弦函数和最大，再利用正弦函数的性质进行优化。
1.5.18铁球下落的高度和总是一定的，所以我们关心的问题只是它的水平移动距离。
我们称平台i的两头为平台端点的横坐标为x[i,0]和x[i,1]，并设端点i纵坐标为y[i]。
为方便处理，我们将铁球的初始位置抽象成宽度为0的平台0。
每落到一个平台，球有两种决策：向左滚和向右滚，因此我们设从平台i的第k个边缘(k=0为左边缘，k=1为右边缘)落下后还需要移动的最少水平距离为d[i,k]。
设p[i,k]为从平台i的第k个边缘落下后到达的平台编号（即状态d[i,k]描述的“当前平台”，如果落下会摔碎，则p[i,k]=-1），则两种决策是：决策一：向左滚，指标函数为d[p[i,k],0]+|x[i,k] - x[p[i,k],0]|决策二：向右滚，指标函数为d[p[i,k],1]+|x[i,k] - x[p[i,k],1]|状态数为O(n)，决策数为O(1)，动态规划的时间复杂度取决于状态转移的时间复杂度，即p数组的计算复杂度。
我们可以从高到低依次考察平台i下面平台j，如果x[i,k]处于区间[x[j,0], x[j,1]]内，则p[i,k]=j。
最坏情况下的时间复杂度为O(n^2)，比动态规划本身还要高。
事实上可以用BST或者线段树来做到O(nlogn)，请读者思考。
