当前位置：文档库 › acm入门基础题解一_New

acm入门基础题解一_New

acm入门基础题解一

Problem A: 数字三角形

#include

const int maxn=110;

int a[maxn][maxn],b[maxn][maxn],n;

void data_set(){

for(int i=1;i<=n;i++){

for(int j=1;j<=i;j++){

scanf("%d",&a[i][j]);

}

void solve(){

for(int j=1;j<=n;j++)

b[n][j]=a[n][j];

for(int i=n-1;i>=1;i--)

for(int j=1;j<=i;j++){

if(b[i+1][j+1]>b[i+1][j])

b[i][j]=b[i+1][j+1]+a[i][j]; else

b[i][j]=b[i+1][j]+a[i][j]; }

printf("%d\n",b[1][1]);

}

int main(){

while(scanf("%d",&n)!=EOF&&n!=0){

data_set();

solve();

}

return 0;

}

Problem B: 去北京看奥运

#include

const int maxn=110;

const int inf=200000000;

int a[maxn],b[maxn][maxn],dp[maxn][maxn],n;

void data_set(){

for(int j=0;j

for(int k=0;k

dp[k][j]=inf;

dp[0][1]=0;

int s,e,l;

scanf("%d",&n);

a[0]=1;a[n+1]=1;

for(int i=1;i<=n;i++) scanf("%d",&a[i]);

for(int i=0;i<=n;i++){

for(int j=1;j

for(int k=1;k

b[k][j]=inf;

while(1){

scanf("%d",&s);

if(s==0) break;

scanf("%d%d",&e,&l);

b[s][e]=l;

}

for(int j=1;j<=a[i+1];j++){

for(int k=1;k<=a[i];k++){

if(dp[i+1][j]>dp[i][k]+b[k][j]&&b[k][j]!=inf) dp[i+1][j]=dp[i][k]+b[k][j];

}

printf("%d\n",dp[n+1][1]);

}

int main(void){

int t;

scanf("%d",&t);

while(t--)

data_set();

}

Problem C: 计算直线的交点数

#include

using namespace std;

int main()

{

int n,tmp;

set s[21];

s[0].insert(0);

s[1].insert(0);

for(int i=2;i<21;i++)

{

for(int j=0;j

{

set::iterator it;

for(it=s[j].begin();it!=s[j].end();it++) {

tmp=*it+(i-j)*j;

s[i].insert(tmp);

}

while(cin>>n)

{

set::iterator it;

for(it=s[n].begin();it!=s[n].end();it++)

{

if(it!=s[n].begin()) cout<<" ";

cout<<*it;

}

cout<

}

Problem D: 免费馅饼

#include

int a[100050][11];

int main()

{

int i, j, n, p, q, x, m;

while(scanf("%d", &n)!=EOF)

{

if(n==0) break;

m=0;

memset(a, 0, sizeof(a));

for(i=1;i<=n;i++)

{

scanf("%d%d", &q, &p);

a[p][q]++;

if(p>m) m=p;

}

for(i=m;i>=0;i--)

{

for(j=0;j<11;j++)

{

int x=a[i+1][j];

if(j>0&&a[i+1][j-1]>x) x=a[i+1][j-1]; if(j<10&&a[i+1][j+1]>x) x=a[i+1][j+1]; a[i][j]+=x;

}

printf("%d\n", a[0][5]);

}

return 0;

}

Problem E: 地道战

#include

const int maxn=110;

const int inf=200000000;

int n,m,a[maxn][maxn],r[maxn][maxn],d[maxn][maxn];

int min(int a,int b){

return a

}

void data_set(){

for(int i=1;i<=n;i++)

for(int j=1;j

scanf("%d",&r[i][j]);

for(int i=1;i<=m;i++)

for(int j=1;j

scanf("%d",&d[j][i]);

for(int i=0;i<=n;i++)

for(int j=0;j<=m;j++)

a[i][j]=inf;

}

void solve(){

a[1][1]=0;

for(int i=2;i<=m;i++) a[1][i]=a[1][i-1]+r[1][i-1];

for(int i=2;i<=n;i++) a[i][1]=a[i-1][1]+d[i-1][1];

for(int i=2;i<=n;i++){

for(int j=2;j<=m;j++){

a[i][j]=min(a[i][j-1]+r[i][j-1],a[i-1][j]+d[i-1][j]); }

}

printf("%d\n",a[n][m]);

}

int main()

{

while(scanf("%d%d",&n,&m)!=EOF){

data_set();

solve();

}

Problem F: 最长不下降序列

#include

using namespace std;

const int maxn=2000;

int i,j,n,t,x,lmax,a[maxn],b[maxn];

int main(){

int max;

while(scanf("%d",&n)!=EOF){

for(i=1;i<=n;i++)

cin>>a[i];

b[n]=1;

lmax=0;

for(i=n-1;i>=1;i--){

max=0;

for(j=i+1;j<=n;j++)

if(a[i]<=a[j]&&b[j]>max)

max=b[j];

b[i]=max+1;

if(b[i]>lmax) lmax=b[i];

}

cout<

}

return 0;

}

Problem A: Substrings

#include

using namespace std;

bool comp(string str1,string str2){

return str1.length()

string str[112];

int main(){

int t;

cin>>t;

while(t--){

int n;

cin>>n;

int i=0;

for(i=0;i

cin>>str[i];

sort(str,str+n,comp);

string::iterator p1;

string::iterator p2;

string::iterator p0;

int ans=0,max=0;

for(p1=str[0].begin();p1=p1;p2--){

string

ss1=str[0].substr(p1-str[0].begin(),p2-p1+1);

string ss2;

for(string::iterator

it=p2;it>=p1;it--){

ss2+=*it;

}

ans=ss1.length();

int flag=1;

for(i=1;i

int x=str[i].find(ss1);

int y=str[i].find(ss2);

if(x==-1&&y==-1){

flag=0;

break;

}

if(flag==1&&max<=ans)

max=ans;

}

cout<

}

return 0;

}

ProblemB:Calling Extraterrestrial Intelligcn

#include

#define N 100005

using namespace std;

bool no_prim[N];

int m,a,b,p,q;

void primetable()

{

int i,j;

for(i=3;i<317;i+=2)

{

if(no_prim[i]==false)

{

int tmp=i<<1;

for(j=i*i;j

no_prim[j]=true;

}

int main()

{

int i,j;

primetable();

while(scanf("%d%d%d",&m,&a,&b)&&m&&a&&b)

{

p=q=0;

double limit=a*1.0/b;

for(i=2;i<=m;i++)

{

if(!no_prim[i]&&i%2!=0||i==2)

{

for(j=2;j<=i&&i*j<=m;j++)

{

if(!no_prim[j]&&j%2!=0||j==2)

{

if(j*1.0/i>=limit&&i*j>p*q) //i和j的顺序 {

p=j;

q=i;

}

printf("%d %d\n",p,q);

}

return 0;

}

Problem C: 深入浅出学算法028-桥本分数式

#include

int main()

{

int i,k,g,s;

int m1,m2,m3,a[10];

a[1]=1;i=1;g=1;s=0;

while(1)

{

g=1;

for(k=i-1;k>0;k--)

if(a[k]==a[i]) {g=0; break;}

if(i==9 && g==1 && a[1]

m1=a[2]*10+a[3];

m2=a[5]*10+a[6];

m3=a[8]*10+a[9];

if(a[1]*m2*m3+a[4]*m1*m3==a[7]*m1*m2){

s++;

}

if(i<9 &&g==1){i++; a[i]=1; continue;}

while(a[i]==9 && i>1) i--;

if(a[i]==9 && i==1) break;

else a[i]++;

}

printf("%d\n",s);

}

Problem D: 深入浅出学算法029-素数

和环

#include

int main()

{

int t,i,j,n,k,s,a[2000],b[1000];

while(~scanf("%d",&n))

{

for(k=1;k<=2*n;k++) b[k]=0;

for(k=3;k<=2*n;k+=2)

{

for(t=0,j=3;j<=sqrt(k);j+=2)

if(k%j==0)

{

t=1;break;

}

if(t==0) b[k]=1;

}

a[1]=1;s=0;

i=2;a[i]=2;

while(1)

{

t=1;

for(j=1;j

if(a[j]==a[i] || b[a[i]+a[i-1]]!=1) {

t=0;break;

}

if(t && i==n && b[a[n]+1]==1)

{

s++;

}

if(t && i

if(i>1) a[i]++;

else break;}

printf("%d\n",s);

}

return 0;

}