算法訓(xùn)練普通試題

試題編號(hào)ALGO-101

算法訓(xùn)練圖形顯示

問(wèn)題描述

編寫(xiě)一個(gè)程序，首先輸入一個(gè)整數(shù)，例如5,然后在屏幕上顯示如下的圖形（5表示行

數(shù)）：

*****

****

***

**

本題的C++參考代碼如下:

#include<iostream>

usingnamespacestd;

intmain()

(

intn;

cin?n;

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

for(intj=I；j<=n-i;j++)

(

cout?"*"；

if(j<n-i)

cout?

else

cout?endl;

)

return0;

本題的c參考代碼如下:

#include<stdio.h>

intmain()

{inti,j,allOOJllOOJ,n;

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

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

for(j=0;j<n-i;j++)

(

printf("*")；

if(j!=n-i-l)

printf(”")；

if(j==n-l-i)

printf("\n");

)

試題編號(hào)ALGO-97

算法訓(xùn)練排序

問(wèn)題描述

編寫(xiě)一個(gè)程序，輸入3個(gè)整數(shù)，然后程序?qū)?duì)這三個(gè)整數(shù)按照從大到小進(jìn)行排列。

輸入格式：輸入只有一行，即三個(gè)整數(shù)，中間用空格隔開(kāi)。

輸出格式：輸出只有一行，即排序后的結(jié)果。

輸入輸出樣例

樣例輸入

9230

樣例輸出

3092

本題的C++參考代碼如下：

#include<iostream>

usingnamespacestd;

intmain()

(

inta,b,t,c;

while(cin?a?b?c)

(

if(a<b)

(

t=a;a=b;b=t;

)

if(a<c)

(

t=a;a=c;c=t;

)

if(b<c)

(

t=b;b=c;c=t;

)

cout?a?',?b?,,?c?endl;

return0;

本題的c參考代碼如下：

#include<stdio.h>

#include<stdlib.h>

#definenum100

intmain(void)

(

inti,j,t,a[3]={0};

for(i=0;i<3;i++)

{scanf("%dM,&a[iJ);

)

for(i=0;i<3;i++)

for(j=i;j<3;j++)

if(a[i]<=a[j]){t=a[i];a[i]=a[j];a[j]=t;}

for(i=0;i<3;i++)

{printf("%dn,a[i]);

if(i!=2)printf("'1);

)

printf(M\n");

return0;

試題編號(hào)ALGO-95

算法訓(xùn)練2的次塞表示

問(wèn)題描述

任何一個(gè)正整數(shù)都可以用2進(jìn)制表示，例如：137的2進(jìn)制表示為10001001。

將這種2進(jìn)制表示寫(xiě)成2的次第的和的形式,令次事高的排在前面,可得到如下表達(dá)式:

137=2A7+2A3+2A0

現(xiàn)在約定寒次用括號(hào)來(lái)表示，即Sb表示為a(b)

此時(shí)，137可表示為：2(7)+2(3)+2(0)

進(jìn)一步：7=2人2+2+2入0(27用2表示)

3=2+2人0

所以最后137可表示為：2(2(2)+2+2(0))+2(2+2(0))+2(0)

又如：1315=2八10+2八8+2A5+2+1

所以1315最后可表示為：

2(2(2+2(0))+2)+2(2(2+2(0)))+2(2(2)+2(0))+2+2(0)

輸入格式

正整數(shù)(l<=n<=20000)

輸出格式

符合約定的n的0,2表示(在表示中不能有空格)

樣例輸入

137

樣例輸出

2(2(2)+2+2(0))+2(2+2(0))+2(0)

樣例輸入

1315

樣例輸出

2(2(2+2(0))+2)+2(2(2+2(0)))+2(2(2)+2(0))+2+2(0)

提示

用遞歸實(shí)現(xiàn)會(huì)比較簡(jiǎn)單，可以一邊遞歸一邊輸出

本題的C++參考代碼如下:

#include<iostream>

usingnamespacestd;

〃遞歸實(shí)現(xiàn)思路是先轉(zhuǎn)換成二進(jìn)制

intfun(intn)

inti=0;

inta[20]={0};

intm=n;

while(m)

{

a[i]=m%2;

m/=2;

i++；

)

for(intj=i-l;j>=O;j-)//高位到低位排列但是要注意每位的權(quán)改變

(

if(a|j]=l)

(

〃若是最后一個(gè)1則之后不要加號(hào)

intflag=l;

for(intk=j-l;k>=O;k—)

(

if(a[k]==l)

(

flag=O;

break;

}

)

if(flag)〃是最后一位

(

if(j==l)

cout?H2";

else

(

if(j==O)

coutvv"2(“vvj?")”；

else

(

cout?"2(";

fun(j);

cout?")M;

)

else〃不是最后一位

(

ifg)

cout?',2+M;

else

if)

cout?H2(n?j?n)+u;

else

(

cout?n2(M;

fun(j);

cout?")+";

)

return0;

I

intmain()

(

intn;

cin?n;

fun(n);

cout?endl;

return0;

本題的c參考代碼如下：

#include<stdio.h>

int1=0;

chartemp[1000]={0};

voidshow(intn)

(

if(n==0){temp[l]=,0,;l++;retum;)

if(n==2){temp[l]=,2,,l+4-;return;}

inta[15]={0},i=0,j;

while(n!=0)

(

a[i]=n%2;

n/=2;

i++；

)

for(j=i-l；j>=0;j-)

if(a[j]==l)

if(j==D

(

if(temp[l-l]==')'IItemp[l-l]=='2,){temp[l]='+,;l++;}

temp[l]=,2,;l++;

)

else

(

if(temp[l-l]==')'IItemp[l-l]=='2'){temp[l]='+';l++;}

temp[l]='2,;l++;

temp[l]=,(,;l++;

show(j);

temp[l]=,),;l++;

intmain()

(

intn;

scanf("%d",&n);

show(n);

printf(M%s,temp);

return0;

試題編號(hào)ALGO-92

算法訓(xùn)練前綴表達(dá)式

問(wèn)題描述

編寫(xiě)一個(gè)程序，以字符串方式輸入一個(gè)前綴表達(dá)式，然后計(jì)算它的值。輸入格式為：“運(yùn)

算符對(duì)象1對(duì)象2”，其中，運(yùn)算符為“+”（加法）、（減法）、“*”（乘法）或

“/”（除法），運(yùn)算對(duì)象為不超過(guò)10的整數(shù)，它們之間用一個(gè)空格隔開(kāi)。要求：對(duì)于加、

減、乘、除這四種運(yùn)算，分別設(shè)計(jì)相應(yīng)的函數(shù)來(lái)實(shí)現(xiàn)。

輸入格式：輸入只有一行，即一個(gè)前綴表達(dá)式字符串。

輸出格式：輸出相應(yīng)的計(jì)算結(jié)果（如果是除法，直接采用c語(yǔ)言的“/”運(yùn)算符，結(jié)果

為整數(shù)）。

輸入輸出樣例

樣例輸入

+52

樣例輸出

7

本題的C++參考代碼如下：

#include<iostream>

usingnamespacestd;

intmain（）

（

charc;

inta,b;

cin?c?a?b;

intres;

if（c==,+,）res=a+b;

elseif（c==,-,）res=a-b;

elseif（c=='*'）res=a*b;

elseres=a/b;

cout?res;

return0;

本題的c參考代碼如下:

#include<stdio.h>

intmain()

{inta[2];

inti,j;

charc=getchar();

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

scanfC'%dn,&a[i]);

if(c==,+')

j=a[O]+a[l];

elseif(c==-*)

j=a[O]-a[l];

elseif(c==,*1)

j=a[O]*a[l];

elseif(c=='/')

j=a[O]/a[l];

printf("％d\j);

retum0;

)

試題編號(hào)ALGO-91

算法訓(xùn)練Anagrams問(wèn)題

問(wèn)題描述

Anagrams指的是具有如下特性的兩個(gè)單詞：在這兩個(gè)單詞當(dāng)中，每一個(gè)英文字母（不

區(qū)分大小寫(xiě)）所出現(xiàn)的次數(shù)都是相同的。例如，“Unclear”和“Nuclear"、“Rimon”和“MinOR”

都是Anagramso編寫(xiě)一個(gè)程序,輸入兩個(gè)單詞，然后判斷一下，這兩個(gè)單詞是否是Anagrams?

每一個(gè)單詞的長(zhǎng)度不會(huì)超過(guò)80個(gè)字符，而且是大小寫(xiě)無(wú)關(guān)的。

輸入格式：輸入有兩行，分別為兩個(gè)單詞。

輸出格式：輸出只有一個(gè)字母Y或N,分別表示Yes和No。

輸入輸出樣例

樣例輸入

Unclear

Nuclear

樣例輸出

Y

本題的C++參考代碼如下:

#include<iostream>

#include<cmath>

#include<string>

#include<windows.h>

#include<stack>

#include<vector>

#include<iomanip>

#include<stack>

#include<set>

#include<map>

usingnamespacestd;

charGetCapital(charc)

(

if(c<=,Z,)

returnc;

else

return

)

intmain(intargc,char**argv){

map<char,int>a,b;

stringt;

cin?t;

for(inti=O;i<t.length();i++)

a[GetCapital(t[i])]++;

cin?t;

for(inti=O;i<t.length();i++)

b[GetCapital(t[i])]++;

if(a==b)

cout?uYn;

else

cout?uNn;

return0;

}

本題的c參考代碼如下：

#include<stdio.h>

voidsort(chara[],intlen)

(

inti,j,max;

for(i=0;i<len;i++)

(

max=i;

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

if(a[j]>a[max])max=j;

j=a[i];a[i]=a[max];a[max]=j;

)

)

voidstrtoupper(chara[],intlen)

(

inti;

for(i=0;i<len;i++)

if(a[i]>='a'&&a[i]<=,z')a[i]-=32;

)

intmystrcmp(chara[],int11,charb[],int12)

(

if(ll!=12)return0;

inti;

for(i=0;i<ll;i++)

if(a[i]!=b[i])return0;

return1;

intmystrlen(char*p)

{

int1=0;

while(*p++!=0)

1++;

return1;

}

intmain()

(

charsl[l000]={0},s2[l000]={0};

int11,12;

scanf(H%s%s",sl,s2);

ll=mystrlen(sl);

12=mystrlen(s2);

strtoupper(sl,ll);

strtoupper(s2,12);

sort(sl,ll);

sort(s2,12);

if(mystrcmp(s1,11,s2,12))printf(uYn);

elseprintf(”N")；

return0;

試題編號(hào)ALGO-90

算法訓(xùn)練出現(xiàn)次數(shù)最多的整數(shù)

問(wèn)題描述

編寫(xiě)一個(gè)程序，讀入一組整數(shù)，這組整數(shù)是按照從小到大的順序排列的，它們的個(gè)數(shù)N

也是由用戶輸入的，最多不會(huì)超過(guò)20。然后程序?qū)?duì)這個(gè)數(shù)組進(jìn)行統(tǒng)計(jì)，把出現(xiàn)次數(shù)最多

的那個(gè)數(shù)組元素值打印出來(lái)。如果有兩個(gè)元素值出現(xiàn)的次數(shù)相同，即并列第一，那么只打印

比較小的那個(gè)值。

輸入格式：第一行是一個(gè)整數(shù)N,N￡20；接下來(lái)有N行，每一行表示一個(gè)整數(shù),

并且按照從小到大的順序排列。

輸出格式：輸出只有一行，即出現(xiàn)次數(shù)最多的那個(gè)元素值。

輸入輸出樣例

樣例輸入

5

100

150

150

200

250

樣例輸出

150

本題的C++參考代碼如下:

#include“iostream”

#includeustring"

usingnamespacestd;

inimain()

(

intn;

cin?n;

if(n<=0)return0;

string*a=newstring[n];

inti;

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

cin?a[i];

stringnumber=a[0];

intcount=1;

intflag=1;

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

(

if(a[i].compare(a[i-1])==0)

flag=flag+1;

if(a[i].compare(a[i-1])==0IIi==n-1)

(

if(flag>count)

(

count=flag;

number=a[i-1];

)

flag=1;

)

}

cout?number?endl;

return0;

)

本題的c參考代碼如下：

#include<stdio.h>

intmain()

(

intn,ij,t,max=1,num=0;

scanf("％d”,&n);

if(n>0)

(

inta[n];

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

scanf(n%dn,a+i);

j=num=a[0];

t=l；

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

if(a[i]==j)

(

++t;

if(t>max)

max=t;num=a[i];

else

t=l；

j=a[i]；

)

printf("%d",num);

return0;

}

試題編號(hào)ALGO-87

算法訓(xùn)練字串統(tǒng)計(jì)

問(wèn)題描述

給定一個(gè)長(zhǎng)度為n的字符串S,還有一個(gè)數(shù)字L,統(tǒng)計(jì)長(zhǎng)度大于等于L的出現(xiàn)次數(shù)最多

的子串(不同的出現(xiàn)可以相交)，如果有多個(gè)，輸出最長(zhǎng)的，如果仍然有多個(gè)，輸出第一次

出現(xiàn)最早的。

輸入格式

第一行一個(gè)數(shù)字L。

第二行是字符串So

L大于0,且不超過(guò)S的長(zhǎng)度。

輸出格式

一行，題目要求的字符串。輸入樣例1：

4

bbaabbaaaaa輸出樣例1：

bbaa輸入樣例2：

2

bbaabbaaaaa輸出樣例2：

aa

數(shù)據(jù)規(guī)模和約定

n<=60

S中所有字符都是小寫(xiě)英文字母。提示

枚舉所有可能的子串，統(tǒng)計(jì)出現(xiàn)次數(shù)，找出符合條件的那個(gè)

本題的C++參考代碼如下：

#include<cstdio>

#include<cstring>

intmain()

chars[65],str[65];

intmax=O,t,n,len;

scanf(u%d%sn,&n,s)；

len=strlen(s);

if(n<=len)

(

charss[65],tt[65];

for(inti=len;i>=n;i-)

(

ss[i]=tt[i]=^r;

for(intj=O;j<=len-i;j++)

(

t=l；

for(intk=O;k<i;k++)

ss[k]=s[k+j]；

for(intx=j+1;x<=len-i;x++)

(

for(inty=O;y<i;y++)

tt[y]=s[y+x];

if(strcmp(ss,tt)==O)

t++；

)

if(t>max)

(

max=t;

strcpy(str,ss);

//printf(M%s\nn,str);

)

}

)

printf(H%s\nH,str);

本題的c參考代碼如下：

#include<stdio.h>

#include<string.h>

intmain(){

charS[1OOO],str[l000][1000],temp[l00],out[100];

intL,i=0,s,otongji=0,ttongji,a,b,c;

scanf("%d%c%c,\&L,&S[0],&S[0]);

while(S[i]!=\n!){

scanf(n%cM,&S[i+l]);

i++;

sm=vr；

for(s=i+l;L<=s;L++){

for(a=0;a<s+1-L;a++){〃賦值

for(b=0;b<L;b++){

str[a][b]=S[a+b];

)

str[a][b]=W;

for(i=0;i<a-l;){〃比較

for(b=O;b<a;b++){

if(str[b][O]!='\O'){

for(c=O;c<L;c++){

temp[c]=str[b][c];

)

temp[c]='\0";

ttongji=1;

i++；

str[b][0]=V)';

break;

)

)

for(b++;b<a;b++){

if(!strcmp(str[b],temp)){

ttongji++;

i++；

str[b][01='0';

if(ttongji>

otongjill(ttongji==otongji&&strlen(temp)>strlen(out))){

strcpy(out,temp);

otongji=ttongji;

)

)

i=0;

while(out[i]!=W){

printf("%c”,out[i]);

i++；

getchar();

return0;

)

試題編號(hào)ALGO-86

算法訓(xùn)練矩陣乘法

問(wèn)題描述

輸入兩個(gè)矩陣，分別是m*s,s*n大小。輸出兩個(gè)矩陣相乘的結(jié)果。

輸入格式

第一行，空格隔開(kāi)的三個(gè)正整數(shù)m,s,n(均不超過(guò)200)。

接下來(lái)m行，每行s個(gè)空格隔開(kāi)的整數(shù)，表示矩陣A(i,j)o

接下來(lái)s行，每行n個(gè)空格隔開(kāi)的整數(shù)，表示矩陣B(i,j)o

輸出格式

m行，每行n個(gè)空格隔開(kāi)的整數(shù)，輸出相乘彳爰的矩陣C(i,j)的值。

樣例輸入

232

10-1

11-3

03

12

31

樣例輸出

-32

-82

提示

矩陣C應(yīng)該是m行n歹U,其中C(i,j)等于矩陣A第i行行向量與矩陣B第j列列向量的內(nèi)積。

例如樣例中C(l,1)=(1,0,-1)*(0,1,3)=1*0+0*1+(-1)*3=3

本題的C++參考代碼如下:

#include<stdio.h>

#include<string.h>

#include<stdlib.h>

#include<ctype.h>

intmain()

(

intm,s,n;

intsum=0;

int

inta[200][200],b[200][200],c[200][200];

scanf("%d%d%d",&m,&s,&n);

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

(

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

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

I

for(i=0;i<s;i++)

{

for(j=0；j<n;j++)

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

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

(

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

(

for(l=0;l<s;l++)

(

sum+=(a[i][l]*b[l]|j]);

)

c[i]|j]=sum;

sum=0;

)

)

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

(

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

printf("%d",c[i][j]);

printf("\n");

I

return0;

本題的c參考代碼如下：

#include<stdio.h>

intmain(){

intm,s,n,ij,k,a[200][200],b[200][200],c[200][200];

scanf(H%d%d%dM,&m,&s,&n);

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

for(j=l;j<=s;j++)

scanf(n%dM,&a[i][j]);

for(i=l;i<=s;i++){

for(j=l;j<=n;j++)

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

)

for(i=l;i<=m;i++){

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

c[i][j]=O;

}

for(i=l;i<=m;i++){

for(j=l;j<=n;j++){

for(k=1;k<=s;k++){

c[i][j]=c[i][j]+a[i][k]*b[k][j];

)

)

I

for(i=l;i<=m;i++){

for(j=l;j<=n;j++)

printf("%d",c[i][j])；

printf("\n");

return0;

試題編號(hào)ALGO-84

算法訓(xùn)練大小寫(xiě)轉(zhuǎn)換

問(wèn)題描述

編寫(xiě)一個(gè)程序，輸入一個(gè)字符串（長(zhǎng)度不超過(guò)20）,然后把這個(gè)字符串內(nèi)的每一個(gè)字

符進(jìn)行大小寫(xiě)變換，即將大寫(xiě)字母變成小寫(xiě)，小寫(xiě)字母變成大寫(xiě)，然后把這個(gè)新的字符串輸

出。

輸入格式：輸入一個(gè)字符串，而且這個(gè)字符串當(dāng)中只包含英文字母，不包含其他類型的

字符，也沒(méi)有空格。

輸出格式：輸出經(jīng)過(guò)轉(zhuǎn)換后的字符串。

輸入輸出樣例

樣例輸入

AeDb

樣例輸出

aEdB

本題的C++參考代碼如下:

#include<iostream>

#include<string>

usingnamespacestd;

intmain()

(

stringstr;

cin?str;

unsignedi;

for(i=0;i<str.size();i++)

(

if(str[i]>=,A,&&str[i]<=,Z')

str[i]+=32;

elseif(str[i]>=,a'&&str[i]<=,z')

str[i]-=32;

)

cout?str;

return0;

本題的c參考代碼如下:

#include<stdio.h>

intmain()

(

inti;

charchflOO];

gets(ch);

i=0;

while(ch[i]!=,\O')

(

if(ch[i]<=,z'&&ch[i]>=,a')

ch[i]-=32;

elsech[iJ+=32;

i++；

)

puts(ch);

return0;

)

試題編號(hào)ALGO-81

算法訓(xùn)練動(dòng)態(tài)數(shù)組使用

從鍵盤(pán)讀入n個(gè)整數(shù)，使用動(dòng)態(tài)數(shù)組存儲(chǔ)所讀入的整數(shù)，并計(jì)算它們的和與平均值分別輸出。

要求盡可能使用函數(shù)實(shí)現(xiàn)程序代碼。平均值為小數(shù)的只保留其整數(shù)部分。

樣例輸入

34002

樣例輸出

91

樣例輸入

7

3275291

樣例輸出

294

本題的C++參考代碼如下:

#include<iostream>

usingnamespacestd;

intmain()

(

intn,a,sum=0;

cin?n;

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

(

cin?a;

sum+=a;

)

cout?sum?nU?sum/n?endl;

return0;

本題的c參考代碼如下:

#include<stdio.h>

intmain()

inti,n,a[100],b[100],sum=0,avg=0;

scanf(H%d'\&n);

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

(

scanf("%dn,&b[i]);

a[i]=b[i];

sum=sum+a[i];

)

avg=sum/n;

printf("%d%d\n”,sum,avg);

return0;

試題編號(hào)ALGO-79

算法訓(xùn)練刪除數(shù)組零元素

從鍵盤(pán)讀入n個(gè)整數(shù)放入數(shù)組中，編寫(xiě)函數(shù)Compactintegers,刪除數(shù)組中所有值為0的元

素，其后元素向數(shù)組首端移動(dòng)。注意，Compactintegers函數(shù)需要接受數(shù)組及其元素個(gè)數(shù)作

為參數(shù)，函數(shù)返回值應(yīng)為刪除操作執(zhí)行后數(shù)組的新元素個(gè)數(shù)。輸出刪除后數(shù)組中元素的個(gè)數(shù)

并依次輸出數(shù)組元素。樣例輸入：（輸入格式說(shuō)明：5為輸入數(shù)據(jù)的個(gè)數(shù)，34002是

以空格隔開(kāi)的5個(gè)整數(shù)）

5

34002

樣例輸出：（輸出格式說(shuō)明：3為非零數(shù)據(jù)的個(gè)數(shù)，342是以空格隔開(kāi)的3個(gè)非零整數(shù)）

3

342

樣例輸入

7

0070090

樣例輸出

2

79

樣例輸入

3

000

樣例輸出

0

本題的C++參考代碼如下:

#include"iostream”

usingnamespacestd;

intmain()

intn;

int*arr;

cin?n;

arr=newintfn];

intnum=0;

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

(

cin?arr[i];

if(arr[i]!=0)

(

++num;

)

)

cout?num?endl;

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

(

if(arr[i]==0)

(

continue;

)

cout?arr[i]?Mu;

)

return0;

)

本題的c參考代碼如下:

#includeustdio.h"

intCompactlntegers(inta[],intlen)

(

inti,j,k;

for(k=0;k<len;k++)

for(i=0;i<len;i++)

(

if(a[i]==0)

(

for(j=i;j<len-l;j++)

a[j]=a[j+l];

len—;

returnlen;

voidprint(intaf],intlen)

(

inti;

for(i=0;i<len;i++)

printf(M%d",a[i]);

printf(n\nu);

)

intmain()

(

inta[100000];

intn;

scanf("％d”,&n);

inti;

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

scanf("％d”,&a[i]);

intlen=Compactlntegers(a,n);

if(len>l)

(

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

print(a,len);

}

else

printf("%dn,0);

getchar();

getchar();

getchar();

return0;

試題編號(hào)ALGO-53

算法訓(xùn)練最小乘積(基本型)

問(wèn)題描述

給兩組數(shù)，各n個(gè)。

請(qǐng)調(diào)整每組數(shù)的排列順序，使得兩組數(shù)據(jù)相同下標(biāo)元素對(duì)應(yīng)相乘，然后相加的和最小。

要求程序輸出這個(gè)最小值。

例如兩組數(shù)分別為:13-5和-241

那么對(duì)應(yīng)乘積取和的最小值應(yīng)為：

(-5)*4+3*(-2)+1*1=-25

輸入格式

第一個(gè)行一個(gè)數(shù)T表示數(shù)據(jù)組數(shù)。后面每組數(shù)據(jù)，先讀入一個(gè)n,接下來(lái)兩行每行n個(gè)

數(shù)，每個(gè)數(shù)的絕對(duì)值小于等于1000。

n<=8,T<=1000

輸出格式

一個(gè)數(shù)表示答案。

樣例輸入

2313-5-24151234510101

樣例輸出

-256

本題的C++參考代碼如下：

#include<iostream>

#include<algorithm>

usingnamespacestd;

inta[8],b[8];

intmain()

(

intT,n;

inti,j;

cin?T;

while(T—)

(

intsum=O;

cin?n;

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

cin?a[i];

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

cin?b[i];

sort(a,a+n);

sort(b,b+n);

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

(

sum+=a[i]*b[n-l-i];

}

cout?sum?endl;

)

return0;

本題的c參考代碼如下:

#include<stdio.h>

voidsort1(int*a,intn)

(

inti,j;

inttmp;

for(i=0;i<n-l;i++)

for(j=0;j<n-1-i；j++)

if(aU]>a[j+l])

(

tmp=a[j];

a[j]=a[j+l];

a[j+l]=tmp;

}

(

voidsort2(int*a,intn)

(

inti,j;

inttmp;

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

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

if(aU]<aU+l])

tmp=a[j];

a[j]=a[j+l];

a[j+l]=tmp;

)

)

intmain(void)

(

intT;

intn,i;

inttotal;

inta[8],b[8],c[8];

scanf(u%d'\&T);

while(T)

(

total=0;

scanf(u%dn,&n);

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

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

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

scanf("%dH,&b[i]);

sortl(a,n);

sort2(b,n);

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

c[ij=alij*b[i];

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

total+=clij;

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

T-；

return0;

試題編號(hào)ALGO-51

算法訓(xùn)練Torry的困惑（基本型）

問(wèn)題描述

Torry從小喜愛(ài)數(shù)學(xué)。一天，老師告訴他，像2、3、5、7……這樣的數(shù)叫做質(zhì)數(shù)。Torry

突然想到一個(gè)問(wèn)題，前10,100,1000,10000……個(gè)質(zhì)數(shù)的乘積是多少呢?他把這個(gè)問(wèn)題

告訴老師。老師愣住了，一時(shí)回答不出來(lái)。于是Torry求助于會(huì)編程的你，請(qǐng)你算出前n個(gè)

質(zhì)數(shù)的乘積。不過(guò)，考慮到你才接觸編程不久，Torry只要你算出這個(gè)數(shù)模上50000的值。

輸入格式

僅包含一個(gè)正整數(shù)儲(chǔ)其中n<=l00000?

輸出格式

輸出一行，即前n個(gè)質(zhì)數(shù)的乘積模50000的值。

樣例輸入

1

樣例輸出

2

本題的C++參考代碼如下:

#include<iostream>

usingnamespacestd;

inta[100005];

intmain()

(

unsignedinti,j,n,ent=1,cj=2;

cin?n;

if(n==1)

(

cout?2?endl;

return0;

)

alOJ=2;

for(i=3;i<2000000;i++)

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

if(aU]*a[j]>i)

(

break;

)

else

(

if(!(i%aUD)

(

break;

if(aU]*a[j]>i)

(

a[cnt++]=i;

cj=(cj%50000)*(i%50000);

if(ent==n)

(

break;

}

)

)

cout?cj%50000?endl;

return0;

)

本題的c參考代碼如下：

#include<stdio.h>

intpr[100010];

inttop;

intisPrime(intn)

(

inti;

for(i=0;i<top;i++)

(

if(n%pr[i]==0)

(

return0;

return1;

intfindNextPrime(void)

intn=pr[top-1]+1;

while(!isPrime(n))

(

n++;

)

pr[top++]=n;

returnn;

)

intmain(void)

(

inti,n;

intresult=2;

scanf(u%d",&n);

pr[O]=2;

top=1;

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

{

intx=findNextPrime();

result*=x;

result%=50000;

prinlf("%d",result);

return0;

)

試題編號(hào)ALGO-49

算法訓(xùn)練尋找數(shù)組中最大值

問(wèn)題描述

對(duì)于給定整數(shù)數(shù)組a[],尋找其中最大值，并返回下標(biāo)。

輸入格式

整數(shù)數(shù)組an,數(shù)組元素個(gè)數(shù)小于1等于100。輸出數(shù)據(jù)分作兩行：第一行只有一個(gè)數(shù),

表示數(shù)組元素個(gè)數(shù)：第二行為數(shù)組的各個(gè)元素。

輸出格式

輸出最大值，及其下標(biāo)

樣例輸入

3321

樣例輸出

30

本題的C++參考代碼如下:

#include<iostream>

#include<algorithm>

#include<cstring>

usingnamespacestd;

inimain(){

intn,a[1000],max,ans;

cin?n;

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

cin?a[i];

max=a[0];ans=0;

for(inti=l;i<n;i++){

if(a[i]>max){

max=a[i];

ans=i;

)

)

cout?max?M"?ans;

return0;

本題的c參考代碼如下:

#include<stdio.h>

inimain()

(

intn,i,k,max;

scanf(n%dH,&n);

inta[n];

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

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

max=a[O];

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

{

if(a[i]>=max)

(

max=a[i];

k=i;

)

)

printf(n%d%d'\max,k);

return0;

)

試題編號(hào)ALGO-48

算法訓(xùn)練關(guān)聯(lián)矩陣

問(wèn)題描述

有一個(gè)n個(gè)結(jié)點(diǎn)m條邊的有向圖，請(qǐng)輸出他的關(guān)聯(lián)矩陣。

輸入格式

第一行兩個(gè)整數(shù)n、m,表示圖中結(jié)點(diǎn)和邊的數(shù)目。n<=100,m<=1000o

接下來(lái)m行，每行兩個(gè)整數(shù)a、b,表示圖中有(a,b)邊。

注意圖中可能含有重邊，但不會(huì)有自環(huán)。

輸出格式

輸出該圖的關(guān)聯(lián)矩陣，注意請(qǐng)勿改變邊和結(jié)點(diǎn)的順序。

樣例輸入

59

12

31

15

25

23

23

32

43

54

樣例輸出

1-11000000

-100111-100

0100-1-11-10

00000001-1

00-1-100001

本題的C++參考代碼如下:

#include<iostream>

#include<cstdio>

usingnamespacestd;

intans[101][1001];

intmain()

intn,m;

inta,b;

cin?n?m;

for(inti=l；i<=m;i++)

(

scanf("%d%dH,&a,&b);

ans[a][i]=1;

ans[b][i]=-1;

)

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

(

for(intj=1;j<=m-l;j++)

(

printf(n%d",ans[i][j]);

}

printf(H%d\n",ans[i][m]);

}

return0;

)

本題的c參考代碼如下:

#include<stdio.h>

intmain()

(

inti,ii,n,m,a[1000][2];

scanf(^'%d%d',,&n,&m);

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

scanf(u%d%d",&a[i][0],&a[i][l]);

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

(

for(ii=0;ii<m;ii++)

(

if(i==a[ii][0])

(

printf("l");

}

else

if(i==a[ii][l])

printf("-l");

)

else

(

printf("O");

)

printfC^n1');

return0;

試題編號(hào)ALGO-42

算法訓(xùn)練送分啦

問(wèn)題描述

這題想得分嗎？想，請(qǐng)輸出“yes”；不想，請(qǐng)輸出“no”.

輸出格式

輸出包括一行，為“yes”或“no”。

本題的C++參考代碼如下：

#include<cstdio>

#include<cstring>

usingnamespacestd;

intmain()

(

printf(Hyes\nM);

return0;

)

本題的c參考代碼如下：

#include<stdio.h>

#include<stdio.h>

intmain()

(

printf("yes\n");

return0;

試題編號(hào)ALGO-8

算法訓(xùn)練操作格子

問(wèn)題描述

有n個(gè)格子，從左到右放成一排，編號(hào)為1-n。

共有m次操作，有3種操作類型：

1.修改一個(gè)格子的權(quán)值，

2.求連續(xù)一段格子權(quán)值和，

3.求連續(xù)一段格子的最大值。

對(duì)于每個(gè)2、3操作輸出你所求出的結(jié)果。

輸入格式

第一行2個(gè)整數(shù)n,m。

接下來(lái)一行n個(gè)整數(shù)表示n個(gè)格子的初始權(quán)值。

接下來(lái)m行，每行3個(gè)整數(shù)p,x,y,p表示操作類型，p=l時(shí)表示修改格子x的權(quán)值為

y,p=2時(shí)表示求區(qū)間［x,y］內(nèi)格子權(quán)值和，p=3時(shí)表示求區(qū)間［x,y］內(nèi)格子最大的權(quán)值。

輸出格式

有若干行，行數(shù)等于p=2或3的操作總數(shù)。

每行1個(gè)整數(shù)，對(duì)應(yīng)了每個(gè)p=2或3操作的結(jié)果。

樣例輸入

43

1234

213

143

314

樣例輸出

6

3

數(shù)據(jù)規(guī)模與約定

對(duì)于20%的數(shù)據(jù)nv=100,m<=200。

對(duì)于50%的數(shù)據(jù)n<=5000,m<=5000o

對(duì)于100%的數(shù)據(jù)1<=n<=100000,m<=100000,0<=格子權(quán)值<=10000?

本題的C++參考代碼如下：

//test

//l.cpp

/*

ID:Firwaless

LANG:C++

TASK:

*/

#include<cstdio>

#include<algorithm>

structTree

(

intsum,max;

)；

Treetree[l?18];

voidscan(int&n)

(

chare;

c=getchar();

if(c==EOF){

return;

)

while(c<OIIc>9){

c=getchar();

)

n=c-O;

while(c=getchar(),c>='O'&&c<=*9'){

n*=10;

n+=c-'0*;

voidput(intn)

(

intent=0;

chars[16];

if(n==0){

putcharCO1);

return;

)

for(;n;n/=10){

s[cnt++]=n%10+*0';

)

while(ent—){

putchar(s[cnt]);

)

)

voidupdate(intn,intv)

(

for(n+=(1?17),tree[n].sum=tree[n].max=v,n?=1;n;n?=1){

tree[n].max=std::max(tree[n+n].max,tree[n+n+l].max);

tree[n].sum=tree[n+n].sum+tree[n+n+l].sum;

)

)

intquery(ints,intt,intfunc)

(

intsum=0,max=0;

for(s+=(1?17)-l,t+=(l?17)+l；sAtAl;s?=1,t?=1){

if(~s&1){

sum+=tree[sAIJ.sum;

max=std::max(max,tree[s八l].max);

)

if(t&1){

sum+=tree[tA1J.sum;

max=std::max(max,tree[tAl].max);

returnfunc?max:sum;

intmain()

intn,m,i,a,b,c;

scan(n);scan(m);

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

scan(a);

update(i,a);

)

while(m—){

scan(c);scan(a);scan(b);

c==1&&(update(a,b),0);

c==2&&(put(query(a,b,0)),putchar(1\nr),0);

c==3&&(put(query(a,b,1)),putcharCXn1),0);

)

return0;

}

本題的c參考代碼如下：

#include<stdio.h>

#defineN100000

#defineA1000

#defineB100

intsum(int*a,intm,intn)

(

inti,s=0;

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

s+=a[i];

returns;

)

intmax(int*a,intm,intn)

(

inti,s=a[m];

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

if(s<a[i])

s=a[i];

returns;

)

intmain()

inti,j,k,m,n;

inta[100000],b[100000][3],c[A][2]={0};

scanf("%d%d",&n,&m);

for(i