華東師范大學(xué)計(jì)算機(jī)機(jī)試真題VIP

2009機(jī)試2

計(jì)算和的數(shù)位2

大寫改小寫3

素?cái)?shù)對(duì)3

求最大公約數(shù)和最小公倍數(shù)5

排序后求位置處的數(shù)6

*路由器連接8

*編譯原理10

*分開(kāi)連接12

2010機(jī)試16

ECNU的含義16

空瓶換啤酒17

統(tǒng)計(jì)字符18

2010機(jī)試熱身20

粽子買三送一，買五送二20

工程流水線問(wèn)題21

2011機(jī)試22

helloworld22

Specialjudge25

查詢成績(jī)26

2011機(jī)試熱身29

貪吃蛇29

仰望星空32

*編輯距離35

2012機(jī)試37

字母排序37

幸運(yùn)數(shù)37

十六進(jìn)制的加法40

號(hào)碼簿合并排序40

*五子棋41

*止則表達(dá)式匹配43

2013機(jī)試44

斐波那契數(shù)列的素?cái)?shù)個(gè)數(shù)44

*將a字符變成b字符最少修改次數(shù)45

2013機(jī)試熱身47

去重排序47

蛇形圖案49

數(shù)學(xué)手稿51

2009機(jī)試

計(jì)算和的數(shù)位

Sumofdigit

Description

Writeaprogramwhichcorrputesthedigitnumberofsumoftwointegersaandb.

Input

Thefirstlineofinputgivesthenumberofcases,N(1WNW100).Ntestcasesfollow.

Eachtestcaseconsistsoftwointegersaandbwhichareseparetedbyaspaceinaline.

(0<=a,b<=100000000).

Output

Foreachtestcase,printthenumberofdigitsofa+b.

SampleInput

3

57

199

1000999

SampleOutput

2

3

4

#include<stdio.h>

intmain()

(

intn;

inta,b;

intsum;

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

(

while(n-)

(

intan=0;

scanf("%d%d"/&a/&b);

sum=a+b;

while(sum)

(

an++;

sum/=10;

)

printf("%d\n",an++);

)

)

return0;

)

大寫改小寫

Capitalize

Description

Writeaprogramwhichreplaceallthelower-caseletterso:agiventextwiththecorresponding

captitalletters.

Input

Atextincludinglower-caseletters,periods,andspace.

Output

OutputTheconvertedtext.

SampleInput

welcometoeastchinanormaluniversity.

SampleOutput

WELCOMETOEASTCHINANORMALUNIVERSITY.

#include<stdio.h>

#include<string.h>

charstr[1000];

intmain()

(

intI;

while(gets(str))

(

l=strlen(str);

inti;

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

(

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

prindT%c”,str[i]-32);

else

printf(”%c”,str[i]);

)

printf("\n")；

)

return0;

)

素?cái)?shù)對(duì)

PrimpsPair

Description

Wearrangethenumbersbetween1andN(1<=N<=10000)inincreasingorderanddecreasing

orderlikethis:

123456789…N

N...987654321

Twonumbersfacedeachotherformapair.YourtaskistocomputethenumberofpairsPsuch

thatbothnumbersinthepairsareprime.

Input

Thefirstlineofinputgivesthenumberofcases,C(1VC/100).Ctestcasesfollow.

EachtestcaseconsistsofanintegerNinoneline.

Output

Foreachtestcase,outputP.

SampleInput

4

1

4

7

51

SampleOutput

0

2

2

6

#include<stdio.h>

#include<string.h>

boolprime[10005];

voidinit()

(

inti;

intj;

prime[0]=prime[l]=false;〃不是素?cái)?shù)

prime[2]=true;〃是素?cái)?shù)

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

|

prime[i]=true;〃是素?cái)?shù)

prime[i+l]=false;〃不是素?cái)?shù)除0和2之外的偶數(shù)都不是素?cái)?shù)

)

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

(

if(prime[i]==true)〃是素?cái)?shù)

(

j=i+i;

while(j<=10005)

prime[j]=false;〃不是素?cái)?shù)

j+=i；

)

)

}

)

intmain()

