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;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/220685.html
標籤：其他