點選可展開上面目錄
Acm.njupt 1001-1026簡單題
第一頁許多是簡單題,每題拿出來說說,沒有必要,也說不了什麼.
直接貼上AC的代碼.初學者一題題做,看看别人的AC代碼,尋找自己的問題.
記得實習公司的經理說過,最快提高編碼水準的方法有一個就是看别人的代碼.簡單題沒有太多需要解釋的方法,就是訓練一些編碼方法.
由于第一頁的許多題目都是大二的時候寫的,許多代碼不簡潔,算法太水,低級錯誤等等應該都有.不管怎樣,還是AC了.
貼出來,有問題大家指出,太菜的地方各位諒解.
1001 整數求和
描述
給定兩個整數，求它們之和。
輸入
兩個整數A，B.
輸出
兩個整數的和。
樣例輸入
1 2
樣例輸出
3
小結 : 代碼不貼了,看到AC代碼中有0記憶體的方法,上網搜,有人說是用彙編封裝,有人說是記憶體洩露,或者oj系統bug.不得而知,求知情者指教.
1002 求最值
描述
給定N個整數（1<=N<=100），求出這N個數中的最大值，最小值。
輸入
多組資料，第一行為一個整數N，第二行為N個不超過100的正整數，用空格隔開。
輸出
對每組資料輸出一行，包含兩個整數，用一個空格隔開，分别表示N個數中的最大值和最小值
樣例輸入
5
4 6 7 3 1
4
4 3 5 1
樣例輸出
7 1
5 1
#include <cstdio>
const int N = 101;
int main()
{
int a[N];
int n,i,max,min;
while(scanf("%d",&n)!=EOF)
{
max = -1,min = 101;
for(i=1;i<=n;i++)
{
scanf("%d",&a[i]);
if(a[i]>max) max = a[i];
if(a[i]<min) min = a[i];
}
printf("%d %d\n",max,min);
}
return 0;
}
小結 : 這題測試不是很難,故最簡單的周遊能夠AC,比較2*N次.還有更簡化的方法就是,相鄰的兩兩比較,再用小的跟min比較,大的跟max比較,比較次數為1.5*N次.
改進後代碼如下:
#include <iostream>
using namespace std;
const int N = 101;
#define INF 99999
void swap(int &a,int &b)
{
a=a^b;
b=a^b;
a=a^b;
}
int main()
{
int A[N];
int n,i,max,min;
while(scanf("%d",&n)!=EOF)
{
max = -1,min = INF;
for(i=0; i<n; i++)
{
scanf("%d",&A[i]);
}
for(int i=0; i<n-1; i+=2)
{
if(A[i]>A[i+1])
swap(A[i],A[i+1]);
if(A[i]<min)
min=A[i];
if(A[i+1]>max)
max=A[i+1];
}
if(A[n-1]<min)
min=A[n-1];
if(A[n-1]>max)
max=A[n-1];
printf("%d %d\n",max,min);
}
return 0;
}
1003 斐波那契數列
描述
在數學上，斐波那契數列（FibonacciSequence），是以遞歸的方法來定義：
F0 = 0
F1 = 1
Fn = Fn - 1 + Fn - 2
用文字來說，就是斐波那契數列由0和1開始，之後的斐波那契數就由之前的兩數相加。首幾個斐波那契數是：
0, 1, 1, 2, 3, 5,8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946，………………
特别指出：0不是第一項，而是第零項。
在西方，最先研究這個數列的人是比薩的列奧納多（又名斐波那契），他描述兔子生長的數目時用上了這數列。
第一個月有一對剛誕生的兔子
第兩個月之後它們可以生育
每月每對可生育的兔子會誕生下一對新兔子
兔子永不死去
假設在n月有新生及可生育的兔子總共a對，n+1月就總共有b對。在n+2月必定總共有a+b對：因為在n+2月的時候，所有在n月就已存在的a對兔子皆已可以生育并誕下a對後代；同時在前一月(n+1月)之b對兔子中，在當月屬于新誕生的兔子尚不能生育。
現請以較短的時間，求出斐波那契數列第n項數值，0≤n≤40。
#include <iostream>
using namespace std;
int fib[46],j=2,i;
int main()
{
fib[0]=0;
fib[1]=1;
while(j<=42)
{
fib[j]=fib[j-1]+fib[j-2];
j++;
}
while(scanf("%d",&i)!=EOF)
{
printf("%d\n",fib[i]);
}
return 0;
}
1004 線性表操作
描述
線性表是n個元素的有序集合（n0），n是線性表中元素的個數，稱為線性表的長度。可以用一組位址連續的存儲單元依次存儲線性表中元素，采用這種存儲方式的線性表稱為順序表。
請在順序表上實作運算，實作順序表的逆置，删除表中所有元素值等于x的元素。
輸入
三組資料，順序表元素類型分别為整型、字元型和實型。
每一組第一行給出元素數目n（0<n≤1000），第二行給出元素數值，第三行給出待删除的元素。
輸出
三組資料，每一組第一行為逆置後的順序表元素，第二行是在此基礎上删除指定元素後的順序表元素
樣例輸入
8
1 2 3 7 5 6 7 8
7
3
a c m
h
4
1.2 3.4 5.6 7.8
1.2
樣例輸出
8 7 6 5 7 3 2 1
8 6 5 3 2 1
m c a
m c a
7.8 5.6 3.4 1.2
7.8 5.6 3.4
#include<iostream>
#include<math.h>
using namespace std;
#define EPS 1e-6
struct list
{
int ele;
char ele2;
float ele3;
int cur;
};
int main()
{
int n,p,i,a,p2,len;
float b;
struct list str[1002];
scanf("%d",&n);
len=n;
p=0;
str[0].cur=-1;
for(i=1;i<=n;i++)
{
scanf("%d",&str[i].ele);
str[i].cur=str[p].cur;
str[p].cur=i;
}
p=str[0].cur;
while(p!=-1)
{
cout<<str[p].ele<<' ';
p=str[p].cur;
}
cout<<endl;
scanf("%d",&a);
p2=0;
p=str[p2].cur;
while(p!=-1)
{
if(str[p].ele==a)
{
str[p2].cur=str[p].cur;
p=str[p2].cur;
len--;
}
else
{
p2=p;
p=str[p].cur;
}
}
if(len<=0)
{
cout<<endl;
}
else
{
p=str[0].cur;
while(p!=-1)
{
cout<<str[p].ele<<' ';
p=str[p].cur;
}
cout<<endl;
}
getchar();
scanf("%d",&n);
len=n;
p=0;
str[0].cur=-1;
getchar();
for(i=1;i<=n;i++)
{
scanf("%c",&str[i].ele2);
str[i].cur=str[p].cur;
str[p].cur=i;
getchar();
}
p=str[0].cur;
while(p!=-1)
{
cout<<str[p].ele2<<' ';
p=str[p].cur;
}
cout<<endl;
scanf("%c",&a);
p2=0;
p=str[p2].cur;
while(p!=-1)
{
if(str[p].ele2==a)
{
str[p2].cur=str[p].cur;
p=str[p2].cur;
len--;
}
else
{
p2=p;
p=str[p].cur;
}
}
if(len==0)
cout<<endl;
else
{
p=str[0].cur;
while(p!=-1)
{
cout<<str[p].ele2<<' ';
p=str[p].cur;
}
cout<<endl;
}
scanf("%d",&n);
len=n;
p=0;
str[0].cur=-1;
for(i=1;i<=n;i++)
{
scanf("%f",&str[i].ele3);
str[i].cur=str[p].cur;
str[p].cur=i;
}
p=str[0].cur;
while(p!=-1)
{
cout<<str[p].ele3<<' ';
p=str[p].cur;
}
cout<<endl;
scanf("%f",&b);
p2=0;
p=str[p2].cur;
while(p!=-1)
{
if(fabs(str[p].ele3-b)<=EPS)
{
str[p2].cur=str[p].cur;
p=str[p2].cur;
len--;
}
else
{
p2=p;
p=str[p].cur;
}
}
if(len<=0)
cout<<endl;
else
{
p=str[0].cur;
while(p!=-1)
{
cout<<str[p].ele3<<' ';
p=str[p].cur;
}
cout<<endl;
}
return 0;
}
小結 : 這題的代碼用連結清單寫的,寫的非常屎,大家不要學習
1005 多項式加
1006 多項式乘
小結 : 當時沒AC,有空再做.
1007 完美立方
描述
a3 = b3 + c3 + d3為完美立方等式。例如123 = 63 + 83 + 103 。編寫一個程式，對任給的正整數N (N≤100)，尋找所有的四元組(a, b, c, d)，使得a3 = b3 + c3 + d3，其中1<a,b, c, d ≤N。
輸入
正整數N (N≤100)
輸出
每行輸出一個完美立方，按照a的值，從小到大依次輸出。當兩個完美立方等式中a的值相同，則依次按照b、c、d進行非降升序排列輸出，即b值小的先輸出、然後c值小的先輸出、然後d值小的先輸出。
樣例輸入
24
樣例輸出
Cube = 6, Triple = (3,4,5)
Cube = 12, Triple = (6,8,10)
Cube = 18, Triple = (2,12,16)
Cube = 18, Triple = (9,12,15)
Cube = 19, Triple = (3,10,18)
Cube = 20, Triple = (7,14,17)
Cube = 24, Triple = (12,16,20)
#include<iostream>
using namespace std;
struct node
{
int a;
int b;
int c;
int d;
};
int main()
{
int i,j,k,m,n=0;
struct node str[100];
for(i=6;i<=100;i++)
{
for(j=2;j<=i;j++)
{
for(k=j;k<=i;k++)
{
for(m=k;m<=i;m++)
{
if(i*i*i==(j*j*j+k*k*k+m*m*m))
{
str[n].a=i;
str[n].b=j;
str[n].c=k;
str[n].d=m;
n++;
}
}
}
}
}
while(scanf("%d",&j)!=EOF)
{
for(i=0;;i++)
{
if(str[i].a>j||i>=n)
break;
cout<<"Cube = "<<str[i].a<<", Triple = ("<<str[i].b<<","<<str[i].c<<","<<str[i].d<<")"<<endl;
}
}
return 0;
}
小結 : 大家代碼可以跟簡化很多.
1008 第幾天
描述
在我們現在使用的月曆中, 閏年被定義為能被4整除的年份，但是能被100整除而不能被400整除的年是例外，它們不是閏年。例如：1700, 1800, 1900 和 2100 不是閏年，而 1600, 2000 和 2400是閏年。
給定公元2000年1月1日後的某年某月某日（包括2000年1月1日），你的任務：（1）給出這一天從公元2000年1月1日開始逝去的天數，（2）判斷這一天是當年的第幾天。
輸入
輸入包含若幹行，每行包含三個空格間隔的正整數，它們分别表示年、月、日。輸入最後一行是−1, 不必處理。可以假設結果的年份不會超過9999。
輸出
多組，每組兩行，分别為每行輸入所代表的一天從公元2000年1月1日開始逝去的天數、在當年的第幾天。
樣例輸入
2000 1 1
2009 3 14
-1
樣例輸出
1
3360
73
#include<iostream>
using namespace std;
bool f(int a)
{
if(a%4==0&&!(a%100==0&&a%400!=0))
return true;
else
return false;
}
int main()
{
int num,k,yu,ni,ri,i,num1;
int Ryue[12]={31,29,31,30,31,30,31,31,30,31,30,31};
int yue[12]={31,28,31,30,31,30,31,31,30,31,30,31};
while(scanf("%d%d%d",&ni,&yu,&ri)!=EOF)
{
num=0;
if(ni==-1)
break;
k=2000;
while(k<ni)
{
if(f(k))
num+=366;
else
num+=365;
k++;
}
num1=num;
i=0;
k=yu;
for(i=0;i<k-1;i++)
{
if(f(ni))
num+=Ryue[i];
else
num+=yue[i];
}
num+=ri;
cout<<num-1<<endl<<num-num1<<endl;
}
return 0;
}
1009 2的N次方
描述
程式設計精确計算2的N次方。（N是介于100和1000之間的整數）。
輸入
正整數N (100≤N≤1000)
輸出
2的N次方
樣例輸入
200
樣例輸出
1606938044258990275541962092341162602522202993782792835301376
#include<iostream>
using namespace std;
int main()
{
int str[1000],len,n,i,b,temp;
while(scanf("%d",&n)!=EOF)
{
str[0]=1;
len=1;
while(n--)
{
b=0;
for(i=0;i<len;i++)
{
temp=str[i]*2+b;
b=temp/10;
str[i]=temp%10;
}
while(b!=0)
{
str[i]=b%10;
b=b/10;
i++;
len++;
}
}
for(i=len-1;i>=0;i--)
cout<<str[i];
cout<<endl;
}
return 0;
}
1010 數的計算
描述
要求找出具有下列性質數的個數（包含輸入的自然數n）：
先輸入一個自然數n(n<=1000),然後對此自然數按照如下方法進行處理:
1. 不作任何處理;
2. 在它的左邊加上一個自然數,但該自然數不能超過原數的一半;
3. 加上數後,繼續按此規則進行處理,直到不能再加自然數為止.
輸入
一個自然數n
輸出
一個數，表示滿足條件的數的個數
樣例輸入
6
樣例輸出
6
提示
樣例說明：滿足條件的數是6，16，26，126，36，136
#include<iostream>
#include<math.h>
using namespace std;
__int64 f[1001];
int main()
{
__int64 i,j,n;
memset(f,0,sizeof(f));
//freopen("aa.txt","r",stdin);
f[0]=1;
f[1]=1;
f[2]=2;
f[3]=2;
for(i=4;i<1001;i++)
{
for(j=0;j<=i/2;j++)
{
f[i]+=f[j];
}
}
while(scanf("%d",&n)!=EOF)
{
printf("%I64d\n",f[n]);
}
return 0;
}
1011 大數加法
描述
求兩個非負整數（1000位以内）的和。
輸入
兩個非負整數（1000位以内），以空格分隔。
輸出
兩個非負整數的和。
樣例輸入
111111111111 222222222222
樣例輸出
333333333333
#include<iostream>
using namespace std;
#define maxn 1001
void swap(char &a,char &b)
{
a=a^b;
b=a^b;
a=a^b;
}
void f(char *s1,char *s2)
{
int i,temp;
int n1=strlen(s1);
int n2=strlen(s2);
char t[maxn];
if(n1<n2)
{
strcpy(t,s1);
strcpy(s1,s2);
strcpy(s2,t);
swap(n1,n2);
}
int b=0;
for(i=0; i<n1-i-1; i++)
{
swap(s1[i],s1[n1-i-1]);
}
for(i=0; i<n2-i-1; i++)
{
swap(s2[i],s2[n2-i-1]);
}
for(i=n2; i<n1; i++)
{
s2[i]='0';
}
for(i=0; i<n1; i++)
{
temp=(s1[i]-'0')+(s2[i]-'0')+b;
b=temp/10;
s1[i]=temp%10+'0';
}
while(b!=0)
{
temp=b;
b=b/10;
s1[i]=temp%10+'0';
i++;
}
int n=i;
for(i=0; i<n-i-1; i++)
{
swap(s1[i],s1[n-i-1]);
}
s1[n]='\0';
}
int main()
{
char s1[maxn],s2[maxn];
while(scanf("%s%s",&s1,&s2)!=EOF)
{
f(s1,s2);
cout<<s1<<endl;
}
return 0;
}
小結 : 還是很屎的代碼.
1012 進制轉換
描述
将一個十進制數N轉換成R進制數輸出，2≤R≤16，R≠10。
輸入
多行。第一行指出以下一共有多少組資料，後續每行包含兩個整數N和R，以空格分隔，-100000≤N≤100000，2≤R≤16，R≠10。
輸出
多行。每行給出轉換後的R進制數。
樣例輸入
3
7 2
23 12
-4 3
樣例輸出
111
1B
-11
#include<iostream>
using namespace std;
int f(int n,int r,int s[])
{
int temp;
int i=0;
do
{
s[i]=n%r;
n=n/r;
i++;
}while(n!=0);
n=i;
for(i=0;i<n-i;i++)
{
temp=s[i];
s[i]=s[n-i-1];
s[n-i-1]=temp;
}
return n;
}
int main()
{
int t,n,r,i;
int s[200001];
bool flag;
char str[16]={'0','1','2','3','4','5','6','7','8','9','A','B','C','D','E','F'};
scanf("%d",&t);
while(t--)
{
flag=false;
scanf("%d%d",&n,&r);
if(n<0)
{
flag=true;
n=-n;
}
n=f(n,r,s);
if(flag)
cout<<"-";
for(i=0;i<n;i++)
{
cout<<str[s[i]];
}
cout<<endl;
}
return 0;
}
1013 三角形判斷
描述
給定三條邊的長度，判斷能否組成三角形，如果可以，判斷三角形的形狀。
輸入
一組資料，每行三個實數，在(0,10]之間，精确到小數點後第四位。最後以0 0 0表示結束。
輸出
根據每行的資料判斷，如果不能組成三角形，則輸出“Not a triangle”；如果是“等腰三角形”，則輸出“Isosceles triangle”；如果是“直角三角形”，則輸出“Righttriangle”；如果是“等腰直角三角形”，則輸出“Isosceles right triangle”；如果是“等邊三角形”，則輸出“Equilateral triangle”；否則，輸出“General triangle”。最後輸出一行“End”。
樣例輸入
1.4142 1.4142 2
1.0000 4.0000 5.0000
0 0 0
樣例輸出
Isosceles right triangle
Not a triangle
End
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
int Isosceles(double a,double b,double c);
int Right(double a,double b,double c);
int istriangle(double a,double b,double c)
{
if(a<1e-3) return 0;
if(a+b-c>1e-3)
return 1;
return 0;
}
int Equilateral(double a,double b,double c)
{
if(fabs(a-c)<1e-3)
return 1;
return 0;
}
int IsRight(double a,double b,double c)
{
double aa=pow(a*1.0,2),bb=pow(b*1.0,2),cc=pow(c*1.0,2);
if(fabs(aa+bb-cc)<1e-3&&(fabs(a-b)<1e-3))
return 1;
return 0;
}
int Right(double a,double b,double c)
{
if(!(fabs(a-b)<1e-3))
{
double aa=pow(a*1.0,2),bb=pow(b*1.0,2),cc=pow(c*1.0,2);
if(fabs(aa+bb-cc)<1e-3)
return 1;
}
return 0;
}
int Isosceles(double a,double b,double c)
{ if(fabs(a-b)<1e-3||fabs(c-b)<1e-3) return 1;
return 0;
}
int main()
{
double temp[5];
int sum;
while(1)
{
scanf("%lf%lf%lf",&temp[0],&temp[1],&temp[2]);
if(temp[0]==0) break;
sum=0;
//sort
sort(temp,temp+3);
if(istriangle(temp[0],temp[1],temp[2])==0)
printf("Not a triangle\n");
else
{
if(Equilateral(temp[0],temp[1],temp[2])==1)
{
sum++;
printf("Equilateral triangle\n");
}
else
{
if(IsRight(temp[0],temp[1],temp[2])==1)
{
sum++;
printf("Isosceles right triangle\n");
}
else
{
if(Isosceles(temp[0],temp[1],temp[2])==1)
{
sum++;
printf("Isosceles triangle\n");
}
else
{
if(Right(temp[0],temp[1],temp[2])==1)
{
sum++;
printf("Right triangle\n");
}
}
}
}
if(sum==0)
{
printf("General triangle\n");
}
}
}
printf("End");
return 0;
}
小結 : 精确到小數點後四位,判斷時要用1E-3.當時-3,-4,-5都試過,-3 AC了.
1014 資料的插入與删除
描述
在一組資料（數目不超過10000）中，插入新數，删除所有與給定數相等的資料。
輸入
第一行是未排序的一組非負整數,數目不超過10000。以-1作為結束标志。
第二行是要插入的數。
第三行是要删除的數。
輸出
第一行輸出自小到大排好序的數。如果沒有元素，輸出“No elements.”（不包括引号）。
第二行輸出插入後自小到大排好序的數，以“,”隔開。
第三行輸出删除後自小到大排好序的數，以“,”隔開。如果沒有元素，輸出“No elements.”（不包括引号）。
樣例輸入
100 98 79 63 44 99 -1
88
79
樣例輸出
44,63,79,98,99,100
44,63,79,88,98,99,100
44,63,88,98,99,100
#include<iostream>
using namespace std;
int main()
{
int m=0,i,j,jia,jian,temp,str[10001];
while(cin>>str[m]&&str[m]!=-1)
{m++;}
cin>>jia>>jian;
str[m]=jia;
for(j=m-2;j>=0;j--)
{
for(i=0;i<=j;i++)
{
if(str[i]>str[i+1])
{
temp=str[i];
str[i]=str[i+1];
str[i+1]=temp;
}
}
}
if(m==0)
cout<<"No elements."<<endl;
else{
for(i=0;i<=m-2;i++)
{
cout<<str[i]<<',';
}
cout<<str[m-1]<<endl;
}
for(j=m-1;j>=0;j--)
{
for(i=0;i<=j;i++)
{
if(str[i]>str[i+1])
{
temp=str[i];
str[i]=str[i+1];
str[i+1]=temp;
}
}
}
for(i=0;i<=m-1;i++)
{
cout<<str[i]<<',';
}
cout<<str[m]<<endl;
for(i=0;i<=m;i++)
{
if(str[i]==jian)
{
for(j=i;j<=m-1;j++)
{
str[j]=str[j+1];
}
m=m-1;
i=i-1;
}
}
if(m==-1)
{
cout<<"No elements."<<endl;
}
else
if(m==0)
{
cout<<str[m]<<endl;
}
else{
for(i=0;i<=m-1;i++)
{
cout<<str[i]<<',';
}
cout<<str[m]<<endl;}
return 0;
}
1015 最大公約數與最小公倍數
描述
求兩個正整數的最大公約數和最小公倍數
輸入
兩個正整數A，B
輸出
兩個正整數的最大公約數、最小公倍數
樣例輸入
4 3
樣例輸出
1 12
#include<iostream>
using namespace std;
void f(int &a,int &b)
{
if(a<b)
a=a^b;
b=a^b;
a=a^b;
}
int f1(int a,int b)
{
int temp;
int A=a,B=b;
F(A,B);
while(A!=B)
{
temp=A-B;
A=temp;
f(A,B);
}
return A;
}
int main()
{
int a,b;
while(scanf("%d%d",&a,&b)!=EOF)
{
cout<<f1(a,b)<<' '<<a*b/f1(a,b)<<endl;
}
return 0;
}
小結 : 進一步分析見blog:
1016 求幂
描述
求R的n次幂(0.0<r<99.999,0<n<=25)
輸入
每行輸入兩個數R和n
R值占1-6列，n占8-9列
輸出
對應于每一行輸入，輸出R的n次幂
前導的0不要輸出
無意義的0不要輸出
如果結果是一個整數，不要輸出小數點
最後一行是空行
樣例輸入
95.123 12
0.4321 20
5.1234 15
6.7592 9
98.999 10
1.0100 12
樣例輸出
548815620517731830194541.899025343415715973535967221869852721
.00000005148554641076956121994511276767154838481760200726351203835429763013462401
43992025569.928573701266488041146654993318703707511666295476720493953024
29448126.764121021618164430206909037173276672
90429072743629540498.107596019456651774561044010001
1.126825030131969720661201
import java.io.*;
import java.util.*;
import java.math.*;
public class Main {
public static void main(String args[]){
Scanner cin = new Scanner(System.in);
Integer n;
BigDecimal a;
String s;
while(cin.hasNext()){
a = cin.nextBigDecimal();
n = cin.nextInt();
s = a.pow(n).stripTrailingZeros().toPlainString();
if(s.charAt(0) == '0')
s = s.substring(1);
System.out.println(s);
}
}
}
小結 : 投機取巧,java封裝了大數計算,~~~
1017 乘積最大
描述
今年是國際數學聯盟确定的“2000——世界數學年”，又恰逢我國著名數學家華羅庚先生誕辰90周年。在華羅庚先生的家鄉江蘇金壇，組織了一場别開生面的數學智力競賽的活動，你的一個好朋友XZ也有幸得以參加。活動中，主持人給所有參加活動的選手出了這樣一道題目：
設有一個長度為N的數字串，要求選手使用K個乘号将它分成K+1個部分，找出一種分法，使得這K+1個部分的乘積能夠為最大。
同時，為了幫助選手能夠正确了解題意，主持人還舉了如下的一個例子：
有一個數字串：312， 當N=3，K=1時會有以下兩種分法：
1) 3*12=36
2) 31*2=62
這時，符合題目要求的結果是：31*2=62
現在，請你幫助你的好朋友XZ設計一個程式，求得正确的答案。
輸入
輸入共有兩行：
第一行共有2個自然數N，K（6≤N≤40，1≤K≤6）
第二行是一個長度為N的數字串。
輸出
輸出所求得的最大乘積（一個自然數）,答案在long long 資料範圍之内。
#include<iostream>
#define MAX 50
using namespace std;
__int64 max(__int64 a,__int64 b)
{
return a>=b?a:b;
}
__int64 G[MAX][MAX],dp[MAX][8],str[MAX];
int main()
{
__int64 n,m,i,j,l;
char ch;
while(scanf("%I64d%I64d",&n,&m)!=EOF)
{
getchar();
for(i=1;i<=n;i++)
{
scanf("%c",&ch);
str[i]=ch-'0';
G[i][i]=str[i];
}
for(i=1;i<=n-1;i++)
{
for(j=i+1;j<=n;j++)
{
G[i][j]=G[i][j-1]*10+str[j];
}
}
for(i=1;i<=n;i++)
dp[i][0]=G[1][i];
for(i=1;i<=n;i++)
{
for(j=1;j<=i;j++)
{
dp[i][j]=0;
for(l=j;l<i;l++)
{
dp[i][j]=max(dp[i][j],dp[l][j-1]*G[l+1][i]);
}
}
}
printf("%I64d\n",dp[n][m]);
}
return 0;
}
小結 : 動态規劃問題.
1018 深度周遊二叉樹
描述
二叉樹(binary tree)是非常重要的樹形資料結構，它是結點的有限集合，該集合或者為空集，或者是由一個根和兩個互不相交的、稱為該根的左子樹和右子樹的二叉樹組成。
一般意義上，周遊（traverse）一棵二叉樹意味着對該二叉樹中的每個結點通路且僅通路一次。
（1）若二叉樹不為空，先序周遊是指先通路該樹根結點，再通路先序周遊左子樹，最後先序周遊右子樹。
（2）若二叉樹不為空，中序周遊是指先中序周遊左子樹，再通路該樹根結點，最後中序周遊右子樹。
（3）若二叉樹不為空，後序周遊是指先後序周遊左子樹，再後序周遊右子樹，最後通路該樹根結點。
圖1018-1給出一棵二叉樹，先序周遊序列為A BD C E F，中序周遊序列為B D A E C F，後序周遊序列為D B E F C A，樣例輸出給出了輸出格式。
圖1018-1
程式設計建立下圖1018-2描述的二叉樹，給出先序、中序和後序周遊序列。
圖1018-2
輸入
無需顯式輸入任何資料
輸出
共三行，依次輸出先序、中序和後序周遊序列。
#include<stdio.h>
int main()
{
printf("PreOrder: D E H F J G C K A B\nInOrder: H E J F G K C D A B\nPostOrder: H J K C G F E B A D\n");
return 0;
}
小結 : 都說了沒有顯示輸入~~
1019 計算二叉樹的高度與節點數
二叉樹是非常重要的樹形資料結構，根據該樹的先序、中序或後序周遊序列可以建立一棵二叉樹。例如輸入先序周遊序列A B # D # # C E # # F # #可以建立圖1019-1所示的二叉樹，這裡用#代表空樹或空子樹（另一種說法：若無孩子結點，則用#代替），如圖1019-2。
圖1019-1
圖1019-2
請實作基于周遊的二叉樹運算：求高度、計算結點數目
輸入
二叉樹的先序周遊序列，用#代表空樹或空子樹。
輸出
共五行
前三行依次輸出先序、中序和後序周遊序列，
第四行輸出二叉樹的高度，
第五行依次輸出二叉樹總結點數目、葉子結點數目、度為1的結點數目。
#include<iostream>
using namespace std;
struct BTnode
{
char n;
struct BTnode *l;
struct BTnode *r;
};
void f(struct BTnode * &t)
{
char c;
cin>>c;
if(c=='#')
t=NULL;
else{
t=new struct BTnode;
t->n=c;
f(t->l);
f(t->r);
}
}
void f1(struct BTnode *t)
{
if(t)
{
cout<<' '<<t->n;
f1(t->l);
f1(t->r);
}
}
void f2(struct BTnode *t)
{
if(t)
{
f2(t->l);
cout<<' '<<t->n;
f2(t->r);
}
}
void f3(struct BTnode *t)
{
if(t)
{
f3(t->l);
f3(t->r);
cout<<' '<<t->n;
}
}
int f4(struct BTnode *t)//??????????????????????????????
{
if(t==NULL)
return 0;
int lhigh=f4(t->l);
int rhigh=f4(t->r);
if(lhigh>=rhigh)
return lhigh+1;
else
return rhigh+1;
}
void f5(struct BTnode *t,int &flag)
{
if(t)
{
if(!t->l&&!t->r)
flag++;
f5(t->l,flag);
f5(t->r,flag);
}
}
void f6(struct BTnode *t,int &flag1)
{
if(t)
{
flag1++;
f6(t->l,flag1);
f6(t->r,flag1);
}
}
void f7(struct BTnode *t,int &flag2)
{
if(t)
{
if((!(t->r))&&t->l)
{
flag2++;
f7(t->l,flag2);
}
if((!(t->l))&&t->r)
{
flag2++;
f7(t->r,flag2);
}
if(t->r&&t->l)
{
f7(t->l,flag2);
f7(t->r,flag2);
}
}
}
int main()
{
int flag=0;
int flag1=0;
int flag2=0;
struct BTnode *first;
f(first);
cout<<"PreOrder:";
f1(first);
cout<<endl;
cout<<"InOrder:";
f2(first);
cout<<endl;
cout<<"PostOrder:";
f3(first);
cout<<endl;
cout<<f4(first)<<endl;
f6(first,flag1);
cout<<flag1<<' ';
f5(first,flag);
cout<<flag<<' ';
f7(first,flag2);
cout<<flag2<<endl;
return 0;
}
1020 層次周遊二叉樹
描述
二叉樹是非常重要的樹形資料結構，層次周遊一棵二叉樹是按從上到下、從左到右的次序通路樹上的結點。例如，圖1020所示的二叉樹層次周遊序列為A B C D E F。
圖1020
請根據先序周遊序列建立一棵的二叉樹（用#代表空樹或空子樹），輸出層次周遊序列。
輸入
二叉樹的先序周遊序列，用#代表空樹或空子樹
輸出
二叉樹層次周遊序列
樣例輸入
A B # D # # C E # # F # #
樣例輸出
LevelOrder: A B C D E F
#include<iostream>
#include<deque>
#include<math.h>
#include<string>
using namespace std;
struct node
{
char A;
struct node * r;
struct node * l;
};
deque <struct node *> S;
struct node *build()
{
char ch;
cin>>ch;
struct node *first;
first=new struct node;
if(ch=='#')
first=NULL;
else
{
first->A=ch;
first->l=build();
first->r=build();
}
return first;
}
void f(struct node *first)
{
if(first)
S.push_back(first);
while(S.size()>0)
{
struct node *p=S.front();
S.pop_front();
cout<<' '<<p->A;
if(p->l)
S.push_back(p->l);
if(p->r)
S.push_back(p->r);
}
return ;
}
int f(const void *a,const void *b)
{
return 1;
}
int main()
{
struct node *first;
//freopen("aa.txt","r",stdin);
first=build();
cout<<"LevelOrder:";
f(first);
cout<<endl;
return 0;
}
1021 二叉樹的複制與左右子樹互換
描述
二叉樹是非常重要的樹形資料結構。複制一棵二叉樹是在另一個存儲區存放相同的結構和内容，而一棵二叉樹上所有左右子樹互換是在原存儲區上的運算。
請分别根據先序周遊序列建立兩棵的二叉樹（用#代表空樹或空子樹），再将這兩棵二叉樹複制為左右子樹建立第三棵二叉樹，輸出先序和層次周遊序列，最後将第三棵二叉樹上所有左右子樹互換，并輸出先序和層次周遊序列。
輸入
共三行
前兩行分别對應兩棵二叉樹的先序周遊序列，用#代表空樹或空子樹
第三行為第三棵二叉樹的根結點。
輸出
共四行
前兩行為第三棵二叉樹生成時的先序、層次周遊序列，
後兩行為第三棵二叉樹左右子樹互換後的先序、層次周遊序列。
樣例輸入
B # D # #
C E # # F # #
A
樣例輸出
PreOrder: A B D C E F
LevelOrder: A B C D E F
PreOrder: A C F E B D
LevelOrder: A C B F E D
#include<iostream>
#include<deque>
using namespace std;
struct node
{
char c;
struct node *ld;
struct node *rd;
};
deque <struct node *> S;
struct node *build()
{
char ch;
cin>>ch;
struct node *p;
p=(struct node *)malloc(1*sizeof(struct node));
if(ch=='#')
{
p=NULL;
}
else
{
p->c=ch;
p->ld=build();
p->rd=build();
}
return p;
}
void f(struct node *p)
{
if(p)
{
cout<<' '<<p->c;
}
if(p->ld)
{
f(p->ld);
}
if(p->rd)
{
f(p->rd);
}
return ;
}
void f2(struct node *first)
{
struct node *temp;
if(first)
{
temp=first->ld;
first->ld=first->rd;
first->rd=temp;
}
if(first->ld)
{
f2(first->ld);
}
if(first->rd)
{
f2(first->rd);
}
return ;
}
void f3(struct node *first)
{
if(first)
S.push_back(first);
while(S.size()>0)
{
struct node *p=S.front();
S.pop_front();
cout<<' '<<p->c;
if(p->ld)
S.push_back(p->ld);
if(p->rd)
S.push_back(p->rd);
}
return ;
}
struct node *str[4];
int main()
{
//freopen("fuck.txt","r",stdin);
int i;
char ch;
for(i=1;i<=2;i++)
{
str[i]=build();
}
cin>>ch;
str[3]=new struct node;
str[3]->c=ch;
str[3]->ld=str[1];
str[3]->rd=str[2];
cout<<"PreOrder:";
f(str[3]);
cout<<endl;
cout<<"LevelOrder:";
f3(str[3]);
cout<<endl;
f2(str[3]);
cout<<"PreOrder:";
f(str[3]);
cout<<endl;
cout<<"LevelOrder:";
f3(str[3]);
cout<<endl;
return 0;
}
1022 哈夫曼編碼與譯碼
描述
已知電文包括的字元集為{A，C，I，M，N，P，T，U}，輸入對應權值，對字元集合進行哈夫曼編碼，完成電文的哈夫曼編碼與譯碼工作。
輸入
共三行：第一行為對應字元集{A，C，I，M，N，P，T，U}的權值第二行為一段字元串表示的電文(長度不超過1000）；第三行為一段電文的哈夫曼編碼。
輸出
共十行：
前八行為各字元的編碼；
第九行是與第二行輸入對應的哈夫曼編碼；
第十行是與第三行輸入對應的電文。
樣例輸入
1 2 3 4 5 6 7 8
NUPTICPCACM
1111011111100
樣例輸出
A: 11110
C: 11111
I: 1110
M: 100
N: 101
P: 110
T: 00
U: 01
1010111000111011111110111111111011111100
ACM
#include<iostream>
#include<queue>
#include<string>
using namespace std;
#define MAX 10
char str[8]={'A','C','I','M','N','P','T','U'};
int temp[MAX*3];
int str2[256][MAX*3];
string str3;
class node
{
public:
int k;
char c;
node *l,*r;
node()
{
c='0';
k=0;r=l=NULL;
}
node(int a,char s)
{
k=a;r=l=NULL;
c=s;
}
friend node* uni(node *p,node *q)
{
node *temp=new node(p->k+q->k,'0');
temp->l=p;
temp->r=q;
return temp;
}
friend void prim(node *p,int L);
};
void prim(node *p,int L)
{
if(!p->r)
{
str2[p->c][0]=L;
for(int i=1;i<=L;i++)
{
str2[p->c][i]=temp[i-1];
}
}
else
{
temp[L]=0;
prim(p->l,L+1);
temp[L]=1;
prim(p->r,L+1);
}
}
class nodeCmp : public binary_function<node*, node*, bool>
{
public: bool operator()(node* p1, node* p2) const
{
return p1->k > p2->k;
}
};
node *s[MAX*3];
priority_queue<node *,deque<node *>,nodeCmp> pro_queue;
int main()
{
// freopen("ayjs.txt","r",stdin);
int i,a;
for(i=0;i<8;i++)
{
cin>>a;
node *p;
p=new node(a,str[i]);
s[i]=p;
pro_queue.push(s[i]);
}
while(pro_queue.size()>1)
{
node *p,*q,*k;
p=pro_queue.top();
pro_queue.pop();
q=pro_queue.top();
pro_queue.pop();
k=uni(p,q);
pro_queue.push(k);
}
node *p=pro_queue.top();
prim(p,0);
for(int i=0;i<8;i++)
{
cout<<str[i]<<": ";
for(int j=1;j<=str2[str[i]][0];j++)
{
cout<<str2[str[i]][j];
}
cout<<endl;
}
cin>>str3;
int len=str3.length();
for(int i=0;i<len;i++)
{
for(int j=1;j<=str2[str3[i]][0];j++)
{
cout<<str2[str3[i]][j];
}
}
cout<<endl;
cin>>str3;
len=str3.length();
node *q=pro_queue.top();
for(int i=0;i<len;i++)
{
if(str3[i]=='1')
{
q=q->r;
}
else
{
q=q->l;
}
if(q->c!='0')
{
cout<<q->c;
q=pro_queue.top();
}
}
return 0;
}
小結 : 哈夫曼編碼的正确性證明見blog:
1023 字元串排序
描述
有一些A、C、M組成的字元串，将其按字元A排序。
輸入
一組測試資料，輸入資料由若幹行組成，每行是字元A、C或M組成的字元串。
輸出
對所有輸入的資料，先按字元A的個數進行升序排序，如果字元A的數量相等，再按出現的先後順序排序，每行輸出一個字元串。
樣例輸入
ACM
MCA
AACAAMMM
AACCMM
CMAAMMMMMM
AAA
樣例輸出
ACM
MCA
AACCMM
CMAAMMMMMM
AAA
AACAAMMM
#include<iostream>
#include<math.h>
#include<string>
#define MAX 1001
using namespace std;
struct node
{
char ch[10001];
int l;
int c;
};
struct node str[MAX];
int f(const void *a,const void *b)
{
if(((struct node *)a)->l==((struct node *)b)->l)
return ((struct node *)a)->c-((struct node *)b)->c;
return ((struct node *)a)->l-((struct node *)b)->l ;
}
int main()
{
int i=0,j,n;
//freopen("fuck.txt","r",stdin);
while(scanf("%s",&str[i].ch)!=EOF)
{
getchar();
n=strlen(str[i].ch);
str[i].l=0;
str[i].c=i;
for(j=0;j<n;j++)
{
if(str[i].ch[j]=='A')
str[i].l++;
}
i++;
}
n=i;
qsort(str,n,sizeof(struct node),f);
for(i=0;i<n;i++)
cout<<str[i].ch<<endl;
return 0;
}
1024 01排序
描述
将01串首先按長度排序，長度相同時，按1的個數多少進行排序，1的個數相同時再按ASCII碼值排序。
輸入
輸入資料中含有一些01串，01串的長度不大于256個字元。
輸出
重新排列01串的順序。使得串按基本描述的方式排序。
樣例輸入
10011111
00001101
1010101
1
1100
樣例輸出
1
1100
1010101
00001101
10011111
#include<iostream>
using namespace std;
bool f(char *p1,char *p2)
{
int len1,num1,num2,i;
num1=num2=0;
if(strlen(p1)>strlen(p2))
return true;
else
if(strlen(p1)<strlen(p2))
return false;
else
{
len1=strlen(p1);
for(i=0;i<len1;i++)
{
num1+=p1[i]-'0';
num2+=p2[i]-'0';
}
if(num1>num2)
return true;
else
{
if(num1<num2)
return false;
else
{
if(strcmp(p1,p2)<0)
return true;
else
return false;
}
}
}
}
int main()
{
int i=0;
int j,n;
char temp[280];
char str[2000][280];
while(scanf("%s",&str[i])!=EOF)
{
i++;
}
n=i;
for(i=n-1;i>=0;i--)
{
for(j=0;j<i;j++)
{
if(f(str[j],str[j+1]))
{
strcpy(temp,str[j]);
strcpy(str[j],str[j+1]);
strcpy(str[j+1],temp);
}
}
}
for(i=0;i<n;i++)
{
cout<<str[i]<<endl;
}
return 0;
}
1025 完數
描述
自然數中，完數寥若晨星，請在從1到某個整數範圍中列印出所有的完數來。所謂“完數”是指一個數恰好等于它的所有不同因子之和。例如，6是完數，因為6=1+2+3。而24不是完數，因為24≠1+2+3+4+6+8+12＝36。
輸入
輸入資料中含有一些整數n（1＜n＜10000）。
輸出
對于每個整數n，輸出所有不大于n的完數。每個整數n的輸出由n引導，跟上冒号，然後是由空格開道的一個個完數，每個n的完數清單應占獨立的一行。
樣例輸入
100
5000
樣例輸出
100: 6 28
5000: 6 28 496
#include<iostream>
using namespace std;
int main()
{
int n;
while(scanf("%d",&n)!=EOF)
{
if(n>=8128)
cout<<n<<": 6 28 496 8128"<<endl;
else
if(n>=496)
cout<<n<<": 6 28 496"<<endl;
else
if(n>=28)
cout<<n<<": 6 28"<<endl;
else
if(n>=6)
cout<<n<<": 6"<<endl;
else
cout<<n<<":"<<endl;
}
return 0;
}
1026 五位以内對稱素數
描述
判斷一個數是否為對稱且不大于五位數的素數。
輸入
輸入資料含有不多于50個的正整數(0<n<2^32)。
輸出
對于每個n，如果該數是不大于五位數的對稱素數，則輸出“Yes”，否則輸出“No”。每個判斷結果單獨列一行。
樣例輸入
11 101 272
樣例輸出
Yes
Yes
No
#include<iostream>
using namespace std;
bool H[100000];
int str[115]={2,3,5,7,11,101,131,151,181,191,313,353,373,383,727,757,787,797,919,929,10301,10501,10601,11311,11411,12421,12721,12821,13331,13831,13931,14341,14741,15451,15551,16061,16361,16561,16661,17471,17971,18181,18481,19391,19891,19991,30103,30203,30403,30703,30803,31013,31513,32323,32423,33533,34543,34843,35053,35153,35353,35753,36263,36563,37273,37573,38083,38183,38783,39293,70207,70507,70607,71317,71917,72227,72727,73037,73237,73637,74047,74747,75557,76367,76667,77377,77477,77977,78487,78787,78887,79397,79697,79997,90709,91019,93139,93239,93739,94049,94349,94649,94849,94949,95959,96269,96469,96769,97379,97579,97879,98389,98689};
void f()
{
for(int i=0;i<115;i++)
{
H[str[i]]=1;
}
}
int main()
{
int flag,i,a;
f();
while(scanf("%d",&a)==1)
{
if(H[a])
printf("Yes\n");
else
printf("No\n");
}
return 0;
}
小結 : ~~又是打表,還是手打的..
之後的題目,挑有的說的慢慢更新~
![南郵 OJ 1308 背包問題[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)