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
0
输出样例
5
6
7
8
9
10
// An highlighted block
#include <iostream>
#include <algorithm>
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 <<a[i]<<endl;
}
return 0;
}
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
输出样例
715827883
分析
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<iostream>
#include <algorithm>
#include<string>
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<len){
t+=a[i]-'0'+b[i]-'0';
ans+=(t%10+'0');//拼接
t/=10;
i++;
}
if(t>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<<dp[n]<<endl;
}
return 0;
}
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<iostream>
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];
else if(i!=1 && j==1) // 给第一列街区赋值，不包括初始位置
dp[i][j] = dp[i-1][j];
else if(i!=1 || j!=1) //除初始位置的其他位置
dp[i][j] = (dp[i][j-1] + dp[i-1][j]) % 10000 ; // 每个街区的路径数为左边街区的路径数和上方路径数之和
}
}
cout << dp[n][n] << endl;
return 0;
}
