上机题目题解
逛超市
n=int(input())
a,b=map(float,input().split())
for i in range(n-1):
x=0.2*a+0.6*b
y=0.8*a+0.4*b
a,b=x,y
print(int(a),int(b))
按照题意计算,最后对结果取整.拿for循环算更加方便,下面是递归解法:
def f(n,x,y):
if (n==1):
return int(x),int(y)
else:
return f(n-1,0.2*x+0.6*y,0.8*x+0.4*y)
n=int(input())
a,b=map(float,input().split())
a,b=f(n,a,b)
print(a,b)
递归函数f有两个返回值,当n=1时触发边界条件停止递归.
淡黄的长裙
T=int(input())
for i in range(T):
s,a=map(int,input().split(","))
cost=100000
tot=ans=0
while s:
x=s%10000
if (abs(x-a)<=cost):
cost=abs(x-a)
ans=tot
s//=10
tot+=1
print(ans)
通过取模运算得到后四位,和最小值比较大小,如果发现小于等于的话,更新一下推的方块数量.和数字拆位的代码比较像.
客观来说,这道题放到while循环部分都是完全可以的.大部分人把这个问题都想复杂了,非要用str类型来取后四位.整数运算中的取模操作和整除操作其实是最契合题意的,完全用不到字符串和list.下面的内容也会强调代码写法的问题.
P.S. 后来发现,不存在把所有箱子都推完的数据,所以不可能有代码WA在这个点上.标程也没考虑这个情况却能通过也侧面反映了这一点.
PP.S. 有人发现我给的数据中有前导0打头的非法数据,后来和出题人沟通后发现,OJ上传的数据是他后来重新造的,我和老师手里的数据是老版本.经过检查,新数据中并不存在0打头的数据,所以也不会有人WA在这个点上.
排列组合
n,r=map(int,input().split())
ans=[]
v=[0 for i in range(25)]
def Dfs (x,s):
global v,ans
if (s==r):
c=''
for i in range(n):
if (v[i]):
c=c+str(i+1)+' '
ans.append(c)
return
if (x>=n):
return
for i in range(x+1,n):
v[i]=1
Dfs(i,s+1)
v[i]=0
for i in range(n):
v[i]=1
Dfs(i,1)
v[i]=0
for i in ans:
print(i)
具体的思路见下方的递归讲解部分.
买辣条
爆搜解法:
def Dfs(x):
global ans,cnt
if (x==n):
ans=min(ans,cnt)
return
for i in range(n):
if (v[i]==0):
v[i]=1
cnt+=a[x]%(i+1)
Dfs(x+1)
cnt-=a[x]%(i+1)
v[i]=0
n=int(input())
a=list(map(int,input().split()))
ans=0x3f3f3f3f
cnt=0
v=[0 for i in range(n)]
Dfs(0)
print(ans)
状态压缩DP解法:
n=int(input())
a=[0]
a+=list(map(int,input().split()))
INF=0x3f3f3f3f
f=[[INF for i in range(2000)] for j in range(20)]
f[0][0]=0
up=(1<<n)
for i in range(1,n+1):
for j in range(0,up):
if (f[i-1][j]!=INF):
for k in range(n):
if ((j&(1<<k)) == 0):
f[i][j|(1<<k)]=min(f[i][j|(1<<k)],f[i-1][j]+a[i]%(k+1))
print(f[n][up-1])
超纲内容,不要求掌握.感兴趣的同学可以自行学习状压DP的知识.
连锁反应
m,n=map(int,input().split(','))
r={'Q':0,'W':1,'E':2,'R':3,'T':4,'Y':5,'U':6,'I':7,'O':8,'P':9}
l=[[-1 for i in range(110)] for i in range(110)]
def Line(x):
for i in range(m):Clear(x,i)
def Row(x):
for i in range(n):Clear(i,x)
def Number(x):
for i in range(n):
for j in range(m):
if (l[i][j]==str(x)):
l[i][j]=-1
def Choose(ch,x,y):
if (ch==-1):
return
if (ch=='>'):
Line(x)
elif (ch=='v'):
Row(y)
elif (ch=='X'):
Clear(x-1,y),Clear(x+1,y)
Clear(x-1,y+1),Clear(x,y+1),Clear(x+1,y+1)
Clear(x-1,y-1),Clear(x,y-1),Clear(x+1,y-1)
elif (ch.isdigit()==0):
Number(r[ch])
def Clear(x,y):
global l
if (x<0 or y<0 or x>=n or y>=m):
return
p=l[x][y]
l[x][y]=-1
Choose(p,x,y)
for i in range(n):
s=input()
for j in range(m):
l[i][j]=s[j]
y,x=map(int,input().split(','))
Clear(x-1,y-1)
for j in range(m):
s=n
for i in range(n-1,-1,-1):
if (l[i][j]!=-1):
l[s][j]=l[i][j]
l[i][j]=-1
s-=1
for i in range(1,n+1):
for j in range(m):
if (l[i][j]==-1):
print(end=' ')
else:
print(l[i][j],end='')
print('')
这道题的解决思路是比较清晰的,关键是如何处理好各个道具的消除效果和连锁反应的情况.下面分函数讲解.
m,n=map(int,input().split(','))
r={'Q':0,'W':1,'E':2,'R':3,'T':4,'Y':5,'U':6,'I':7,'O':8,'P':9}
l=[[-1 for i in range(110)] for i in range(110)]
输入部分没有什么好说的,提前开好list准备存储(之所以不用字符串类型,是因为字符串类型是不可修改的,这样在消除环节就很难处理),建一个字典方便下面判断.这里的n,m和题目中的是反着的,因为传统的题目中给出的坐标都是先行后列,这道题是先列后行,我个人习惯了先行后列了,所以就手动反了一下.
for i in range(n):
s=input()
for j in range(m):
l[i][j]=s[j]
y,x=map(int,input().split(','))
Clear(x-1,y-1)
这部分是预处理环节.x,y因为同样的原因反了一下.因为储存的时候下标是从0开始,而题目中是从1开始,所以处理的时候还要减去1,这些细节一定要注意.Clear函数是消除函数,用于消除对应格子的函数,接下来讲解代码中的各个函数.
def Clear(x,y):
global l
if (x<0 or y<0 or x>=n or y>=m):
return
p=l[x][y]
l[x][y]=-1
Choose(p,x,y)
首先是合法性检查,如果越界的话就不处理(可能发生越界的原因下面会讲).然后记录下这个格子里是什么之后,把这一位置为-1.调用Choose函数.
def Choose(ch,x,y):
if (ch==-1):
return
if (ch=='>'):
Line(x)
elif (ch=='v'):
Row(y)
elif (ch=='X'):
Clear(x-1,y),Clear(x+1,y)
Clear(x-1,y+1),Clear(x,y+1),Clear(x+1,y+1)
Clear(x-1,y-1),Clear(x,y-1),Clear(x+1,y-1)
elif (ch.isdigit()==0):
Number(r[ch])
Choose函数的作用是判断消除的这一位是不是一个道具,如果是,触发对应的道具效果.如果这一位是-1,直接结束;如果是横向消除道具,调用Line(x);如果是纵向消除道具,调用Row(y).如果是3\times3消除道具,附近的8个格子都要被消除,那么就调用8次Clear函数.这里需要注意,如果这个道具位于边界位置,8个坐标中是可能有几个坐标越界的,这就是为什么Clear函数要检查合法性的原因.如果发现是字母,就调用Number函数消除对应的数字.
def Line(x):
for i in range(m):Clear(x,i)
消除第x行.需要遍历这一行的每一位,然后调一下Clear函数.
def Row(x):
for i in range(n):Clear(i,x)
消除第x列.需要遍历这一列的每一位,然后调一下Clear函数.
def Number(x):
for i in range(n):
for j in range(m):
if (l[i][j]==str(x)):
l[i][j]=-1
消除对应的数字.因为l里存放的是一个个字符,所以这里判断相等的时候要拿str转化一下.
至此,消除部分处理完毕.
for j in range(m):
s=n
for i in range(n-1,-1,-1):
if (l[i][j]!=-1):
l[s][j]=l[i][j]
l[i][j]=-1
s-=1
一开始,l中储存的范围是0->n-1,0->m-1.n-1表示最后一行.我们假想在这一行下面其实还有一行,其中每个元素都是-1.然后对每一列处理,让元素开始下落.s记录的是,如果上面的元素往下落,应该会落在什么位置.当检测到l[i][j]不是-1时,下落,把这一位置为-1.因为落下来了一个元素,所以s的值应该减少1,表示接下来的元素会落在更高的地方.经过这么处理,l中的储存范围变为了是1->n,0->m-1.接下来直接输出就可以了.
for i in range(1,n+1):
for j in range(m):
if (l[i][j]==-1):
print(end=' ')
else:
print(l[i][j],end='')
print('')
输出部分,-1就补空格,否则直接输出.
这种题目是比较复杂的模拟类题目,代码实现难度较大,接下来分享一下我解决这道题的过程和思路.
拿到题目后,发现这道题目的重点在于三个模块:输入模块,消除模块,下落模块.依次实现这些模块.
写输入模块时,发现字符串类型不好修改,改用list来储存.同时发现坐标是反着的,直接在输入部分处理一下就行了.
然后发现题目中给出了一个消除某个特定位置的操作,简单分析后发现其他的那些奇怪的道具也都是由消除特定位置的操作组合成的,所以需要一个函数来实现.于是有了Clear函数.我在写的时候一开始是没有边界条件判断的,而且在Clear函数里面直接写了道具类型的判断.在写3\times3消除的时候我发现可能会发生越界,于是为Clear函数加上了边界判断.
按照题意,显然我还需要Line,Row,Number这三个消除函数,接下来就是实现它们.因为我已经写好了消除特定格子的Clear函数,所以直接调用就行了.这时代码的主体部分已经写的差不多了,Choose函数是我觉得Clear函数有点冗长而专门分出去的,不分也可以.
写完之后,我并没有急着写掉落函数,而是直接写了输出,然后运行代码.因为掉落的实现比较复杂,同时会改变消除的原始结果,如果写完掉落函数再运行,一旦发生错误,我就不知道是哪里的问题了,Debug过程会非常麻烦.通过人眼实现掉落过程,核对了两个样例之后,发现消除模块没有问题,这时才开始写掉落模块.
掉落部分的思路是比较清晰的,简单推导之后就完成了书写.运行样例,发现没有问题,然后提交,AC.(大家平时写题的时候一定一定要自己造数据测试,尤其是这种情况比较复杂的题目)
接下来是一点简单的心得.这种复杂的题目很难一次性全部完成,要分模块写,每写完一个模块就测试一下,确定刚刚写完的阶段没有问题之后再写下一个模块.这可以为之后的Debug减少很多工作量.像这种带有功能各异的道具的,最好为这些道具单独写一个函数实现它们的功能,一方面调用的时候很方便,另一方面Debug的时候也容易直接检查和修正.写代码和解淑芬题是不一样的,淑芬需要先证明引理,然后一步步得出下面的结论.但是写代码不是这样,你可以自由选择书写的顺序,只要最后实现相应的功能就行.从上面的过程可以看出,我并不是先实现了各种道具的消除效果后才写的消除部分,而是先有的消除单独格子的函数再写道具的函数.模块化编程是一个很重要的思想,希望大家慢慢体会.
一些问题的说明
变量命名
“给某人一个变量名混乱的程序，你将折磨他一整天；教某人如何乱写变量名，他将折磨别人一辈子。” ——hzwer
这次答疑的时候突然发现大家的变量命名方式五花八门...突然冒出来很多abcd命名法,拼音命名法.这里简单给大家讲一下变量的命名规则.形成一个好的变量习惯一方面可以帮助别人去理解你的代码,另一方面,自己在复习的时候,可以很快速的理解过去的代码,甚至可以只凭代码去推断出题意是什么.
变量命名有很多约定俗成的习惯,例如循环遍历一般使用i,j,k,g来表示.下面是别人整理出的一个比较通用的变量命名规范,供大家参考.
注意:这个指南原本是针对C++,C用户的,极个别几个变量名在Python里是保留字,不能使用
然后变量命名也有一些忌讳,首先就是不要拿拼音全称命名,可读性差是一方面,另一方面Spyder也不提供补全功能,写起来也费时间;还有就是不要完全走字母表顺序,一个代码里有变量a,b,c是正常的,但是有a,b,c,d,e,f,g就不正常了,当代码比较长的时候你就很难知道哪个变量是什么含义了.这一点在写大作业的时候你们就体会到了.下面是我个人的一些命名习惯,仅供参考
n,m #一般存题目中的n,m
T #数据组数
s #字符串
v #记录访问性的list
dp,f #动态规划中的转移数组
ans #记录答案
flag #标记变量
cnt,tot #计数器
a,b,c,d #根据需要灵活使用
i,j,k,g #循环变量
x,y,z #根据需要灵活使用,通常拿来记录坐标
写法的选择
”经验告诉我们,一个人如果为了实现一个功能而组合使用了3个及以上的自带函数,那么他的代码有99%的可能存在Bug.这时候还不如自己造轮子.“ ——Marvolo
这次实验的第二题暴露出了很多问题,大部分人使用了Str类型来解决.首先要说明的是,Python的Str类型确实非常方便,提供的一些函数也很好用,但是这不代表Str类型可以在任何场景中使用.在第二题中,每次要推掉最后一个箱子,和这个很像的操作有两个:list的pop和整数的//10.我们需要计算的是价格差,那么用整数来处理就会更自然,方便一些.同时,题目中框住后四位数的操作,和整数中的%10000十分贴切.如果使用字符串处理，那么当剩余的箱子数少于4个时,就需要进行特判,代码会写的很麻烦.这就说明字符串和这道题并不是很契合.
很多人的代码中使用了str函数来实现整数和字符串之间的转化.这个函数其实会带来很大的时间消耗,只是这道题数据比较小体现不出来.除了输入输出等必要的处理,我们一般不会轻易把别的东西转化为字符串.因为这实在是太慢了,能用整数最好用整数.
有个比较通用的原则是,如果在一道题目中没有出现字符串,例如只是让算个价格,求和,算个函数什么的,那么字符串类型就一般不会在这道题目中使用.当然万事无绝对,如果使用字符串可以为代码带来很大程度的优化,该用还是要用的.
很多人在算最后答案的时候用到了index函数,为了找最后出现的那次又使用了list类型的reverse函数.自带的函数用起来确实很方便,但是当我们的需求比较特别时,最好还是自己造轮子.假如你不知道reverse函数,又想偷懒用index函数找到最后一个出现的最大值的位置,就会很难实现.
找最后一个出现的最大值自己实现并不是很复杂:
pos=0
x=0
for i in range(len(l)-1,-1,-1):
if (l[i]>x):
pos=i
x=l[i]
和先用find找出现次数,然后分情况判断需不需要reverse,再index的写法比要更加清晰一些.
总的原则就是,当我们的需求比较简单的时候,用自带的函数(算个最大最小值,求个和什么的);当需求比较复杂时,切忌把多个自带的函数组合使用
洛谷题目
"如果你想拿省一,那么这一年里你至少要刷够100道题目.只靠看书和上课听你是绝对学不会编程的." ——我的竞赛教练
上次给大家推荐了洛谷的题单功能,有很多同学都开始做题了,然后也发现了一些问题,需要在这里说明一下.
如果代码发生了莫名的RE,而且你确定这不是你的问题,那么请跳题.
如果发生了TLE或者MLE,而且在提交记录中没有看到一个Python的AC提交,那么请跳题.
题目中的标签功能是很重要的,如果在这些标签中看到了没见过的算法,那么大概率这题是超纲的.多个标签中最难的那个一般才是正解.
不要用那个随机题目的功能,目前能做的题目在OJ中还是占少数.个人推荐还是按照题单去刷.
知识补充
递归
引入
接下来的讲解会从头开始为大家捋一下递归算法.下面是我自己的一些理解,仅供参考.
递归引入的例题一般是斐波那契数列.当我们拿到一个公式:f(n)=f(n-1)+f(n-2),首先可以发现,求f(n)的值可以化为为两个规模更小的问题.这两个问题又可以进一步转化.通过不断转化,再结合我们已知的f(1)=f(2)=1,就能把f(n)算出来.代码实现大概是这样:
def f(n):
if n<=2:
return 1
else:
return f(n-1)+f(n-2)
上面这段代码包含了三个很重要的要素,递归状态n,边界条件n\leq2,和状态的转移.
先说边界条件,这是递归停止的标志,没有边界条件就会发生无限递归的情况,最后导致崩栈或者TLE.崩栈是一个非常常见的错误,以下面的代码为例:
def f(x):
if x==1:
return 0
return f(x-1)
print(f(2964))
根据测试,这段代码在Spyder里只能算出f(2964).(不同的电脑,编辑器可能存在差异).这是因为递归函数在调用的时候会消耗栈空间,栈空间并不是无限的,当你消耗的比被分配的还要多的时候就会提示RecursionError: maximum recursion depth exceeded in comparison,表示你的代码发生了崩栈.在本地测试的时候,如果递归是正确的,输入的数据比较大,也是有可能发生崩栈的,这时要根据OJ上的测试结果为准.OJ上的栈空间是很充裕的,只要边界条件没设错一般不会崩栈.
状态的描述
然后来看递归状态,函数里的参数n表示这个递归的进行状态.在设计一个递归时,状态的表述是非常重要的.这里有两个很大的误区:递归函数一定要return算好的结果,所有的状态一定要放到函数里.以排列组合为例,很多同学把当前选择了哪些数作为参数传了进去,其实是没有必要的.n个数选r个,那么我们就可以只用两个变量a,b表示状态,即已经决定了前面的a个数到底是选还是不选,目前一共选好了b个数.至于哪些数是被选择的,我们可以通过一个全局变量来记录.下面是代码的讲解.
def Dfs (x,s):
global v,ans
if (s==r):#选够了
c=''
for i in range(n):
if (v[i]):#这个数被选了
c=c+str(i+1)+' '#生成答案
ans.append(c)#放到答案列表里
return#边界处理完毕
if (x>=n):
return#n个数都处理好了,但是没选够
for i in range(x+1,n):#处理后面还没处理的数
v[i]=1#每个数有两种可能,选,不选.先处理选的情况,做个标记
Dfs(i,s+1)#选了这个数,s+1,继续递归
v[i]=0#不选,需要把v清空,消除影响
这个递归函数中只有两个参数,含义如上所示.s表示已经选出来了几个数,v用来记录哪个数被选了.ans是用于算最后的答案的.
首先,我们要设置边界条件.按照题意,要选出恰好r个数,那么s==r就是一个边界,这代表着我们找到了一个答案.之后把格式化好的答案放到全局变量ans里,方便后面输出.注意,即使递归下面的转移还没有写,也要先写边界的处理.我们要优先考虑问题解决时应该怎么办,至于怎么解决问题那是后面的工作,这样更不容易出Bug.从这一段的处理也可以看出,我们的递归根本就没有return有价值的信息,只是单纯的停了下来.这种操作是完全可以的,没有人规定递归的结果一定要return出去.算好了可以存起来,或者直接输出.
边界条件完全可以不止一个,因为递归的状态是多种多样的.我们在s==r设置好了边界,保证了在找够了之后不会接着找下去,也就是不会找多.但是找少的情况还没处理,完全有可能n个数都记录下状态了,但是没选够.所以,针对找少的情况还需要再补一个if.
至此,边界处理完成,下面开始分析该怎么递归下去.
for i in range(x+1,n):#处理后面还没处理的数
v[i]=1#每个数有两种可能,选,不选.先处理选的情况,做个标记
Dfs(i,s+1)#选了这个数,s+1,继续递归
v[i]=0#不选,需要把v清空,消除影响
既然前面x个数已经处理好了,那么我们就不需要管它们了,直接从x+1开始循环.每个数有选,不选两种可能,我们都要考虑进去.假如说,现在该决定第i个数的状态了,先处理选的情况,通过v数组标记,然后把更新后的状态作为参数传递下去,继续递归.这个递归可能会算出一些答案,也可能不会.这个结果我们是不考虑的,在递归结束之后,我们把标记置为0,表示不再选这个数了,然后继续循环.
可能有同学觉得在置为0之后还需要加一句Dfs(i,s)来表示不选的递归情况,这个其实是没有必要的.因为之后的循环中,假如选了i后面的某个数,那么i此时就是没有被选择的状态;如果加一句Dfs(i,s),搜到的结果就会有重复.
在找到了所有的组合方案后,题目中要求按照字典序输出,标程没有做任何处理就直接输出了.因为这个搜索过程就是按照字典序进行的,先搜的是第1个数被选的情况,然后是第1个数不选,第2个数选的情况...所以ans里面的结果直接就按照字典序排列好了,不需要额外处理.
再来看一个例子,选做题买辣条.
和排列组合比较像,这道题是把n种价格的辣条分配给n个人.我们可以使用v数组表示第i种价格的辣条是不是已经被买了,然后进行递归.
def Dfs(x):
global ans,cnt#ans为答案,cnt为当前剩余的钱数
if (x==n):#n个人已经都买完了辣条
ans=min(ans,cnt)#更新答案
return#边界处理
for i in range(n):#枚举辣条价格
if (v[i]==0):#如果这种价格的辣条还没被人买过
v[i]=1#买!
cnt+=a[x]%(i+1)#更新剩余钱数
Dfs(x+1)#让下一个人买
cnt-=a[x]%(i+1)#这个人不买这个价格的辣条了
v[i]=0#不买了,退货!
可以看出,递归的过程和排列组合非常的像.Dfs(x)表示已经有x个人买好了辣条,现在是x+1个人挑选辣条了.
首先是边界的处理,如果大家都买好了辣条,那么更新答案,return.如果没有,那么就看看还有哪个价格的辣条没有被买,找到后更新一下当前剩余钱数,让下一个人接着买.然后要消除刚刚买辣条的影响,也就是把剩余钱数变回买之前的状态,方便递归其余的情况.
不难发现,在递归之前,一定会有一个买辣条的操作,也就是在当前这个人买过了辣条之后才会递归到下一个人那里.而且买的时候是判断过不会买重的,所以这个递归可以枚举出所有的买辣条方案.
总结一下,递归的难点在于如何去描述一个状态,这个状态不一定要作为参数传递进函数里,也可以作为一个全局变量.递归函数也不一定有返回值,只要能算出结果,存起来和return其实差不多,有时候存起来比return还更加方便.
上面两道题只是抛砖引玉,对递归的掌握还是需要大量的积累.这里推荐一些洛谷的题目:
P1255 数楼梯
P1028 数的计算
P1464 Function
P1036 选数
记忆化
“一个搜索如果没有记忆化,那么和暴力又有什么区别呢?” ——Marvolo
还是以斐波那契为例,讲一下记忆化搜索的概念.
def f(n):
if n<=2:
return 1
else:
return f(n-1)+f(n-2)
当我们使用上面的函数来计算数列时,不难发现,如果算f(10),会先调用f(9),然后f(9)会接着调用f(8),......直到算出了结果.然后f(10)还会再调用一次f(8),也就是f(8)这个结果算了2次.这会带来很大的时间消耗,因为我们进行了大量的重复运算.记忆化的思想就是,把算过的结果存起来,下次再碰见时,如果发现算过了,就不再算了.
添加了记忆化之后的代码:
def f(n):
global v
if n<=2:
return 1
else:
if v[n]>0:#之前算过
return v[n]#用现成的
x=f(n-1)+f(n-2)#没算过就现在算
v[n]=x#存下来
return x
本文地址: Python第六周周报
