练习1-递推等

1000 Problem A

时间限制 : 40/20 MS(Java/Others) | 内存限制 : 65536/32768 KB(Java/Others)

Submits : 110 | Solved : 24

题目描述

给定一组无序数值，数值的大小在1到百万之间，数值的个数在10-50万个之间。现需要找出其中第5到第10小的整数。

输入要求

一组非0整数，（个数>=10个），0为结束标志。

输出要求

其中第5到第10小的整数。每输出一个整数换行。

输入样例

1

2

3

4

5

6

7

8

9

10

输出样例

5

6

7

8

9

10

// An highlighted block #include #include using namespace std; int main{ int a[5000]; int i=0; int x;while(cin >>x){if(x==0)break; a[i++]=x;}sort(a,a+i-2);for(i=4;i<10;i++){ cout <

1001 Problem B

时间限制 : 2000/1000 MS(Java/Others) | 内存限制 : 65536/32768 KB(Java/Others)

Submits : 55 | Solved : 7

题目描述

对于一个2行N列的走道。现在用12或22的砖去铺满。问有多少种不同的方式（请用递推方式求解）。如果N很大，需要高精度计算。下图是一个2行17列的走道的某种铺法：

输入要求

一个整数N，N<=1000。

输出要求

共有多少种铺法。

输入样例

30

输出样例

分析

1 大整数的加法用string

2 铺砖问题:

每次铺砖时考虑的情况大致类似，所以可以用递归求解。根据最后剩余的列数，我们将本问题分成两种情况：

A：最后剩余一列，那么假设把这列去掉后，其铺砖情况与n-1时的情况一样，而加上后，也只有一种情况所以方法数位pave（n-1）

B：最后剩余两列，那么把这两列先去掉后和n-2的情况一样，加上这两列后一共有三种情况：12竖着放2列，12横着放，22直接填满。因为12竖着放和A情况重复，所以方法数为pave（n-2）*2

综上：方法总数=pave（n-1）+2*pave（n-2

// An highlighted block #include #include #include using namespace std;//用string实现大整数加法 string myadd(string a,string b){reverse(a.begin,a.end);//字符串翻转reverse(b.begin,b.end); int len;if(a.length
>b.length){ len=a.length;//记录长的长度while(b.length==len) b+=" ";//末尾补齐}else{ len=b.length;while(a.length==len) a+=" ";} int i=0,t=0; string ans;while(i 0)
ans+=t+'0';//进位加上reverse(ans.begin,ans.end);return ans;} int main{ int n; string dp[1200]; dp[0]="1"; dp[1]="1"; dp[2]="3";for(int i=3;i<=1000;i++){
dp[i]=myadd(dp[i-1],myadd(dp[i-2],dp[i-2]));}while(cin >>n){ cout<

1002 Problem C

时间限制 : 2000/1000 MS(Java/Others) | 内存限制 : 65536/32768 KB(Java/Others)

Submits : 56 | Solved : 11

题目描述

一个N×N的街区，左上角为[1,1],右下角为[N,N]，（N<100）。现要求出从左上角到右下角的路径总数，每次只能向下或向右走。

路径中有M个街区有障碍（M<10），不能通过，但不会形成到不了终点的情况。

每条路上的汇总路径数都要对10000取余，以免数据溢出。

输入要求

第一行：两个整数N和M；分别表示街区维度和障碍数；

第二行开始M行：障碍所在的街区。

输出要求

输出满足题意的路径数。

输入样例

3 1

3 1

输出样例

5

// An highlighted block # include using namespace std; int dp[101][101];// 保存走到每个街区的路数 int main{for(int i=0;i<=100;i++)for(int j=0;j<=100;j++) dp[i][j]=1; int n,m;// 街区的维数和障碍数 cin >> n
>> m;while(m--)// 将每个有障碍的街区置为0 { int a, b; cin >> a >> b; dp[a][b]=0;}for(int i=1; i<=n; i++)for(int j=1; j<=n; j++){if(dp[i][j]!=0)//不考虑已经被置为0的有障碍的街区 {if(i==1&&
j!=1)// 给第一行街区赋值，不包括初始位置 dp[i][j]= dp[i][j-1];elseif(i!=1&& j==1)// 给第一列街区赋值，不包括初始位置 dp[i][j]= dp[i-1][j];elseif(i!=1|| j!=1)//除初始位置的其他位置 dp[i][j]=(dp[i][j-1]+ dp[i-1][j])%10000;//
每个街区的路径数为左边街区的路径数和上方路径数之和 }} cout << dp[n][n]<< endl;return0;}