华东师范大学计算机机试真题

2009机试2

计算和的数位2

大写改小写3

素数对3

求最大公约数和最小公倍数5

排序后求位置处的数6

*路由器连接8

*编译原理10

*分开连接12

2010机试16

ECNU的含义16

空瓶换啤酒17

统计字符18

2010机试热身20

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

工程流水线问题21

2011机试22

helloworld22

Specialjudge25

查询成绩26

2011机试热身29

贪吃蛇29

仰望星空32

*编辑距离35

2012机试37

字母排序37

幸运数37

十六进制的加法40

号码簿合并排序40

*五子棋41

*止则表达式匹配43

2013机试44

斐波那契数列的素数个数44

*将a字符变成b字符最少修改次数45

2013机试热身47

去重排序47

蛇形图案49

数学手稿51

2009机试

计算和的数位

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;

)

素数对

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;〃不是素数

prime[2]=true;〃是素数

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

|

prime[i]=true;〃是素数

prime[i+l]=false;〃不是素数除0和2之外的偶数都不是素数

)

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

(

if(prime[i]==true)〃是素数

(

j=i+i;

while(j<=10005)

prime[j]=false;〃不是素数

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为奇数

(

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

sum+=l;

}

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

)

)

return0;

)

求最大公约数和最小公倍数

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;

)

排序后求位置处的数

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;

)

*分开连接

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机试

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〃空瓶数量

while(empty>=c)〃空瓶数量可换

(

sum+=empty/c;〃换的满瓶

empty=empty/c+empty%c;〃新的空瓶数量

)

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

)

return0;

统计字符

统计字符

Description

输入一行字符，分别统计其中英文字母、空格、数字和其他字符的个数。

Input

输入一个整数t,表示有几组数据

接下来有t行，每行字符不超过10000个

Hint可能有空格之类的字符

Output

对于每行字符输出其中

1英文字母（大小写都算）的个数

2数字的个数

3其他字符的个数

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();〃去除上一个换行符

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机试热身

粽子买三送一，买五送二

端午节快乐

Description

今天是端午节，ECNU决定请大家吃粽子。恰好，今天超市为了迎合“端午节”，推出了“端午

大酬宾”，即促销活动。严格的买三送一，买五送二。

ECNU想用现有的人民币，买最多的粽子，但是他自己又不会算，所以希望你能帮帮他。

Input

输入第一行为一个数N(l<=N<=100),表示测试数据的组数。

每组测试数据有两个整数，A,B(0<=A<=1000,0<B<10)表示ECNU有A元人民币,每个粽子价格

为B元人民币,超市推出了买5个送2个，和买3个送1个的活动。

Output

输出ECNU最多能买到的粽子数量。

SampleInput

2

103

223

SampleOutput

4

9

Hint:

有两组测试数据：

对于第一组测试数据:有1。元人民币，粽子3元一个，可以买3个,但是买3送1,所以最后有4

个。

对于第二组测试数据:有22元人民币，粽子3元一个，可以买7个,但是买5送2,所以最后有9

个。

#include<stdio.h>

#include<string.h>

intmain()

