用Python刷Codeforces水题

heike1

　　
　　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=[int(i) for i in raw_input().split()]
a=[int(i) for i in raw_input().split()]
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=[int(i) for i in raw_input().split()]
print max(0,k*(1+n)*n/2-w)
　　
　　Soldier and Cards
　　思路：直接模拟就行。
　　在python中可变对象如list是不能直接哈希的，可以转换成tuple来哈希。



n=int(raw_input())
a=[int(i) for i in raw_input().split()]
b=[int(i) for i in raw_input().split()]
del a[0],b[0]
def move(a,b):
a.append(b[0])
a.append(a[0])
del a[0],b[0]
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[0]>b[0]:
move(a,b)
else:
move(b,a)
step+=1
print solve()
　　
　　Ilya and Diplomas
　　题意是从三个给定范围内找出三个数和等于n。要求输出的三个数依次尽可能最大。



n=int(input())
mi1,mx1=[int(i) for i in input().split()]
mi2,mx2=[int(i) for i in input().split()]
mi3,mx3=[int(i) for i in input().split()]
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))