(

intc;

intn;

init();〃初始化

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

{

while(c--)

(

scanf("%d"z&n);

intsum=O;

inti;

for(i=2;i<=n^;i++)

(

if(prime[i]==true&&prime[n+l-i]==true)

sum++;

)

sum*=2;

if(n%2==l)//n為奇數(shù)

(

if(prime[n/2+l]==true)

sum+=l;

}

printf("%d\n“,sum);

)

)

return0;

)

求最大公約數(shù)和最小公倍數(shù)

GCDandLCM

Description

Writeaprogramwhichcomputesthegreatestcommondivisor(GCD)andtheleastcommon

multiple(LCM)ofgivenaandb(0<a,bW44000).

Input

Thefirstlineofinputgivesthenumberofcases,N(1WNW100).Ntestcasesfollow.

Eachtestcasecontainstwoimergeraandbseparatedbyasinglespaceinaline.

Output

Foreachtestcase,printGCDandLCMseparatedbyasinglespaceinaline.

SampleInput

2

86

50003000

SampleOutput

224

100015000

#include<stdio.h>

intgetgcd(intajntb)

(

intgcd;

inttl,t2;

tl=a;

t2=b;

gcd=tl%t2;

while(gcd!=0)

(

tl=t2;

t2=gcd;

gcd=tl%t2;

)

returnt2;

)

intmain()

{

intn;

inta,b;

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

(

while(n-)

(

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

printf("%d%d\n",getgcd(azb),a*b/(getgcd(a,b)));

}

)

return0;

)

排序后求位置處的數(shù)

Sortit...

Description

Thereisadatabase,partychenwantyoutosortthedatabase'sdataintheorderfromtheleastup

tothegreatestelement,thendothequery:"Whichelementisi-thbyitsvalue?"-withibeinga

naturalnumberinarangefrom1toN.

Itshouldbeabletoprocessquicklyquerieslikethis.

Input

Thestandardinputoftheproblemconsistsoftwoparts.Atfirst,adatabaseiswritten,andthen

there'sasequenceofqueries.Theformatofdatabaseisverysimple:inthefirstlinethere'sa

numberN(l<=N<=100000j,inthenextNlinestherearenumbersofthedatabaseoneineach

lineinanarbitraryorder.Asequenceofqueriesiswrittensimplyaswell:inthefirstlineofthe

sequenceanumberofqueriesK(1<=K<=100)iswritten,andinthenextKlinesthereare

queriesoneineachline.Thequery"Whichelementisi-thbyitsvalue?"iscodedbythenumber

i.

Output

TheoutputshouldconsistofKlines.Ineachlinethereshouldbeananswertothecorresponding

query.Theanswertothequery"i"isanelementfromthedatabase,whichisi-thbyitsvalue(in

theorderfromtheleastuptothegreatestelement).

SampleInput

5

7

121

123

7

121

3

3

2

5

SampleOutput

121

7

123

#include<stdio.h>

#include<algorithm>

usingnamespacestd;

intnum[100010];

intpos[105];

intmain()

(

intn;

inti;

intk;

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

{

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

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

scanf("%d",&k);

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

scanf("%d，&pos[i]);

sort(num+l,num+l+n);

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

printf("%d\rT,num[pos[i]]);

)

return0;

)

*路由器連接

HubConnectionplan

Description

Partychenisworkingassystemadministratorandisplanningtoestablishanewnetworkinhis

company.TherewillbeNhubsinthecompany,theycanbeconnectedtoeachotherusingcables.

Sinceeachworkerofthecompanymusthaveaccesstothewholenetwork,eachhubmustbe

accessiblebycablesfromanyotherhub(withpossiblysomeintermediatehubs).

Sincecablesofdifferenttypesareavailableandshorteronesarecheaper,itisnecessarytomake

suchaplanofhubconnection,thatthecostisminimal,partychenwillprovideyouallnecessary

informationaboutpossiblehubconnections.Youaretohelppartychentofindthewayto

connecthubssothatallaboveconditionsaresatisfied.

Input

Thefirstlineoftheinputcontainstwointegernumbers:N-thenumberofhubsinthenetwork(2

<=N<=1000)andM-thenumberofpossiblehubconnections(1<=M<=15000).Allhubsare

numberedfrom1toN.ThefollowingMlinescontaininformationaboutpossibleconnections-

thenumbersoftwohubs,whichcanbeconnectedandthecablecostrequiredtoconnectthem,

costisapositiveintegernumberthatdoesnotexceed106.Therewillalwaysbeatleastoneway

toconnectallhubs.

Output

Outputtheminimizecostofyourhubconnectionplan.

SampleInput

46

121

131

142

231

341

241

SampleOutput

3

#include<stdio.h>

#include<algorithm>

usingnamespacestd;

structEdge{

inta,b;

intcost;

}E[15010];

intTree[1010];

intfindRoot(intx)

(

if(Tree[x]==-l)

returnx;

else

(

inttmp=findRoot(Tree[x]);

Tree[x]=tmp;

returntmp;

)

)

boolCmp(Cdgea,匚dgeb)

(

returna.cost<b.cost;

)

intmain()

{

intn;

intm;

inti;

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

(

scanf("%d",&m);

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

scanf("%d%d%d",&E[i].a,&E[i].b,&E[i].cost);

sort(E+l,E+l+m,Cmp);〃排序

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

Tree[i]=-1;

intans=0;

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

(

inta=findRoot(E[i].a);

intb=findRoot(E[i].b);

if(a!=b)

Tree[a]=b;

ans+=E[i].cost;

)

printf("%d\rT,ans);

)

return0;

)

*編譯原理

PrinciplesofCompiler

Description

AfterlearntthePrinciplesofCompilecpartychenthoughtthathecansolveasimpleexpression

problem.Sohegiveyoustringsoflessthan100characterswhichstrictlyadheretothefollowing

grammar(giveninEBNF):

A:='('B')Tx'.

B:=AC.

C:={'+'A}.

Canyousolvethemtoo?

Input

Thefirstlineofinputgivesthenumberofcases,N(1WNW100).Ntestcasesfollow.

ThenextNlineswilleachcontainastringasdescribedabove.

Output

Foreachtestcase,iftheexpressionisadapttotheEBNFaboveoutput"Good"zelseoutput

"Bad".

SampleInput

3

(x)

(x+(x+x))

()(x)

SampleOutput

Good

Good

Bad

//include<cstdio>

#include<cstring>

ttinclude<cstdlib>

ttinclude<vector>

#include<cmath>

ttinclude<iostream>

#include<algorithm>

//include<functional>

#include<string>

ttinclude<map>

//include<cctype>

usingnamespacestd;

charex[110];

intindex;

boolA();

boolB();

boolC();

boolA()

(

if(ex[index]=='x')

(

index++;

while(ex[index]=='')index++;

returntrue;

)

if(ex[index]=="(')

(

index++;

while(ex[index]=='')index++;

if(D()&&ex[index]==')')

(

index++;

while(ex[index]=='')index++;

returntrue;

)

)

returnfalse;

)

boolB()

(

returnA()&&C();

)

boolC()

(

while(ex[index]=='+')

(

index++;

while(ex[index]=='')index++;

//returnA();

if(!A())

returnfalse;

)

returntrue;

)

intmain()

intN;

scanf("%d"z&N);

getchar();

while(N-)

{

gets(ex);

index=O;

printf("%s\n",A()&&ex[index]=='\0,?"Good":"Bad");

)

return0;

)

*分開(kāi)連接

SeparateConnections

Description

Partychenareanalyzingacommunicationsnetworkwithatmost18nodes.Characterinamatrix

i,j(i,jboth0-based,asmatrix[i][j])denoteswhethernodesiandjcancommunicate('Y'foryes,'N'

forno).Assuminganodecannotcommunicatewithtwonodesatonce,returnthemaximum

numberofnodesthatcancommunicatesimultaneously.Ifnodeiiscommunicatingwithnodej

thennodejiscommunicatingwithnodei.

Input

Thefirstlineofinputgivesthenumberofcases,N(1WNW100).Ntestcasesfollow.

Ineachtestcase,thefirstlineisthenumberofnodesM(1WMW18),thenthereareagridby

M*Mdescribledthematrix.

Output

Foreachtestcase,outputthemaximumnumberofnodesthatcancommunicatesimultaneously

SampleInput

2

5

NYYYY

YNNNN

YNNNN

YNNNN

YNNNN

5

NYYYY

YNNNN

YNNNY

YNNNY

YNYYN

SampleOutput

2

4

Hint

Thefirsttestcase:

Allcommunicationsmustoccurwithnode0.Sincenode0canonlycommunicatewith1nodeat

atime,theoutputvalueis2.

Thesecondtestcase:

Inthissetup,wecanletnode0communicatewithnode1,andnode3communicatewithnode4.

^include<cstdio>

ttinclude<cstring>

#include<rcstdlib>

ttinclude<vector>

//include<cmath>

#include<iostream>

#include<algorithm>

^include<functional>

//include<string>

#include<map>

//include<queue>

usingnamespacestd;

ttdefineMAXN250

ttdefineMAXEMAXN*MAXM*2

#defineSET(a,b)memsetfa^sizeoffa))

deque<int>Q;

boolg[MAXN][MAXN],inque[MAXN],inblossom[MAXN];

intmatch[MAXN],pre[MAXN],base[MAXN];

intfindancestor(intujntv)

(

boolinpath[MAXN]={false};

while(l)

(

u=base[u];

inpath[u]=true;

if(match[u]==-l)break;

u=pre[match[u]];

)

while(l)

(

v=base[v];

if(inpath[v])returnv;

v=pre[match[v]];

)

)

voidreset(intujntanc)

{

while(u!=anc)

intv=match[u];

inblossom[base[u]]=l;

inblossom[base[v]]=l;

v=pre[v];

if(base[v]!=anc)pre[v]=match[u];

u=v;

)

)

voidcontract(intujntv,intn)

(

intanc=findancestor(u,v);

SET(inblossom,0);

reset(u,anc);

reset(v,anc);

if(base[u]!=anc)pre[u]=v;

if(base(v]!=anc)pre[v]=u;

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

if(inblossom[base[i]])

{

base[i]=anc;

if(!inque[i])

(

Q.push_back(i);

inque[i]=l;

)

)

)

booldfsfintS,intn)

(

for(inti=O;i<=n;i++)pre[i]=-l,inque[i]=O,base[i]=i;

Q.clear();

Q.push_back(S);

inque[S]=l;

while(!Q.empty())

(

intu=Q.front();

Q.pop_front();

for(intv=l;v<=n;v++)

(

i^(g[u][v]&&base[v]!=base[u]&&match[u]!=v)

(

if(v==S||(match[v]!=-l&&pre[match[v]]!=-l))contract(u,v,n);

elseif(pre[v]==-l)

pre[v]=u;

if(match(v]!=-l)Q.push_back(match[v])zinque[match[v]]=l;

else

u=v;

while(u!=-l)

(

v=pre[u];

intw=match[v];

match[u]=v;

match[v]=u;

u=w;

)

returntrue;

)

}

)

)

)

returnfalse;

)

intsolve(intn)

(

SET(match,-l);

intans=O;

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

if(match[i]==-l&&dfs(izn))

ans++;

returnans;

)

intmain()

(

intans;

intn,m;

chartmp[30];

scanf("%d",&n);

while(n-)

(

ans=O;

memset(g,0,sizeof(g));

scanf("%d",&m);

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

scanf("%s",tmp+l);

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

if(tmp[jl=='Y')

(

g[i][j]=gU][i]=l；

)

)

)

ans=solve(m);

printf("%d\n",ans*2);

)

return0;

2010機(jī)試

ECNU的含義

Welcometo2009ACMselectivetrial

Description

Welcometo2009ACMselectivetrial.ACMisalongwaytogo,andit'snotjustamatch.Sowhat

youneedtodofornowisdoyourbest!AndasmembersofACMlab,wearegoingtoteachyou

somethingimportant.FirstyyoushouldbeproudthatyouareamemberofECNU,because'E'

represents"Excellent",'Crepresents"Cheer",'N'represents"Nice",*U'represents"Ultimate".

SecondyoushouldrememberImpossibleisnothing,because"Impossible"represents"I'm

possible".ThirdfortodayyoushouldkeepACM,becauseforyouACMrepresents"AcceptMore".

Doyourememberthemclearly?

Nowwewillgiveyouastringeither"E"/'C","N'7'U","Impossible"or"ACM",youneedtotellme

whatdoesitmeans?

Input

Thefirstlineofinputgivesthenumberofcases,N(1WNW10).Ntestcasesfollow.

Eachtestconsistsofastringwhichw川beoneof"E","C","N","U","lmpossible"or"ACM".

Output

Tellmewhatdoesitmeans

SampleInput

3

E

Impossible

ACM

SampleOutput

Excellent

I'mpossible

AcceptMore

#include<stdio.h>

#include<string.h>

charstr[2O];

intmain()

(

intN;

scanf("%d",&N);

while(N--)

(

scanf("%s"zstr);

if(strcmp(str；'E")==O)

printf("Excellent\n");

elseif(strcmp(str；'C")==O)

printf("Cheer\n");

elseif(strcmp(str/'N")==O)

printf("Nice\n");

elseif(strcmp(str/,U")==O)

printf("Ultimate\n");

elseif(strcmp(stc"lmpossible")==0)

printf('Tmpossible\n");

elseif(strcmp(str；'ACM")==3)

printf("AcceptMore\n")；

)

return0;

)

空瓶換啤酒

SodaSurpler

Description

Timisanabsolutelyobsessivesodadrinkeohesimplycanno:getenough.Mostannoyingly

though,healmostneverhasanymoney,sohisonlyobviouslegalwaytoobtainmoresodaisto

takethemoneyhegetswhenherecyclesemptysodabottlestobuynewones.Inadditiontothe

emptybottlesresultingfromhisownconsumptionhesometimesfindemptybottlesinthes:reet.

Onedayhewasextrathirsty,soheactuallydranksodasuntilhecouldn'tafordanewone.

Input

Threenon-negativeintegerse,f,c,wheree<1000equalsthenumberofemptysoda

bottlesinTim'spossessionatthestartoftheday,f<1000thenumberofemptysoda

bottlesfoundduringtheday,and1<c<2000thenumberofemptybottlesrequiredto

buyanewsoda.

Output

HowmanysodasdidTimdrinkonhisextrathirstyday?

SampleInput

903

552

SampleOutput

4

9

#include<stdio.h>

#include<string.h>

intmain()

(

inte,fzc;

intt;

intsum;

intfull,empty;

while(scanf("%d%d%d',,&e,&f,&c)!=EOF)

(

sum=0;

empty-ee〃空瓶數(shù)量

while(empty>=c)〃空瓶數(shù)量可換

(

sum+=empty/c;〃換的滿瓶

empty=empty/c+empty%c;〃新的空瓶數(shù)量

)

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

)

return0;

統(tǒng)計(jì)字符

統(tǒng)計(jì)字符

Description

輸入一行字符，分別統(tǒng)計(jì)其中英文字母、空格、數(shù)字和其他字符的個(gè)數(shù)。

Input

輸入一個(gè)整數(shù)t,表示有幾組數(shù)據(jù)

接下來(lái)有t行，每行字符不超過(guò)10000個(gè)

Hint可能有空格之類的字符

Output

對(duì)于每行字符輸出其中

1英文字母（大小寫都算）的個(gè)數(shù)

2數(shù)字的個(gè)數(shù)

3其他字符的個(gè)數(shù)

SampleInput

2

q2e2

qweqrwwerr232424fwetetg===2342gdsg3.//-=@321

SampleOutput

character:2

number:2

others:l

character:21

number:14

others:9

#include<stdio.h>

#include<string.h>

charstr[10010];

intmain()

(

intt;

inti;

intcn,nn,on;

scanf(”%d”,&t);

getchar();〃去除上一個(gè)換行符

while(t-)

(

gets(str);

intl=strlen(str);

cn=nn=on=0;

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

(

if(str[i]>='0'&&str[i]<='9')

nn++;

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

cn++;

else

on++;

)

printf("character:%d\n",cn);

printf("number:%d\n"/nn);

printf("others:%cl\n",on);

return0;

2010機(jī)試熱身

粽子買三送一，買五送二

端午節(jié)快樂(lè)

Description

今天是端午節(jié)，ECNU決定請(qǐng)大家吃粽子。恰好，今天超市為了迎合“端午節(jié)”，推出了“端午

大酬賓”，即促銷活動(dòng)。嚴(yán)格的買三送一，買五送二。

ECNU想用現(xiàn)有的人民幣，買最多的粽子，但是他自己又不會(huì)算，所以希望你能幫幫他。

Input

輸入第一行為一個(gè)數(shù)N(l<=N<=100),表示測(cè)試數(shù)據(jù)的組數(shù)。

每組測(cè)試數(shù)據(jù)有兩個(gè)整數(shù)，A,B(0<=A<=1000,0<B<10)表示ECNU有A元人民幣,每個(gè)粽子價(jià)格

為B元人民幣,超市推出了買5個(gè)送2個(gè)，和買3個(gè)送1個(gè)的活動(dòng)。

Output

輸出ECNU最多能買到的粽子數(shù)量。

SampleInput

2

103

223

SampleOutput

4

9

Hint:

有兩組測(cè)試數(shù)據(jù)：

對(duì)于第一組測(cè)試數(shù)據(jù):有1。元人民幣，粽子3元一個(gè)，可以買3個(gè),但是買3送1,所以最后有4

個(gè)。

對(duì)于第二組測(cè)試數(shù)據(jù):有22元人民幣，粽子3元一個(gè)，可以買7個(gè),但是買5送2,所以最后有9

個(gè)。

#include<stdio.h>

#include<string.h>

intmain()

(

intn;

intazb;

intzn;

intnum;

scanf("%d",&n);

while(n-)

(

scanf("%d%d",&a,&b);〃輸入人民幣數(shù)和粽子單價(jià)

zn=a/b;〃買了zn個(gè)

num=zn;

if(zn/5!=0)

(

num+=zn萬(wàn)*2;

zn=zn%5;

)

if(zn/3!=0)

(

num+=zn/3;

)

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

)

return0;

工程流水線問(wèn)題

工程

Description

Castor在ECNU工廠工作?？倧S有一條生產(chǎn)線，現(xiàn)在生產(chǎn)流水線上排隊(duì)的零件總數(shù)為當(dāng)

前Castor開(kāi)場(chǎng)加工第一個(gè)零件。

流水線上的零件總是按順序加工的。例如零件i必須是在零件i+1之前加工.

現(xiàn)在Castor只需要再加工K(K<=M)個(gè)零件就能休息了，Castor想知道他還要工作多長(zhǎng)時(shí)間才

能休息.

Input

第一行為一個(gè)整數(shù)T,表示測(cè)數(shù)數(shù)據(jù)的組數(shù).

對(duì)每組測(cè)試數(shù)據(jù)

第一行有兩個(gè)整數(shù)M,K(l<=K<=M<=1000)

然后一行有M個(gè)數(shù)字第i個(gè)數(shù)字表示零件隊(duì)列的第i個(gè)零件需要加工的時(shí)間為

ti(l<=ti<=10000)

Output

每組數(shù)據(jù)輸出一行，每行只有一個(gè)整數(shù)表示Castor還需要工作多長(zhǎng)時(shí)間

SampleInput

2

32

523

31

123

SampleOutput

7

1

#include<stdio.h>

#include<string.h>

#include<math.h>

ffinclude<stdlib.h>

intmain()

intT;

intM,K;

inti;

intt[1005];

intsum;

scanf("%d",&T);

while(T-)

(

sum=O;

scanf("%d%d",&M/&K];

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

scanf("%d"z&t[i]);

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

(

sum+=t[i];

)

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

)

return0;

2011機(jī)試

helk）world

HelloWorld!

Description

當(dāng)開(kāi)場(chǎng)學(xué)習(xí)程序語(yǔ)言，第一個(gè)程序肯定是在屏幕上輸出一些字符:，比方輸出〃Hell。

Worldo

遇到輸出的句子過(guò)長(zhǎng)時(shí)，輸出的句子由于換行將被屏幕裁斷。現(xiàn)在給你一些文本，文本的文

法如下：

TEXT（文本）:=SENTENCE|SENTENCESPACETEXT

SENTENCE（句子）:=WORDSPACESENTENCE|WORDEND

END（完畢符）:={：?,T}

WORD（單詞）:=LETTER|LETTERWORD

LETTER（字母）:={'a'./z','A'./Z'}

SPACE（空格

你的任務(wù)是把滿足上述文法的文木分割成多行（每行文木的長(zhǎng)度都不超過(guò)n）。并且滿足如

下條件：

一、輸出的句子不能被截?cái)唷Ｈ纾?Hi!WelcometoECNU."假設(shè)被分割成"Hi!Welcome"

則認(rèn)為被截?cái)啵床缓戏ā?/p>

二、文本分割后保證行數(shù)最小。如："Hi!WelcometoECNU.Haveaniceday!"在每行文本長(zhǎng)

度要求在n=20的情況下,可以分割為："Hi!""WelcometoECNU.""Haveaniceday!"也可

以被分割為："Hi!WelcometoECNU./zHaveaniceday!z/此時(shí)認(rèn)為第二種分法才合法。

注意：如果兩個(gè)相鄰的句子被分割到兩行，句子中間的空格可以被忽略。

Input

第1行為測(cè)試數(shù)據(jù)組數(shù)T(T<=100),接下來(lái)為T組數(shù)據(jù)。

每組數(shù)據(jù)包含2行，第1行為屏幕每行最多可以顯示的字符數(shù)n(2<=n<=255)。第二行為文本,

字符總數(shù)不超過(guò)10001,并且保證符合上述文法。

Output

輸出包含T行，每行輸出分解后的文本最少需要的屏幕行數(shù)。如果無(wú)法到達(dá)要求，則輸出"

Impossible"(不要輸出引號(hào))。

SampleInput

3

12

HelloWorld!

11

HelloWorld!

40

Hello.WelcometoEastChinaNormalUniversity!Whatisyojrname?

SampleOutput

i

Impossible

3

#include<stdio.h>

#include<string.h>

charstr[10010];

intnum[5010];〃每個(gè)句子的個(gè)數(shù)

intmain()

{

intT;

intn;

inti;

scanf("%d"z&T);

while(T-)

scanf(”％d”,&n);〃每行的限制字符個(gè)數(shù)

getchar();〃丟棄上一個(gè)換行

gets(str);〃輸入文本

intl=strlen(str);〃文本的長(zhǎng)度

intcn=O;〃統(tǒng)計(jì)句子的長(zhǎng)度

intk=0;〃句子長(zhǎng)度數(shù)組的下標(biāo)

i=0;

while(i<l)

|

if(str[i]==?||str[i]==?||str[i]==T)〃遇到句子完畢為止

(

cn++;

i+=2;〃跳過(guò)空格

num[k]=cn;

k++;

cn=0;〃長(zhǎng)度清空

)

else

(

cn++;

i++;

)

)

intflag=l;

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

(

if(num[i]>n)〃單個(gè)句子字符數(shù)大于限制的個(gè)數(shù)

(

flag=O;

break;

)

)

if(flag==0)

printf("lmpossible\n");

else

(

inth=l;〃行數(shù)為1

intsum=0;

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

(

if(sum+num[i]<=n)

(

sum+=num[i];

)

else〃累加句子字符數(shù)大于限制個(gè)數(shù)

h++;

sum=num[];〃清空

)

)

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

}

)

return0;

)

Specialjudge

SpecailJudge

Description

大家都知道OnlineJud浜(在線判題系統(tǒng)，比方你現(xiàn)在使用的EOJ),它的工作原理是通過(guò)對(duì)■比

用戶提交的程序運(yùn)行獲得的數(shù)據(jù)是否和系統(tǒng)的測(cè)試數(shù)據(jù)一致，對(duì)比的方式往往是逐個(gè)字節(jié)的

比對(duì)。但是有一些題需要特殊的比對(duì)，比方標(biāo)準(zhǔn)數(shù)據(jù)是0.01,而用戶提交的數(shù)據(jù)是0.02,那

么在0.1的誤差允許范圍內(nèi)，認(rèn)為用戶是正確的?，F(xiàn)在請(qǐng)你來(lái)寫一個(gè)程序判斷用戶的程序是

否正確。

Input

第1行為測(cè)試數(shù)據(jù)組數(shù)T(T<=1000),接下來(lái)為T組數(shù)據(jù)。

每組數(shù)據(jù)包含三行，每行一個(gè)浮點(diǎn)數(shù)s,t,e,分別表示通過(guò)運(yùn)行用戶程序獲得的數(shù)據(jù)，標(biāo)準(zhǔn)數(shù)

據(jù)，誤差允許的范圍

Output

輸出包含T行,如果用戶數(shù)據(jù)和標(biāo)準(zhǔn)數(shù)據(jù)相差在誤差范圍內(nèi)(|s-t|<=e),則輸出"Accept",

否則輸出"WrongAnswer"?(不要輸出引號(hào))

SampleInput

3

0.02

0.01

0.1

0.02

0.01

0.01

0.02

0.01

0.001

SampleOutput

Accept

Accept

WrongAnswer

#include<stdio.h>

#include<math.h>〃使用fabs()函數(shù)求絕對(duì)值

intmain()

(

intT;

doubles,t?

scanf("%d",&T);

while(T-)

(

scanf("％lf%lf%吃&s,&t,&e);

if(fabs(s-t)<=e)//假設(shè)|s-t|<=e

printf("Accept\n");

else

printf("WrongAnswer\n")；

}

return0;

)

查詢成績(jī)

Description

給你n(n<=50,000)個(gè)學(xué)生的名字和成績(jī)，查詢大于某個(gè)分?jǐn)?shù)s的第一個(gè)學(xué)生，并輸出其名字,

如果兩個(gè)學(xué)生成績(jī)一樣，則以名字字典序小的在前輸出。

Input

第1行為測(cè)試數(shù)據(jù)總數(shù)T(T<=10),接下來(lái)為T組數(shù)據(jù)。

每組數(shù)據(jù)包含假設(shè)干行，第1行為人的數(shù)量n(n<=50,000),接下來(lái)n行為以空格隔開(kāi)學(xué)生的名

字和成績(jī)，名字由大小寫字母組成，長(zhǎng)度<=5,并且保證不存在重復(fù)的名字，成績(jī)?yōu)榉秦?fù)整

?s(s<=2A31-l)o

接下來(lái)一行為一個(gè)整數(shù)Q(Q<=50,000),表示查詢的次數(shù)，再接下來(lái)Q行，每行一個(gè)非負(fù)整

數(shù)，表示要查詢的分?jǐn)?shù)s(s<=271-1)。

注意：當(dāng)輸入輸出數(shù)據(jù)很大時(shí)，請(qǐng)使用scanf和printf而不要用cin和cout。

Output

輸出包含假設(shè)干行，每組測(cè)試數(shù)據(jù)包含Q行，為查詢到的學(xué)生的名字，如果不存在，則輸出"

Impossible"(不要輸出引號(hào))。

SampleInput

2

3

one955

three1000

two994

3

900

955

1000

2

three995

one1000

2

500

1000

SampleOutput

one

two

Impossible

three

Impossible

#include<stdio.h>

#include<algorithm>

usingnamespacestd;

structstu{

charname[10];

longintre;

⑶50010];

longintquery[50010];〃孩子的分?jǐn)?shù)

intfind(intlowjnthighjongintx)〃查詢大于x的第一個(gè)元素位置

(

intmid=(low+high)/2;

while(low<=high)

(

if(s[mid].re>x)

(

high=mid-l;

mid=(low+high)/2;

)

else

(

low=mid+l;

mid=(low+high)/2;

)

returnlow;〃找到該位置

)

boolCmp(stua,stub)〃成績(jī)低的排在前面，假設(shè)成績(jī)一樣，以名字字典序小的在前輸出

(

if(a.re!=b.re)

returna.re<b.re;

else

return<;

)

intmain()

|

intT;

intn,q;

inti;

intj;

scanf(”%d”,&T);

while(T--)

{

scanf("%d",&n);

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

scanf("%s%ld",s[i].name,&s[i].re);〃輸入孩子的姓名和成績(jī)

sort(s,s+n,Cmp);〃排序

scanf(”%d",&q);

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

scanf(”％ld”,&query「])；〃輸入查詢的成績(jī)

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

{

if(queMi]>=s[n-l].re)〃如果查詢成績(jī)大于等于最大值

printf("lmpossible\n")；

else

(

,,

printf(%s\n"/s[find(O/n-l/query[i])].name);

}

)

return0;

2011機(jī)試熱身

貪吃蛇

Description

相信很多人都玩過(guò)這個(gè)游戲，當(dāng)然這個(gè)題目不是叫你寫一個(gè)貪吃蛇游戲，而是很簡(jiǎn)單的模擬

而已，為了簡(jiǎn)化規(guī)則，我們把游戲抽象為：

在HxW的格點(diǎn)上有一條小小的長(zhǎng)度為1的蛇，這條蛇每次只能向上下左右四個(gè)方向移動(dòng)一

個(gè)單位距離。在某些格點(diǎn)上有營(yíng)養(yǎng)價(jià)值不同的蘑菇，當(dāng)蛇移動(dòng)到含有蘑菇的點(diǎn)的時(shí)候，其生

命力會(huì)增加相應(yīng)的值。在每個(gè)時(shí)間點(diǎn)，其選擇的方向是由函數(shù)。％4決定的，其中尸0=0,

Fl=l,Fn=Fn-l+Fn-2.如果蛇選擇的方向會(huì)立即撞到墻，它會(huì)沿著該方向的順時(shí)針選

擇第一個(gè)不會(huì)撞到墻的方向作為該時(shí)刻的方向。初始時(shí)刻是0時(shí)刻，蛇在左上角，初始生命

力為0,某個(gè)點(diǎn)上的蘑菇在吃掉后會(huì)立刻長(zhǎng)出來(lái)。最外一圈是墻，沒(méi)有給出來(lái)。

請(qǐng)你輸出T時(shí)刻蛇的生命力。方向?qū)?yīng)關(guān)系為：上(0)、右(1)、下(2)、左(3).

Input

每個(gè)文件一個(gè)測(cè)試數(shù)據(jù)：

數(shù)據(jù)的第一行三個(gè)整數(shù)H,W,T。(2<=H、W<=100,0<=T<=1000)

接下來(lái)H行，每行W個(gè)字符，其中？表示可行走的空地，0-9表示價(jià)值不同的蘑菇，相應(yīng)

的價(jià)值分別為0-9

Output

對(duì)于每組數(shù)據(jù)，輸出一個(gè)值，表示T時(shí)刻后(含T時(shí)刻：蛇的生命力

SampleInput

234

145

1..

SampleOutput

10

Hint:

。時(shí)刻蛇在(0,0),方向0,但是會(huì)出界，順時(shí)針選擇第一個(gè)不出界的方向1,生命力1

1時(shí)刻蛇在(0,1),方向1,生命力5

2時(shí)刻蛇在(0,2),方向1,會(huì)出界.選擇方向2.牛命力10

3時(shí)刻蛇在(1,2),方向2,會(huì)出界,選擇方向3,生命力10

4時(shí)刻蛇在(1,1),方向3,生命力10

#include<stdio.h>

#include<string.h>

intf[1010];〃蛇的t時(shí)刻移動(dòng)方向

voidinit()

inti;

f[0]=0；

f[l]=l;

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

(

intg。⑷⑵={〃定義方向

-1,0,〃上

0,1,〃右

1,0,〃下

0,-1}；〃左

structE{

intx;〃橫坐標(biāo)

inty;〃縱坐標(biāo)

intt;〃小蛇的生命力

回〃定義小蛇

char〃是否有蘑菇

intmain()

(

init();〃初始化

inti;

intj;

inth,w,t;

while(scanf("%d%d%d"/&h,&w/&t)!=EOF)

(

〃小蛇的初始狀態(tài)

e.x=0;

e.y=0;

e.t=0;

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

(

scanf('%s”,ch[i]);〃輸入生命值

)

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

{

if(ch[e.x][eM>='(T&&(:h[e.x][e.y]<=9)〃此處有蘑菇

(

e.t+=(ch[e.x][e.y]-,0,);

)

if(e.x==0&&e.y==0)〃小蛇處于左上角

if(f[i]==0||f[i]==3)〃向上走或向左走

f[i]=l；〃改變方向向右，更新坐標(biāo)

)

e.x+=go[f[i]][0];

e.y+=go[f[i]][l];

)

elseif(e.x==O&&e.y==w-l)〃小蛇在右上角

(

if(f[i]==O||f[i]==l)〃向上走或向右走

(

f「]=2;〃改變方向向下，更新坐標(biāo)

)

e.x+=go[f[i]][0];

e.y+=go[f[i]][l];

}

elseif(e.x==h-l&&e.y==O)〃小蛇在左下角

|

if(f[i]==2||f[i]==3)〃向下走或向左走

{

f[i]=O；〃改變方向向上，更新坐標(biāo)

)

e.x+=go[f(i]][0];

e.y+=go[f[i]][l];

)

elseif(e.x==h-l&&e.y==w-l)〃小蛇在右下角

(

if(f[i]==l||皿==2)〃向下走或向右走

{

f[i]=3;〃改變方向向左，更新坐標(biāo)

}

e.x+=go[f[i]][0];

e.y+=go[f[i]][l];

)

elseif(e.x==O)〃在最上面

|

if(f[i]==O)

{

f[i]=l；

)

e.x+=go[f[i]][0];

e.y+=go[f[i]][l];

)

elseif(e.x==h-l)〃在最卜面

if(f[i]==2)

f[i]=3；

)

e.x+=go[f[i]][0];

e.y+=go[f[i]][l];

|

elseif(e.y==O)

(

(

f[i]=O;

)

e.x+=go[f[i]][0];

e.y+=go[f[i]][l];

}

elseif(e.y==w-l)

(

if(f[i]==l)

f[i]=2；

e.x+=go[f[i]][0];

e.y+=go[f[i]][l];

}

else{〃否則直接轉(zhuǎn)”

e.x+=go[f[i]][0];

e.y+=go[f[i]][l];

)

)

printf("%d\rr,e.t);

|

return0;

)

仰望星空

仰望星空

假設(shè)天空為w*h的平面，星座由相鄰的星星組成。兩顆星相鄰的條件為橫向或縱向或?qū)?/p>

相連。如以以下列圖為10*5的天空：

?**

*******

**

*******

????***

星星為',空白的局部為'上圖星空共有2個(gè)星座。

Input

第1行：兩個(gè)由空格分開(kāi)的整數(shù),l<=w<=80和l<=h<=1000.

第2到h+1行：每一行包含w個(gè)‘*，或者’代表星空的組成。

Output

一行：表示當(dāng)前星空星座的個(gè)數(shù)。

SampleInput

105

***

*******

**

*******

*******

158

******

???????????????

***********

???****??

???**??*??*????

***********

????**???*??*??

********

SampleOutput

2

7

#include<stdio.h>

charmaze[1010][85];〃保存地圖信息

boolmark[1010][85];〃為圖上每一個(gè)點(diǎn)設(shè)立一個(gè)狀態(tài)

intn,m;

intgo[][2]={

1,0,

-1,0,

0,1,

0”,

1,1,

1,」，

-1,-1,

-1,1};/出個(gè)相鄰點(diǎn)與當(dāng)前位置的坐標(biāo)差

voidDFSfintxjnty)

(

inti;

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

(

intnx=x+go[i][0];

intny=y+go皿1];〃計(jì)算其坐標(biāo)

if(nx<l11nx>n11ny<l11ny>m)

continue;〃假設(shè)該坐標(biāo)在地圖之外

if(maze[nx][ny]=='.')

continue;〃假設(shè)該位置不是*

if(mark[nx][ny]==true)

continue;〃該位置己經(jīng)被計(jì)算過(guò)

mark[nx][ny]=true;

DFS(nx,ny);〃遞歸查詢與該相鄰位置直接相鄰的點(diǎn)

)

return;

)

intmain()

(

intij;

whilelscanfd？id？idl&rrb&nWuEOF)〃輸入列和行:

(

if(n==0&&m==0)

break;

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

scanf("%s",maze[]+D；〃第i行地圖信息保存在maze[i][l]到maze[i][m]中

〃按行為單位輸入地圖信息

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

(

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

mark[i][j]=false;〃初始化所有位置為未被計(jì)算

)

intans=0;〃初始化塊計(jì)算器

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

(

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

(

if(mark[i][j]==true)

continue;

if(maze[i][j]=='.')

continue;

DFS(iJ);

ans++;

)

)

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

)

return0;

*編輯距離

編輯距離

Description

有兩個(gè)字符串(僅有英文小寫字母組成〕A,Bo我們可以通過(guò)一些操作將A修改成亂操作

有三種：1修改一個(gè)字母，2