(

intn;

intazb;

intzn;

intnum;

scanf("%d",&n);

while(n-)

(

scanf("%d%d",&a,&b);〃输入人民币数和粽子单价

zn=a/b;〃买了zn个

num=zn;

if(zn/5!=0)

(

num+=zn万*2;

zn=zn%5;

)

if(zn/3!=0)

(

num+=zn/3;

)

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

)

return0;

工程流水线问题

工程

Description

Castor在ECNU工厂工作。总厂有一条生产线，现在生产流水线上排队的零件总数为当

前Castor开场加工第一个零件。

流水线上的零件总是按顺序加工的。例如零件i必须是在零件i+1之前加工.

现在Castor只需要再加工K(K<=M)个零件就能休息了，Castor想知道他还要工作多长时间才

能休息.

Input

第一行为一个整数T,表示测数数据的组数.

对每组测试数据

第一行有两个整数M,K(l<=K<=M<=1000)

然后一行有M个数字第i个数字表示零件队列的第i个零件需要加工的时间为

ti(l<=ti<=10000)

Output

每组数据输出一行，每行只有一个整数表示Castor还需要工作多长时间

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机试

helk）world

HelloWorld!

Description

当开场学习程序语言，第一个程序肯定是在屏幕上输出一些字符:，比方输出〃Hell。

Worldo

遇到输出的句子过长时，输出的句子由于换行将被屏幕裁断。现在给你一些文本，文本的文

法如下：

TEXT（文本）:=SENTENCE|SENTENCESPACETEXT

SENTENCE（句子）:=WORDSPACESENTENCE|WORDEND

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

WORD（单词）:=LETTER|LETTERWORD

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

SPACE（空格

你的任务是把满足上述文法的文木分割成多行（每行文木的长度都不超过n）。并且满足如

下条件：

一、输出的句子不能被截断。如："Hi!WelcometoECNU."假设被分割成"Hi!Welcome"

则认为被截断，即不合法。

二、文本分割后保证行数最小。如："Hi!WelcometoECNU.Haveaniceday!"在每行文本长

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

以被分割为："Hi!WelcometoECNU./zHaveaniceday!z/此时认为第二种分法才合法。

注意：如果两个相邻的句子被分割到两行，句子中间的空格可以被忽略。

Input

第1行为测试数据组数T(T<=100),接下来为T组数据。

每组数据包含2行，第1行为屏幕每行最多可以显示的字符数n(2<=n<=255)。第二行为文本,

字符总数不超过10001,并且保证符合上述文法。

Output

输出包含T行，每行输出分解后的文本最少需要的屏幕行数。如果无法到达要求，则输出"

Impossible"(不要输出引号)。

SampleInput

3

12

HelloWorld!

11

HelloWorld!

40

Hello.WelcometoEastChinaNormalUniversity!Whatisyojrname?

SampleOutput

i

Impossible

3

#include<stdio.h>

#include<string.h>

charstr[10010];

intnum[5010];〃每个句子的个数

intmain()

{

intT;

intn;

inti;

scanf("%d"z&T);

while(T-)

scanf(”％d”,&n);〃每行的限制字符个数

getchar();〃丢弃上一个换行

gets(str);〃输入文本

intl=strlen(str);〃文本的长度

intcn=O;〃统计句子的长度

intk=0;〃句子长度数组的下标

i=0;

while(i<l)

|

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

(

cn++;

i+=2;〃跳过空格

num[k]=cn;

k++;

cn=0;〃长度清空

)

else

(

cn++;

i++;

)

)

intflag=l;

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

(

if(num[i]>n)〃单个句子字符数大于限制的个数

(

flag=O;

break;

)

)

if(flag==0)

printf("lmpossible\n");

else

(

inth=l;〃行数为1

intsum=0;

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

(

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

(

sum+=num[i];

)

else〃累加句子字符数大于限制个数

h++;

sum=num[];〃清空

)

)

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

}

)

return0;

)

Specialjudge

SpecailJudge

Description

大家都知道OnlineJud浜(在线判题系统，比方你现在使用的EOJ),它的工作原理是通过对■比

用户提交的程序运行获得的数据是否和系统的测试数据一致，对比的方式往往是逐个字节的

比对。但是有一些题需要特殊的比对，比方标准数据是0.01,而用户提交的数据是0.02,那

么在0.1的误差允许范围内，认为用户是正确的。现在请你来写一个程序判断用户的程序是

否正确。

Input

第1行为测试数据组数T(T<=1000),接下来为T组数据。

每组数据包含三行，每行一个浮点数s,t,e,分别表示通过运行用户程序获得的数据，标准数

据，误差允许的范围

Output

输出包含T行,如果用户数据和标准数据相差在误差范围内(|s-t|<=e),则输出"Accept",

否则输出"WrongAnswer"«(不要输出引号)

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()函数求绝对值

intmain()

(

intT;

doubles,t©

scanf("%d",&T);

while(T-)

(

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

if(fabs(s-t)<=e)//假设|s-t|<=e

printf("Accept\n");

else

printf("WrongAnswer\n")；

}

return0;

)

查询成绩

Description

给你n(n<=50,000)个学生的名字和成绩，查询大于某个分数s的第一个学生，并输出其名字,

如果两个学生成绩一样，则以名字字典序小的在前输出。

Input

第1行为测试数据总数T(T<=10),接下来为T组数据。

每组数据包含假设干行，第1行为人的数量n(n<=50,000),接下来n行为以空格隔开学生的名

字和成绩，名字由大小写字母组成，长度<=5,并且保证不存在重复的名字，成绩为非负整

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

接下来一行为一个整数Q(Q<=50,000),表示查询的次数，再接下来Q行，每行一个非负整

数，表示要查询的分数s(s<=271-1)。

注意：当输入输出数据很大时，请使用scanf和printf而不要用cin和cout。

Output

输出包含假设干行，每组测试数据包含Q行，为查询到的学生的名字，如果不存在，则输出"

Impossible"(不要输出引号)。

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];〃孩子的分数

