用Python刷Codeforces水题
Two Substrings
题意：问是否存在不重叠的串AB和BA。
思路：注意ABABA、BABAB这两种情况都应该是YES。所以可以找第一个AB，最后一个BA，如果两者不重叠（即两者不是ABA和BAB这样）可以确保一定是YES，同样如果找第一个BA和最后一个AB可以不重叠一样也是YES。
在python中，str的方法s1.find(s2)可以从字符串s1查找s2第一次出现的位置，找不到则返回-1。rfind()是查找最后一次出现位置。
s=raw_input()
x1,y1=s.find("AB"),s.rfind("BA")
x2,y2=s.find("BA"),s.rfind("AB")
if(x1!=-1 and y1!=-1 and x1+1!=y1 and y1+1!=x1 ) or (x2!=-1 and y2!=-1 and x2+1!=y2 and y2+1!=x2):
print 'YES'
else:
print 'NO'
Preparing Olympiad
题意：给一些数字，问有多少子集满足它们的和值位于l和r之间，且最大值与最小值的差超过x。
思路：枚举子集判断即可。
在python中，list(itertools.combinations(a,i))表示在a中枚举长度为i的所有子集。
import itertools
n,l,r,x=
a=
ans=0
for i in range(1,n+1):
sub=list(itertools.combinations(a,i))
for j in sub:
s,d=sum(j),max(j)-min(j)
if l<=s and s<=r and d>=x:
ans+=1
print ans
Soldier and Bananas
思路:用求和公式直接算就行，注意不借钱是答案是0
用python只需要两行
k,w,n=
print max(0,k*(1+n)*n/2-w)
Soldier and Cards
思路：直接模拟就行。
在python中可变对象如list是不能直接哈希的，可以转换成tuple来哈希。
n=int(raw_input())
a=
b=
del a,b
def move(a,b):
a.append(b)
a.append(a)
del a,b
def solve():
vis=set()
step=0
while True:
if len(a)==0:
return str(step)+" "+str(2)
elif len(b)==0:
return str(step)+" "+str(1)
p=(tuple(a),tuple(b))
if p in vis:
return -1
vis.add(p)
if a>b:
move(a,b)
else:
move(b,a)
step+=1
print solve()
Ilya and Diplomas
题意是从三个给定范围内找出三个数和等于n。要求输出的三个数依次尽可能最大。
n=int(input())
mi1,mx1=
mi2,mx2=
mi3,mx3=
a,b,c=n-mi2-mi3,mi2,mi3
if a>mx1:
b+=a-mx1
a=mx1
if b>mx2:
c+=b-mx2
b=mx2
print ("%s %s %s"%(a,b,c))
页:
[1]