大学ACM考试题目及作业答案整理.pdfVIP

太上有立德，其次有立功，其次有立言，虽久不废，此谓不朽。——《左传》

ACM作业与答案整理

1、平面分割方法：设有n条封闭曲线画在平面上，而任何两条封闭曲线恰好相

交于两点，且任何三条封闭曲线不相交于同一点，问这些封闭曲线把平面分割

成的区域个数。

#includeiostream.h

intf(intn)

{

if(n==1)return2;

elsereturnf(n-1)+2*(n-1);

}

voidmain()

{

intn;

while(1)

{

cinn;

coutf(n)endl;

}

}

2、LELE的RPG难题：有排成一行的ｎ个方格，用红(Red)、粉(Pink)、绿(Green)

三色涂每个格子，每格涂一色，要求任何相邻的方格不能同色，且首尾两格也

不同色．编程全部的满足要求的涂法.

#includeiostream.h

intf(intn)

{

if(n==1)return3;

elseif(n==2)return6;

elsereturnf(n-1)+f(n-2)*2;

}

voidmain()

{

intn;

while(1)

{

cinn;

coutf(n)endl;

}

}

太上有立德，其次有立功，其次有立言，虽久不废，此谓不朽。——《左传》

3、北大ACM(1942)

PathsonaGrid

TimeLimit:1000MSMemoryLimit:30000K

Description

Imagineyouareattendingyourmathlessonatschool.Onceagain,youarebored

becauseyourteachertellsthingsthatyoualreadymasteredyearsago(thistime

222

hesexplainingthat(a+b)=a+2ab+b).Soyoudecidetowasteyourtimewith

drawingmodernartinstead.

Fortunatelyyouhaveapieceofsquaredpaperandyouchoosearectangleofsize

n*monthepaper.Letscallthisrectangletogetherwiththelinesitcontainsagrid.

Startingatthelowerleftcornerofthegrid,youmoveyourpenci