intfind(intlowjnthighjongintx)〃查询大于x的第一个元素位置

(

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)〃成绩低的排在前面，假设成绩一样，以名字字典序小的在前输出

(

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);〃输入孩子的姓名和成绩

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

scanf(”%d",&q);

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

scanf(”％ld”,&query「])；〃输入查询的成绩

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

{

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

printf("lmpossible\n")；

else

(

,,

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

}

)

return0;

2011机试热身

贪吃蛇

Description

相信很多人都玩过这个游戏，当然这个题目不是叫你写一个贪吃蛇游戏，而是很简单的模拟

而已，为了简化规则，我们把游戏抽象为：

在HxW的格点上有一条小小的长度为1的蛇，这条蛇每次只能向上下左右四个方向移动一

个单位距离。在某些格点上有营养价值不同的蘑菇，当蛇移动到含有蘑菇的点的时候，其生

命力会增加相应的值。在每个时间点，其选择的方向是由函数。％4决定的，其中尸0=0,

Fl=l,Fn=Fn-l+Fn-2.如果蛇选择的方向会立即撞到墙，它会沿着该方向的顺时针选

择第一个不会撞到墙的方向作为该时刻的方向。初始时刻是0时刻，蛇在左上角，初始生命

力为0,某个点上的蘑菇在吃掉后会立刻长出来。最外一圈是墙，没有给出来。

请你输出T时刻蛇的生命力。方向对应关系为：上(0)、右(1)、下(2)、左(3).

Input

每个文件一个测试数据：

数据的第一行三个整数H,W,T。(2<=H、W<=100,0<=T<=1000)

接下来H行，每行W个字符，其中？表示可行走的空地，0-9表示价值不同的蘑菇，相应

的价值分别为0-9

Output

对于每组数据，输出一个值，表示T时刻后(含T时刻：蛇的生命力

SampleInput

234

145

1..

SampleOutput

10

Hint:

。时刻蛇在(0,0),方向0,但是会出界，顺时针选择第一个不出界的方向1,生命力1

1时刻蛇在(0,1),方向1,生命力5

2时刻蛇在(0,2),方向1,会出界.选择方向2.牛命力10

3时刻蛇在(1,2),方向2,会出界,选择方向3,生命力10

4时刻蛇在(1,1),方向3,生命力10

#include<stdio.h>

#include<string.h>

intf[1010];〃蛇的t时刻移动方向

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;〃横坐标

inty;〃纵坐标

intt;〃小蛇的生命力

回〃定义小蛇

char〃是否有蘑菇

intmain()

(

init();〃初始化

inti;

intj;

inth,w,t;

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

(

〃小蛇的初始状态

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；〃改变方向向右，更新坐标

)

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;〃改变方向向下，更新坐标

)

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；〃改变方向向上，更新坐标

)

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;〃改变方向向左，更新坐标

}

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{〃否则直接转”

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

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

)

)

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

|

return0;

)

仰望星空

仰望星空

假设天空为w*h的平面，星座由相邻的星星组成。两颗星相邻的条件为横向或纵向或对角

相连。如以以下列图为10*5的天空：

♦**

*******

**

*******

♦♦♦♦***

星星为',空白的局部为'上图星空共有2个星座。

Input

第1行：两个由空格分开的整数,l<=w<=80和l<=h<=1000.

第2到h+1行：每一行包含w个‘*，或者’代表星空的组成。

Output

一行：表示当前星空星座的个数。

SampleInput

105

***

*******

**

*******

*******

158

******

・・♦・♦♦・♦・・・♦・・・

***********

♦♦♦****♦♦

・・•**••*•・*・•・・

***********

・・・・**・・・*・・*・・

********

SampleOutput

2

7

#include<stdio.h>

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

boolmark[1010][85];〃为图上每一个点设立一个状态

intn,m;

intgo[][2]={

1,0,

-1,0,

0,1,

0”,

1,1,

1,」，

-1,-1,

-1,1};/出个相邻点与当前位置的坐标差

voidDFSfintxjnty)

(

inti;

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

(

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

intny=y+go皿1];〃计算其坐标

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

continue;〃假设该坐标在地图之外

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

continue;〃假设该位置不是*

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

continue;〃该位置己经被计算过

mark[nx][ny]=true;

DFS(nx,ny);〃递归查询与该相邻位置直接相邻的点

)

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;〃初始化所有位置为未被计算

)

intans=0;〃初始化块计算器

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

有两个字符串(仅有英文小写字母组成〕A,Bo我们可以通过一些操作将A修改成乱操作

有三种：1修改一个字母，2