一、TopCoder提供的Google比赛模拟题（由作者翻译），版权所有

问题1：
造一个长方形的房子，门窗墙为基本单元，长度均为4米，在以下条件下如何摆放四面墙能围成最大面积？
1) 一面最多有一个门
2) 房子至少有一个门
3) 门不能安在角落里
4) 窗的两侧都要是墙

已知墙的个数numReg, 窗的个数numWin, 门的个数numDoor，写一个函数maxArea，返回四面墙能围成的最大面积

举例如下
maxArea(8,0,0)=0;//因为房子不能没有门
maxArea(8,0,1)=48;//12*4,
如：
－－－ 三个墙
｜　｜ 两边各一个墙
－Ｄ－ 两个墙夹一个门

maxArea(9,8,2)=144;//12*12,如：
－Ｄ－ 两个墙夹一个门
｜　｜ 两边各一个墙
Ｗ　Ｗ 两边各一个窗户
｜　｜ 两边各一个墙
－Ｄ－ 两个墙夹一个门

maxArea(6,23,13)=48;//12*4,如：
－Ｗ－ 两个墙夹一个窗户
｜　｜ 两边各一个墙
－Ｄ－ 两个墙夹一个门

问题二：
各个细胞都有其自身的分数，某协议表示存在一个临界值（允许小数），凡是分数小于该值的一般不得癌，反之就得癌。当然也会存在出错的，出错的记下其方差（即分数和临界值的差的平方），符合该协议的则方差为0，而平均方差是所有方差的平均。
已知一系列细胞的分数(整数，2到50之间)及其得癌与否（C表示得了，N表示未得），求在所有可能的临界值中最小的平均方差

举例如下
{3,3,1,8}
"NNNC"
=0;//如果选择临界值为5，则均符合规律，方差均为0，故为(0+0+0+0)/4

{5,2,3,6}
"CCNC"
=0.125;//如果选择临界值为2.5，2和3不符合规律，故为(0+(2.5-2)^2 +(3-2.5)^2+0)/4 = 0.125

{5,2,3,6,2}
"CCNCN"
=0.1;//如果选择临界值为2.5，2和3不符合规律，故为(0+(2.5-2)^2 +(3-2.5)^2+0+0)/5 = 0.1

{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20}
"NNNCNNNCNNNCNCCCCCCC"
=2.34

问题三：
要重排英文小写字母表的字母顺序，通过一串由B和A组成的规则字符串限制相邻字母的关系，如规则字符串第一个字符表示a和b之间的先后关系，第二个表示b和c之间的先后关系，以此类推
B表示必须在..前，A表示必须在..后，如BAA表示，a必须在b前，b必须在c后，c必须在d后
没有提供相互关系的字母不能出现，即如果该规则字符串有k个字母，则字母表只包含从a开始的k+1个字母，如BAA只提供了abcd之间的关系，不包含d之后的字母

已知该规则字符串decree，写一个方法choices，求符合该规则的字母表的个数，如果超过1,000,000,000就返回 -1.
举例如下
"BAA"=3;//表示a必须在b前，b必须在c后，c必须在d后，可能组合为 adcb, dacb, dcab

"AAAA"=1;//edcba为唯一可能
"BABABABABABABABABABABABAB"=-1;//超过1,000,000,000种可能

（要求一小时内完成）

出处：蓝色理想
责任编辑：蓝色

上一页 下一页 中学生一天的解答

◎进入论坛网络编程版块参加讨论