上机题目题解
修电脑
n=int(input())
l=[]
for i in range(n):
c=input()
if (c=='Ctrl+Z'):
l.pop()
else:
l.append(c)
print(l[0],end='')
for i in range(1,len(l)):
print('/'+l[i],end='')
根据题意,通过一个list实现栈的功能.最后注意下输出的格式就好了
老千层饼
这道题的解法非常多,首先是使用队列的解法:
n=int(input())
l=[]
for i in range(1,10):
l.append(i)
while n>1:
x=l.pop(0)
y=x%10
if y!=0:
l.append(x*10+y-1)
l.append(x*10+y)
if y!=9:
l.append(x*10+y+1)
n-=1
print(l[0])
按照Hint中给出的思路去做就好了.注意末尾为0或9时的特殊处理.
还有一个递推思想的解法.如果一个数x是千层饼数,那么x//10显然是.我们可以暴力枚举一个很大范围的数,通过这种方式把千层饼数都筛出来.筛的思路是根据最后两位数判断,和队列解法的把一个数后面再添上一个数的思路很接近.
n=int(input())
l=[0 for i in range(3010)]#存放筛出来的结果
v=[0 for i in range(1200000)]#标记数组,如果为0说明不是千层饼数
tot=0#统计筛出来了几个
for i in range(1,10):
tot+=1
v[i]=l[tot]=i#先把那些个位数处理了
for i in range(10,1122112):#暴力枚举(这个上限是提前算出来的)
if (v[i//10]==0):
continue#根据上面的充分性条件去掉一些数
if (abs(i%10-(i//10)%10)<=1):#在这个条件下,只需要判断最后一位就行了
tot+=1
v[i]=l[tot]=i#记录的同时打个标记
print(l[n])
最后是暴力解法:
n=int(input())
l=[0 for i in range(3010)]
tot=0
for i in range(1,800000):
if (abs(i%10-(i//10)%10)>1 and i>10):
continue#剪枝*1
if (abs((i//100)%10-(i//10)%10)>1 and i>100):
continue#剪枝*2
x=i
y=x%10
flag=0
while x>0:#大家很熟悉的拆位操作
if (abs(y-x%10)>1):
flag=1
break
y=x%10
x//=10
if (flag==0):
tot+=1
l[tot]=i
print(l[n])
和上面的思路一样,也是在一个范围内暴力去找.不过这个解法是真正的暴力思想,把一个数的每一位都拆出来然后验证.数据很强,可能会TLE,所以上面加了两个剪枝操作.如果个位十位,十位百位相差超过1,就不拆分了,直接算下一个数.
破解虫洞
首先是使用了栈的解法(通过list模拟):
def f(x,y):
return (x+42*y)/(42*x+y)
def g(x,y):
return x*y/(42*x-42*y)
s=input()
l=[]
for i in s:
if i.isdigit():
l.append(int(i))
if i.isalpha():
l.append(i)
if i==')':
if l[-3]=='f':
x=f(l[-2],l[-1])
else:
x=g(l[-2],l[-1])
l.pop()
l.pop()
l.pop()
l.append(x)
print('%.7f'%l[0])
需要注意一下中间的运算结果可能是小数,所以在计算函数值的时候不能加int()
其实这道题可以拿eval直接秒,考试的时候有人就发现了这一点并顺利拿到了1血.
def f(x,y):
return (x+42*y)/(42*x+y)
def g(x,y):
return x*y/(42*x-42*y)
print("%.7f"%eval(input()))
合理复习
结论:当\sum_{i=1}^{n}i \geq a+b时,n即为解.
证明1:
显然,时间总和要大于等于a+b才可能是解.下面证明大于等于a+b的第一个n就是解.
这n个数随便分成两堆,如果恰好一堆是a,一堆是b,证毕.
如果不是,假如一堆比a大,那么分给这一堆的数中,一定存在一个数x,使得x-1在另外一堆中.这个是显然的.交换x和x-1.这一堆的时间总和少了1s,如果这堆还比a大,重复以上过程,直到调整为a.此时另一堆的数的总和一定不小于b,故得到了一个分配方案,证毕.
证明2:
首先把a和n比较大小,如果n小于等于a,就让a减去n.然后再和n-1比较.不断重复以上过程直到a为0.(显然可以证明a一定可以恰好减到了0).那么是否被a减去就把这些数分成了两堆,就是一个方案.
下面是暴力解法,直接枚举n,通过等差数列求和式判断.
a,b=map(int,input().split())
s=(a+b)*2
for i in range(1,2000000):
if (i*(i+1)>=s):
print(i)
break
巧妙一些的解法:
a,b=map(int,input().split())
s=(a+b)*2
n=int(s**0.5)
while (n-1)*n>=s:
n-=1
while n*(n+1)<s:
n+=1
print(n)
这里直接开根得到了n的估计值,然后再进行调整.当然也可以直接解一个一元二次方程组.
复杂相对分子质量
这道题的解法比较复杂.代码分为两部分,第一部分是对化学式的预处理,首先要把化学式中的元素符号,数字,括号全部都拆分开,尤其要让隐藏的1显现出来.之后通过一个栈来计算分子量,原理和第三题类似.具体细节见代码.
Ar={'H':1.007,'C':12.011,'N':14.007,'O':15.999}
P=['H','C','N','O']
def Clear(tot):
ans.pop()#弹出)
y=0
while ans[-1]!='(':
y+=ans.pop()#两个括号间一定只剩下了数字
ans.pop()#弹出左括号
ans.append(y*tot)#放入分子量
c=input().strip()+'H'#加一个H是方便处理化学式最后的数字
l=[]
ans=[]
x=-1
'''
1的处理比较复杂,如果出现了右括号或者字母,那么后面就可能隐藏了1
如果一开始遇到的是左括号,前面不一定隐藏了1
x=-1表示前面没有隐藏1的可能
'''
for i in c:
if i=='(':
if (x!=-1):
if (x==0):
x=1#隐藏的1
l.append(x)
x=-1
l.append(i)
elif i==')' or i.isalpha():
if (x!=-1):
if (x==0):
x=1
l.append(x)
x=0#出现了括号或者字母,可能隐藏1
l.append(i)
else:
x=x*10+ord(i)-48#多位数字的处理
l.pop()#把最后的H去掉
for i in l:
if i=='(' or i==')' or i in P:
ans.append(i)
else:
if ans[-1]==')':
Clear(i)#检测到)就处理
else:
x=Ar[ans.pop()]*i#i是数字,那么前面一定是字母,把字母取出
ans.append(x)#把分子量放进去,这样保证了栈里只有()和数字
print('%.2f'%sum(ans))#最后把分子量加起来
对1的处理是一个难点.如果碰到了)或者字母,那么这一位后面有可能隐藏了1,x要置为0.如果碰到了(,说明后面是不具备隐藏1的条件的,x置为-1.然后根据x是否等于0来判断是否隐藏了1.
有同学在这道题上出现了TLE,0.9分的情况.这可能是OJ的评测机不稳定引起的,重新提交一次就有可能通过.当然也有可能是代码本身的问题,例如上周的最后一题的k=1.
枚举的艺术
首先看一道例题:输出从n个数中选出r个数的所有可能,也就是C_{n}^{r}中所有的组合(不用考虑顺序).例如n=5,r=3时,答案为
1 2 3
1 2 4
1 2 5
1 3 4
1 3 5
1 4 5
2 3 4
2 3 5
2 4 5
3 4 5
分析一下,这道题的难点在于如何得到一个长度为r的组合序列.这类题目的解法属为枚举,我们要做的,是把所有取数的情况全部都列举出来,然后选出恰好取了r个数的方案.
每一个数是否被选取有两种情况,选,或者不选,没有中间态.这很容易让人联想到二进制中的0和1.我们接下来也会借助二进制来枚举这一过程.
考虑一个长度为n位的二进制数,为了和计算机中的情况统一,这里下标从0开始.第i位的值代表2^{i}.第i位如果为1,表示选择第i+1个数(因为下标是从0开始的,题目中是从1开始,所以要错一位).否则表示不选.
这么一个二进制数的范围很容易得到,就是0到2^{n}-1.正好代表了全不选和全选这两个极端情况.中间的二进制数和选数方案是一一对应的.接下来我们要做的,就是枚举这个范围内的每一个数,然后把它拆成二进制,得到一个选数方案,并从中找到我们需要的.
下面是示例代码:
n,r=map(int,input().split())
up=(2**n)
for i in range(up):
v=[0 for i in range(n)]
tot=0
for j in range(n):
if ((1<<j)&i):
v[j]=1
tot+=1
if (tot==r):
for j in range(n):
if (v[j]):
print("%d "%(j+1),end='')
print('')
因为循环上界是固定的,为了避免在每次循环的时候都重新算一遍,这里用up提前存好了.(如果循环比较大的话,使用这个方法可以稍微减少一点时间消耗.)之后开了一个长度为n位的list,用来记录第i位二进制数的信息.
接下来并没有使用大家熟悉的while循环转换进制的方法,而是通过一个for循环和一些奇怪的运算得到了结果.单独拿出来分析:
for j in range(n):
if ((1<<j)&i):
v[j]=1
tot+=1
j的循环范围是0到n-1,刚好是这个二进制数的长度.1 << j 是左移位运算,表示把1这个数字的二进制向左移动j位.因为1的二进制就是1,左移两位,得到100,对应4.左移三位,得到1000,对应8,刚好是等效于2**j的.类似的也有>>运算符,称为右移.这两个统称为位运算符.
这里之所以选择位运算的而不是次幂,是因为位运算相对于次幂计算有着很庞大的时间优势.(据不完全测试,这道题的位运算写法和次幂写法的运行时间最多差了35%左右,已经是一个不可忽视的常数优化了).所以大家如果在之后做题的时候使用枚举的话,推荐这种位运算的写法.
接下来是(1 << j ) \& i .我们已经知道了( 1 << j )是一个第j位为1,后面全为0的一个二进制数,把它和i进行与运算,如果结果大于0,那么显然i的二进制的第j位也为1.如果为0,说明二进制的第j位为0.
结论就是, ( 1 << j ) \& i 可以告诉我们i这个数的二进制的第j位是不是1.这个算式希望大家理解并掌握,最起码要记住这个写法.但是请不要自行对这个式子进行魔改,而且位运算这个手法只对2进制数有用,请不要在别的题目中滥用左移右移运算符!!!
如果我们发现了第j位是1,就在v数组对应的位置做个标记方便之后的输出,并且通过tot记录下一共找到了多少个1.之后只需要根据tot和r进行合法性判断就好了.如果发现恰好有r个1,那么就可以输出方案了.因为实际中数字一般从1开始,所以输出的是j+1.
通过对二进制数性质,以及位运算的巧妙利用,我们解决了组合数枚举这个问题,同时得到了一个泛用的代码模板:
up=(2**n)
for i in range(up):
v=[0 for i in range(n)]
tot=0
for j in range(n):
if ((1<<j)&i):
v[j]=1
#接下来根据枚举的结果进行需要的操作
当我们需要从一些元素中挑出一些时,可以使用上面的模板来枚举所有的合法方案,然后根据我们的需要进行进一步的选择和处理.
最后需要注意的是,枚举算法的时间复杂度是O(n2^{n}),一般当n \geq 20时就不再选择枚举了(会TLE).所以在使用时要注意数据范围.
本文地址: Python第五周周报
