本文主要是介绍topcoder 刷题笔录 初级篇（一），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
摘要：本系列文章为在topcoder上(包括部分其他平台)的刷题记录和心得，计划刷题500道。其中，初级题目30道，撰文三篇；中级题目60道，撰文六篇；其他高级题目100道，撰文10篇。
1.题目1——SRM146 DIV1（300‘）
Problem StatementGiven the width and height of a rectangular grid, return the total number of rectangles (NOT counting squares) that can be found on this
grid.
For example, width = 3, height = 3 (see diagram below):__ __ __
|__|__|__|
|__|__|__|
|__|__|__|
In this grid, there are 4 2x3 rectangles, 6 1x3 rectangles and 12 1x2 rectangles. Thus there is a total of 4 + 6 + 12 = 22 rectangles.Note we don't count 1x1, 2x2 and 3x3 rectangles because they are squares.
DefinitionClass:
RectangularGrid
Method:
countRectangles
Parameters:
integer, integer
Returns:
long integer
Method signature:
def countRectangles(self, width, height):LimitsTime limit (s):
2.000
Memory limit (MB):
64
Notes
-
rectangles with equals sides (squares) should not be counted.
Constraints
-
width and height will be between 1 and 1000 inclusive.
Examples
0)3
3
Returns: 22
See above
1)5
2
Returns: 31__ __ __ __ __
|__|__|__|__|__|
|__|__|__|__|__|
In this grid, there is one 2x5 rectangle, 2 2x4 rectangles, 2 1x5 rectangles, 3 2x3 rectangles, 4 1x4 rectangles, 6 1x3 rectangles and
13 1x2 rectangles. Thus there is a total of 1 + 2 + 2 + 3 + 4 + 6 + 13 = 31 rectangles.
2)10
10
Returns: 26403)1
1
Returns: 04)592
964
Returns: 81508708664
分析：这是一道考察计数问题的题目，我们采用组合数学（实际上是高中的计数知识）中的分步计数和分类计数原来，先计算所有方形的个数，再计算所有正方形的个数，二者相减即可得到答案。其中，计算方形的个数，我们采用分步计数原来，先算长边个数，再算宽边个数，二者相乘即可得到答案。
代码：
class RectangularGrid:def countRectangles(self,aa,bb):a=aab=bbif aa < bb:a=bbb=aatotal=(a+1)*a*b*(b+1)/4i=bsqua=0while i>=1:squa+=i*(a-b+i)i-=1 return total-squa2.题目2 SRM144 DIV1（300‘）
Problem StatementLet's say you have a binary string such as the following:
011100011
One way to encrypt this string is to add to each digit the sum of its adjacent digits. For example, the above string would become:
123210122
In particular, if P is the original string, and Q is the encrypted string, then Q[i] = P[i-1] + P[i] + P[i+1] for all digit positions i.Characters off the left and right edges of the string are treated as zeroes.
An encrypted string given to you in this format can be decoded as follows (using 123210122 as an example):
Assume P[0] = 0.
Because Q[0] = P[0] + P[1] = 0 + P[1] = 1, we know that P[1] = 1.
Because Q[1] = P[0] + P[1] + P[2] = 0 + 1 + P[2] = 2, we know that P[2] = 1.
Because Q[2] = P[1] + P[2] + P[3] = 1 + 1 + P[3] = 3, we know that P[3] = 1.
Repeating these steps gives us P[4] = 0, P[5] = 0, P[6] = 0, P[7] = 1, and P[8] = 1.
We check our work by noting that Q[8] = P[7] + P[8] = 1 + 1 = 2. Since this equation works out, we are finished, and we have recoveredone possible original string.
Now we repeat the process, assuming the opposite about P[0]:
Assume P[0] = 1.
Because Q[0] = P[0] + P[1] = 1 + P[1] = 1, we know that P[1] = 0.
Because Q[1] = P[0] + P[1] + P[2] = 1 + 0 + P[2] = 2, we know that P[2] = 1.
Now note that Q[2] = P[1] + P[2] + P[3] = 0 + 1 + P[3] = 3, which leads us to the conclusion that P[3] = 2. However, this violates
the fact that each character in the original string must be '0' or '1'. Therefore, there exists no such original string P where thefirst digit is '1'.
Note that this algorithm produces at most two decodings for any given encrypted string. There can never be more than one possible
way to decode a string once the first binary digit is set.
Given a string message, containing the encrypted string, return a tuple (string) with exactly two elements. The first element should
contain the decrypted string assuming the first character is '0'; the second element should assume the first character is '1'. If
one of the tests fails, return the string "NONE" in its place. For the above example, you should return {"011100011", "NONE"}.
DefinitionClass:
BinaryCode
Method:
decode
Parameters:
string
Returns:
tuple (string)
Method signature:
def decode(self, message):LimitsTime limit (s):
2.000
Memory limit (MB):
64
Constraints
-
message will contain between 1 and 50 characters, inclusive.
-
Each character in message will be either '0', '1', '2', or '3'.
Examples
0)"123210122"
Returns: { "011100011", "NONE" }
The example from above.
1)"11"
Returns: { "01", "10" }
We know that one of the digits must be '1', and the other must be '0'. We return both cases.
2)"22111"
Returns: { "NONE", "11001" }
Since the first digit of the encrypted string is '2', the first two digits of the original string must be '1'. Our test fails when wetry to assume that P[0] = 0.
3)"123210120"
Returns: { "NONE", "NONE" }
This is the same as the first example, but the rightmost digit has been changed to something inconsistent with the rest of the originalstring. No solutions are possible.
4)"3"
Returns: { "NONE", "NONE" }5)"12221112222221112221111111112221111"
Returns:
{ "01101001101101001101001001001101001","10110010110110010110010010010110010" }题目分析：这道题目没有算法方面的难度，需要处理好边界条件即可，另外就是注意字符串和list等结构的转化。
代码：
import string
class BinaryCode:def decode(self,input):length=len(input)i=0q=list(input)q.append('1')q.insert(0,'1')index=0for one in q:q[index]=string.atoi(one)index=index+1pone=(length+2)*[1]pone[0]=0pone[1]=0i=1while i<length+1:pone[i+1]=q[i]-pone[i-1]-pone[i]if pone[i+1]!=0 and pone[i+1]!=1:breaki=i+1if i==length+1 and pone[i]==0:passelse:pone=["NONE"]pone=[1]+pone+[1]pone=pone[1:-1]index=0for each in pone:pone[index]=str(each)index=index+1ponestring=string.join(pone,"")ptwo=(length+2)*[1]ptwo[0]=0ptwo[1]=1i=1while i<length+1:ptwo[i+1]=q[i]-ptwo[i-1]-ptwo[i]if ptwo[i+1]!=0 and ptwo[i+1]!=1:breaki=i+1if i==length+1 and ptwo[i]==0:passelse:ptwo=["NONE"]ptwo=[0]+ptwo+[0]ptwo=ptwo[1:-1]index=0for each in ptwo:ptwo[index]=str(each)index=index+1ptwostring=string.join(ptwo,"")return (ponestring,ptwostring)
题目：
Problem StatementComputers tend to store dates and times as single numbers which represent the number of seconds or milliseconds since a particular date.
Your task in this problem is to write a method whatTime, which takes an integer, seconds, representing the number of seconds since
midnight on some day, and returns a string formatted as "<H>:<M>:<S>". Here, <H> represents the number of complete hours since midnight,
<M> represents the number of complete minutes since the last complete hour ended, and <S> represents the number of seconds since the
last complete minute ended. Each of <H>, <M>, and <S> should be an integer, with no extra leading 0's. Thus, if seconds is 0, you should
return "0:0:0", while if seconds is 3661, you should return "1:1:1".
DefinitionClass:
Time
Method:
whatTime
Parameters:
integer
Returns:
string
Method signature:
def whatTime(self, seconds):LimitsTime limit (s):
2.000
Memory limit (MB):
64
Constraints
-
seconds will be between 0 and 24*60*60 - 1 = 86399, inclusive.
Examples
0)0
Returns: "0:0:0"1)3661
Returns: "1:1:1"2)5436
Returns: "1:30:36"3)86399
Returns: "23:59:59"class Time:def whatTime(self,seconds):second=seconds%60mins=seconds/60min=mins%60hours=mins/60now=str(hours)+":"+str(min)+":"+str(second)return now4. 题目 SRM 145 DIV 1（250‘）
题目：
Problem StatementYou have a certain amount of money to give out as a bonus to employees. The trouble is, who do you pick to receive what bonus? You decide
to assign a number of points to each employee, which corresponds to how much they helped the company in the last year. You are given an
tuple (integer) points, where each element contains the points earned by the corresponding employee (i.e. points[0] is the number ofpoints awarded to employee 0). Using this, you are to calculate the bonuses as follows:
- First, add up all the points, this is the pool of total points awarded. - Each employee gets a percentage of the bonus money, equal to
the percentage of the point pool that the employee got. - Employees can only receive whole percentage amounts, so if an employee's cutof the bonus has a fractional percentage, truncate it. - There may be some percentage of bonus left over (because of the fractional
truncation). If n% of the bonus is left over, give the top n employees 1% of the bonus. There will be no more bonus left after this.
If two or more employees with the same number of points qualify for this "extra" bonus, but not enough bonus is left to give them all anextra 1%, give it to the employees that come first in points.
The return value should be a tuple (integer), one element per employee in the order they were passed in. Each element should be the
percent of the bonus that the employee gets.
DefinitionClass:
Bonuses
Method:
getDivision
Parameters:
tuple (integer)
Returns:
tuple (integer)
Method signature:
def getDivision(self, points):LimitsTime limit (s):
2.000
Memory limit (MB):
64
Constraints
-
points will have between 1 and 50 elements, inclusive.
-
Each element of points will be between 1 and 500, inclusive.
Examples
0){1,2,3,4,5}
Returns: { 6, 13, 20, 27, 34 }
The total points in the point pool is 1+2+3+4+5 = 15. Employee 1 gets 1/15 of the total pool, or 6.66667%, Employee 2 gets 13.33333%,
Employee 3 gets 20% (exactly), Employee 4 gets 26.66667%, and Employee 5 gets 33.33333%. After truncating, the percentages look like:
{6,13,20,26,33} Adding up all the fractional percentages, we see there is 2% in extra bonuses, which go to the top two scorers. These
are the employees who received 4 and 5 points.
1){5,5,5,5,5,5}
Returns: { 17, 17, 17, 17, 16, 16 }
The pool of points is 30. Each employee got 1/6 of the total pool, which translates to 16.66667%. Truncating for all employees, we are
left with 4% in extra bonuses. Because everyone got the same number of points, the extra 1% bonuses are assigned to the four that come
first in the array.
2){485, 324, 263, 143, 470, 292, 304, 188, 100, 254, 296,255, 360, 231, 311, 275, 93, 463, 115, 366, 197, 470}
Returns:
{ 8, 6, 4, 2, 8, 5, 5, 3, 1, 4, 5, 4, 6, 3, 5, 4, 1, 8,1, 6, 3, 8 }This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this
information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2003, TopCoder, Inc. All rights reserved.分析：关键在于排序
代码：
class Bonuses:def getDivision(self,points):length=len(points)sum=0for each in points:sum+=eachpercent=list(points)for i in range(length):percent[i]=percent[i]*100/sumtotal=0for each in percent:total+=eachbonus=100-totalprint bonusaddindex=[[0,0]]*lengthfor each in range(length):addindex[each]=[percent[each],each]addindex.sort(key=lambda l:(l[0],l[1]),reverse=True)i=0 while i<bonus:addindex[i][0]+=1i+=1addindex.sort(key=lambda l:(l[1]))print "addindex=",addindexfor each in range(length):percent[each]=addindex[each][0]print tuple(percent)return tuple(percent)5.题目 SRM 499 DIV 1(250')
题目：
Problem StatementCat Pochi visited a town of rabbits and asked some of the rabbits the following question: "How many rabbits in this town other than
yourself have the same color as you?". The rabbits all replied truthfully, and no rabbit was asked the question more than once. You are
given the rabbits' replies in the tuple (integer) replies. Return the minimum possible number of rabbits in this town.
DefinitionClass:
ColorfulRabbits
Method:
getMinimum
Parameters:
tuple (integer)
Returns:
integer
Method signature:
def getMinimum(self, replies):LimitsTime limit (s):
2.000
Memory limit (MB):
64
Constraints
-
replies will contain between 1 and 50 elements, inclusive.
-
Each element of replies will be between 0 and 1,000,000, inclusive.
Examples
0){ 1, 1, 2, 2 }
Returns: 5
If there are 2 rabbits with a color and 3 rabbits with another color, Pochi can get this set of replies.
1){ 0 }
Returns: 1
A poor lonely rabbit.
2){ 2, 2, 44, 2, 2, 2, 444, 2, 2 }
Returns: 499This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this
information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2003, TopCoder, Inc. All rights reserved.分析：关键在于排序
代码：
Problem StatementCat Pochi visited a town of rabbits and asked some of the rabbits the following question: "How many rabbits in this town other than
yourself have the same color as you?". The rabbits all replied truthfully, and no rabbit was asked the question more than once. You aregiven the rabbits' replies in the tuple (integer) replies. Return the minimum possible number of rabbits in this town.
DefinitionClass:
ColorfulRabbits
Method:
getMinimum
Parameters:
tuple (integer)
Returns:
integer
Method signature:
def getMinimum(self, replies):LimitsTime limit (s):
2.000
Memory limit (MB):
64
Constraints
-
replies will contain between 1 and 50 elements, inclusive.
-
Each element of replies will be between 0 and 1,000,000, inclusive.
Examples
0){ 1, 1, 2, 2 }
Returns: 5
If there are 2 rabbits with a color and 3 rabbits with another color, Pochi can get this set of replies.
1){ 0 }
Returns: 1
A poor lonely rabbit.
2){ 2, 2, 44, 2, 2, 2, 444, 2, 2 }
Returns: 499This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this informatio
n without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2003, TopCoder, Inc. All rights reserved.6.题目SRM 146 DIV2（250‘）
题目：
Problem StatementThis task is about the scoring in the first phase of the die-game Yahtzee, where five dice are used. The score is determined by the
values on the upward die faces after a roll. The player gets to choose a value, and all dice that show the chosen value are considered
active. The score is simply the sum of values on active dice.
Say, for instance, that a player ends up with the die faces showing 2, 2, 3, 5 and 4. Choosing the value two makes the dice showing 2
active and yields a score of 2 + 2 = 4, while choosing 5 makes the one die showing 5 active, yielding a score of 5.
Your method will take as input a tuple (integer) toss, where each element represents the upward face of a die, and return the maximum
possible score with these values.
DefinitionClass:
YahtzeeScore
Method:
maxPoints
Parameters:
tuple (integer)
Returns:
integer
Method signature:
def maxPoints(self, toss):LimitsTime limit (s):
2.000
Memory limit (MB):
64
Constraints
-
toss will contain exactly 5 elements.
-
Each element of toss will be between 1 and 6, inclusive.
Examples
0){ 2, 2, 3, 5, 4 }
Returns: 5
The example from the text.
1){ 6, 4, 1, 1, 3 }
Returns: 6
Selecting 1 as active yields 1 + 1 = 2, selecting 3 yields 3, selecting 4 yields 4 and selecting 6 yields 6, which is the maximum number
of points.
2){ 5, 3, 5, 3, 3 }
Returns: 10This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this
information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2003, TopCoder, Inc. All rights reserved.代码：
class YahtzeeScore:def maxPoints(self,tfive):score=[0]*7for each in tfive:score[each]+=eachresult=max(score)return result
得分：
236
7.题目SRM147-1
题目：
Problem StatementThere are numMales males and numFemales females arranged in a circle. Starting from a given point, you count clockwise and remove the K'thperson from the circle (where K=1 is the person at the current point, K=2 is the next person in the clockwise direction, etc...). Afterremoving that person, the next person in the clockwise direction becomes the new starting point. After repeating this procedure
numFemales times, there are no females left in the circle.
Given numMales, numFemales and K, your task is to return what the initial arrangement of people in the circle must have been, starting
from the starting point and in clockwise order.
For example, if there are 5 males and 3 females and you remove every second person, your return String will be "MFMFMFMM".
DefinitionClass:
PeopleCircle
Method:
order
Parameters:
integer, integer, integer
Returns:
string
Method signature:
def order(self, numMales, numFemales, K):LimitsTime limit (s):
2.000
Memory limit (MB):
64
Constraints
-
numMales is between 0 and 25 inclusive
-
numFemales is between 0 and 25 inclusive
-
K is between 1 and 1000 inclusive
Examples
0)5
3
2
Returns: "MFMFMFMM"
Return "MFMFMFMM". On the first round you remove the second person - "M_MFMFMM". Your new circle looks like "MFMFMMM" from your newstarting point. Then you remove the second person again etc.
1)7
3
1
Returns: "FFFMMMMMMM"
Starting from the starting point you remove the first person, then you continue and remove the next first person etc. Clearly, all thefemales are located at the beginning. Hence return "FFFMMMMMMM"
2)25
25
1000
Returns: "MMMMMFFFFFFMFMFMMMFFMFFFFFFFFFMMMMMMMFFMFMMMFMFMMF"3)5
5
3
Returns: "MFFMMFFMFM"
Here we mark the removed people with '_', and the starting position with lower-case:
Number of | People Remaining
Rounds | (in initial order)
---------------+-----------------0 | mFFMMFFMFM1 | MF_mMFFMFM2 | MF_MM_fMFM3 | MF_MM_FM_m4 | M__mM_FM_M5 | M__MM__m_M
4)1
0
245
Returns: "M"This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of thisinformation without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2003, TopCoder, Inc. All rights reserved.代码：
import string
class PeopleCircle:def order(self,Mnum,Fnum,K):people=["M"]*(Mnum+Fnum)sum=Mnum+Fnumi=0cur=0while i<Fnum:step=0total=Kwhile step<total:if people[(cur+step)%sum]!="M":total+=1step+=1people[(cur+step-1)%sum]="F"cur=(cur+step)%sumi+=1mystr=string.join(people,"")print mystrreturn mystr得分：145
心得：本来准备使用逆向算法，逆着问题的形成过程求解，结果这个算法复杂而且耽误时间。后来改用正向解法，不仅思路清晰，而且时间复杂度大概是Fnum*K，在许可范围内。所以，在动手编程以前，宏观考虑一下算法和预估时间复杂度是一个很好的习惯。
8.题目：SRM 147-2
问题：
Problem StatementJulius Caesar used a system of cryptography, now known as Caesar Cipher, which shifted each letter 2 places further through the alphabet(e.g. 'A' shifts to 'C', 'R' shifts to 'T', etc.). At the end of the alphabet we wrap around, that is 'Y' shifts to 'A'.
We can, of course, try shifting by any number. Given an encoded text and a number of places to shift, decode it.
For example, "TOPCODER" shifted by 2 places will be encoded as "VQREQFGT". In other words, if given (quotes for clarity) "VQREQFGT" and
2 as input, you will return "TOPCODER". See example 0 below.
DefinitionClass:
CCipher
Method:
decode
Parameters:
string, integer
Returns:
string
Method signature:
def decode(self, cipherText, shift):LimitsTime limit (s):
2.000
Memory limit (MB):
64
Constraints
-
cipherText has between 0 to 50 characters inclusive
-
each character of cipherText is an uppercase letter 'A'-'Z'
-
shift is between 0 and 25 inclusive
Examples
0)"VQREQFGT"
2
Returns: "TOPCODER"1)"ABCDEFGHIJKLMNOPQRSTUVWXYZ"
10
Returns: "QRSTUVWXYZABCDEFGHIJKLMNOP"2)"TOPCODER"
0
Returns: "TOPCODER"3)"ZWBGLZ"
25
Returns: "AXCHMA"4)"DBNPCBQ"
1
Returns: "CAMOBAP"5)"LIPPSASVPH"
4
Returns: "HELLOWORLD"代码：
import string
class CCipher:def decode(self,mystring,num):mylist=list(mystring)arr=range(len(mylist))for each in arr:mylist[each]=ord(mylist[each])mylist[each]-=numif mylist[each]<65:mylist[each]+=26mylist[each]=chr(mylist[each])mystring=string.join(mylist,"")return mystring 得分：220
思考：python中的字符是不能进行加减操作的，需要字符和整数的转化需要借助函数ord和chr。另外，如果提升自己的编程效率。
9.题目
题目描述：
POJ1852：http://poj.org/problem?id=1852
代码：
#include<stdlib.h>
#include<stdio.h>
int countAnt(int length,int num,int *a,int *minp,int *maxp);
int main(){int n,length,num,x[100000],result[100000][2];scanf("%d",&n);int j,i;for(i=0;i<n;i++){scanf("%d%d",&length,&num);for(j=0;j<num;j++){scanf("%d",&x[j]);}countAnt(length,num,x,&(result[i][0]),&(result[i][1]));}for(i=0;i<n;i++){printf("%d %d\n",result[i][0],result[i][1]);}}int countAnt(int length,int num,int *a,int *minp,int *maxp){int i;float mid=length*1.0/2;int small,large;int ss=-1,lar=-1;for(i=0;i<num;i++){if(a[i]<mid){small=a[i];large=length-a[i];}if(a[i]>=mid){small=length-a[i];large=a[i];}if(small>ss){ss=small;}if(large>lar){lar=large;}}*minp=ss;*maxp=lar;return 1;
}10.题目：部分和问题
题目描述：给定整数a1，a2.。。。an，判断是否可以从中选出若干数，使得它们的和正好为K
输入：n=4，a=【1，2，4，7】，K=13
输出：OK！
题目分析：这是一个DSP问题，解空间比较确定，思考的时候可以想想如何减小问题规模。如果用子问题的解来构造问题的解法。另外，递归程序的设计，需要设计好递归函数的参数和功能，这样才不至于迷惑。
参考代码：
class NumCount:def countNum(self,sum,index,array,length,key):if sum==key:return Trueif index==length:return False#fetch indexif sum+array[index]<= key:if self.countNum(sum+array[index],index+1,array,length,key):return True#not fetch indexif self.countNum(sum,index+1,array,length,key):return Truereturn False
这篇关于topcoder 刷题笔录 初级篇（一）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
