python小练习

接下来打算在这几个oj上用python刷刷水题,巩固一下刚学的python语法。刚开始想用zoj刷,但是zoj水题太少了,刚学python感到力不从心。。
leetcode
codeforces
leetcode165

class Solution:
    # @param version1, a string
    # @param version2, a string
    # @return an integer
    def compareVersion(self, version1, version2):
        a=version1.split(".");b=version2.split(".");
        lena=len(a);lenb=len(b);
        for i in range(lena):a[i]=int(a[i]);
        for i in range(lenb):b[i]=int(b[i]);
        if(lena<lenb):
            for i in range(lenb-lena):a+=[0];
        elif(lena>lenb):
            for i in range(lena-lenb):b+=[0];
        if(a>b):return 1;
        elif(a<b):return -1;
        else:return 0;
        

cf#1a

str=raw_input();l=str.split(" ");
n=int(l[0]);m=int(l[1]);a=int(l[2]);
if(n%a==0): n/=a;
else:n=n/a+1;
if(m%a==0): m/=a;
else:m=m/a+1;
print(n*m);

cf#1b
这题在整形的列值转化为字母表示的列序号时不知道怎么办了。。于是看了下题解。’A'~’Z'要映射为1~26,当余数为0时,特殊处理,0代表’Z',而且商要减一。。目前还不太明白为什么这么做就对。。。弱爆~~

def judge(a):
    flag1=0;flag2=0;flag3=0;
    for i in a:
        if(i=='R'):flag1=1;
        if(i=='C'):flag2=1;
        if('0'<=i<='9' and flag1==1 and flag2==0): flag3=1;
    if(flag1==1 and flag2==1 and flag3==1):return 0;
    else:return 1;
n=int(input());
for i in range(n):
    s=input();
    ret=judge(s);
    if(ret==0):
        s=s.split("R");
        s=s[1].split("C");
        r=int(s[0]);c=int(s[1]);
        tmp=[];
        while(c!=0):
            cc=c%26;
            if(cc!=0):
                tmp+=[cc];c//=26;
            else:
                tmp+=[26];c=c//26-1;
        tmp.reverse();
        for i in tmp:
            print(chr(i+ord("A")-1),end="");
        print(r);
    else:
        r=c=0;
        for i in s:
            if('A'<=i<='Z'):c=c*26+ord(i)-ord("A")+1;
            else:r=r*10+ord(i)-ord("0");
        print("R%dC%d" % (r,c));

cf#2a

n=int(input());
name=[];rou=[];score=[];win=[];
for i in range(n):
    tmp=(input()).split(" ");
    tmp[1]=int(tmp[1]);
    rou.append(tmp);
    if(tmp[0] not in name):
        name.append(tmp[0]);
        score.append(tmp[1]);
        win.append(0);
    else:
        index=name.index(tmp[0]);
        score[index]+=tmp[1];
ans=max(score);
for i in range(len(score)):
    if(score[i]==ans):
        win[i]=1;
        score[i]=0;
for a in rou:
    index=name.index(a[0]);
    score[index]+=a[1];
    if(score[index]>=ans and win[index]==1):
        print(a[0]);
        break;

cf#3a

def judge(s,t):
    sx=s[0];sy=s[1];
    tx=t[0];ty=t[1];
    if(sx==tx and sy==ty):return "end";
    if(tx>sx and ty>sy):
        s[0]+=1;s[1]+=1;
        return "RU";
    if(tx>sx and ty<sy):
        s[0]+=1;s[1]-=1;
        return "RD";
    if(tx<sx and ty>sy):
        s[0]-=1;s[1]+=1;
        return "LU";
    if(tx<sx and ty<sy):
        s[0]-=1;s[1]-=1;
        return "LD";
    if(tx==sx and ty<sy):
        s[1]-=1;
        return "D";
    if(tx==sx and ty>sy):
        s[1]+=1;
        
        return "U";
    if(tx<sx and ty==sy):
        s[0]-=1;
        return "L";
    if(tx>sx and ty==sy):
        s[0]+=1;
        return "R";
s=input();t=input();
s=[s[0],s[1]];t=[t[0],t[1]];
s[0]=ord(s[0])-ord('a')+1;s[1]=int(s[1]);
t[0]=ord(t[0])-ord('a')+1;t[1]=int(t[1]);
cnt=0;ans=[];
move=judge(s,t);
while(move!="end"):
    ans.append(move);
    cnt+=1;
    move=judge(s,t);
print(cnt);
for i in ans:print(i);

cf#4a

w=int(input());
if(w%2==0 and w>2):print("YES");
else:print("NO");

cf#5a
现在一般能一次性编译通过了,开始对用python写代码有点感觉啦。

name=[];ans=0;
while(1):
    try:
        s=input();
        if(s[0]=='+'):name.append(s[1:]);
        elif(s[0]=='-'):name.remove(s[1:]);
        else:
            tmp=s.split(":");
            ans+=(len(tmp[1])*len(name));
    except:
        break;
print(ans);

cf#5b
要求将给定的文本居中显示,做这道题使我发现python这种脚本处理文本非常方便。

def change(i):
    global a;global flag;
    l=len(a[i]);
    tmp="";
    space=maxlen-l;
    for j in range(space//2):tmp+=' ';
    if(space%2==0):
        a[i]='*'+tmp+a[i]+tmp+'*';
    else:
        if(flag==0):a[i]='*'+tmp+a[i]+tmp+' *';
        else:       a[i]='*'+tmp+' '+a[i]+tmp+'*';
        flag^=1;
a=[];
maxlen=0;
while(1):
    try:
        tmp=input();
        le=len(tmp);
        if(le>maxlen):maxlen=le;
        a.append(tmp);
    except:
        break;
cnt=len(a);
flag=0;
for i in range(cnt):
    change(i);
tmp="";
for i in range(maxlen+2):tmp+='*';
a.insert(0,tmp);a.append(tmp);
for i in a:print(i);

cf#6a

def judge(li):
    li.sort();
    if(li[0]+li[1]>li[2]):return 1;
    elif(li[0]+li[1]==li[2]):return 0;
    else:return -1;
a=input().split(" ");
for i in range(4):
    a[i]=int(a[i]);
flag1=flag2=0;
for i in range(4):
    for j in range(i+1,4):
        for k in range(j+1,4):
            ret=judge([a[i],a[j],a[k]]);
            if(ret==1):flag1=1;break;
            elif(ret==0):flag2=1;
if(flag1==1):print("TRIANGLE");
elif(flag2==1):print("SEGMENT");
else:print("IMPOSSIBLE");

cf#6b

def judge(x,y):
    if(0<=x<=n-1 and 0<=y<=m-1):return 1;
    else:return 0;

def cal(x,y):
    global room;global color;
    if(judge(x+1,y)):
        if('A'<=room[x+1][y]<='Z' and room[x+1][y]!=c):
            color.add(room[x+1][y]);
    if(judge(x-1,y)):
        if('A'<=room[x-1][y]<='Z' and room[x-1][y]!=c):
            color.add(room[x-1][y]);
    if(judge(x,y+1)):
        if('A'<=room[x][y+1]<='Z' and room[x][y+1]!=c):
            color.add(room[x][y+1]);
    if(judge(x,y-1)):
        if('A'<=room[x][y-1]<='Z' and room[x][y-1]!=c):
            color.add(room[x][y-1]);

        
a=input().split(" ");
n=int(a[0]);m=int(a[1]);c=a[2];
color=set();
room=[];
for i in range(n):
    room.append(list(input()));
for i in range(n):
    for j in range(m):
        if(room[i][j]==c):
            cal(i,j);
print(len(color));

cf#7a

def judge(i,flag):
    global a;
    paint=1;
    if(flag==0):
        for j in range(8):
            if(a[i][j]=='W'):
                paint=0;
                break;
    else:
        for j in range(8):
            if(a[j][i]=='W'):
                paint=0;
                break;
    return paint;
a=[];
ans=0;
for i in range(8):
    r=list(input());
    a.append(r);
for i in range(8):ans+=judge(i,0);
for i in range(8):ans+=judge(i,1);
if(ans==16):print(8);
else:       print(ans);

cf#7b

def alloc(s):
    global m;global size;
    cnt=0;
    for i in range(1,size+2):
        if(m[i]==0):
            cnt+=1;
            if(cnt==s):
                for j in range(i-cnt+1,i+1):m[j]=1;
                return [i-cnt+1,i];
        else:cnt=0;
    return [-1];

def erase(begin,end):
    global m;
    for i in range(begin,end+1):m[i]=0;
    return;

a=input().split(" ");
t=int(a[0]);size=int(a[1]);
m=[0];
b=0;
block=[0];
for i in range(1,size+1):m.append(0);
m.append(1);
while(t!=0):
    com=input().split(" ");
    if(com[0]=="alloc"):
        ret=alloc(int(com[1]));
        if(ret[0]!=-1):
            b+=1;
            ret.append(1);
            block.append(ret);
            print(b);
        else:print("NULL");
    elif(com[0]=="erase"):
        x=int(com[1]);
        if(x<=0 or x>b or block[x][2]==0):print("ILLEGAL_ERASE_ARGUMENT");
        else:
            block[x][2]=0;
            erase(block[x][0],block[x][1]);
    else:
        if(len(block)==0):continue;
        use=0;
        for i in range(1,len(block)):
            if(block[i][2]==0):continue;
            use+=block[i][1]-block[i][0]+1;
            blank=0;
            for j in range(1,block[i][0]):
                if(m[j]==0): blank+=1;
            block[i][0]-=blank;block[i][1]-=blank;
        for i in range(1,use+1):m[i]=1;
        for i in range(use+1,size+1):m[i]=0;
    t-=1;

cf#8a
python处理字符串真的很方便,做这题的时候开始用s.reverse(),结果发现字符串对象没有这个方法。。然后get了一个新技能。
也就是字符串的反向切片:s[begin:end:-step](begin>end)
begin大于end表示此时想反向切片,此时步进要设为负值。
正向切片时不用显式的写出步进字段。
反向切片时则一定写写出步进字段,特别的,如果是对整个字符串进行切片,则begin和end都可以省略。
注意一点:end是不包括在切片内的,即半开半闭区间[begin,end)

s=input();
s1=input();
s2=input();
flag1=flag2=0;
pos1=s.find(s1);
if(pos1>=0):
    pos2=s[pos1+len(s1):].find(s2);
    if(pos2>=0):flag1=1;
s=s[::-1];
pos1=s.find(s1);
if(pos1>=0):
    pos2=s[pos1+len(s1):].find(s2);
    if(pos2>=0):flag2=1;
if(flag1==1 and flag2==1):print("both");
elif(flag1==1):print("forward");
elif(flag2==1):print("backward");
else:print("fantasy");

cf#8b
这道水题让我收获挺多。
首先是让我知道了python中dict的关键字和set的元素不能是list但可以是tuple。
其次,由于python的for语句的特性(貌似上界无法动态改变),所以只好用while或者递归来实现bfs(当然也可以直接用collections里面的deque,但是效率不知怎么样,所以还是用数list模拟)
再者,这道题开始考虑欠佳,以为排除几种特殊情况即可,实际上“特殊情况”很多。。所以把给出路径上的方格设为empty,其余设为obstruct,这样就形成了“最好情况”,然后bfs算最短路径,如果这种情况下都不是最短路径,就一定不存在一种情况它是最短路径

def judge(x,y):
    global m;
    if(m[x][y]==0):return 1;
    return 0;

def bfs():
    global dest;
    q=[];
    q.append([100,100,0]);
    iq=1;
    i=0;
    vis=set();vis.add((100,100));
    while(i<=iq-1):
        x=q[i][0];y=q[i][1];dep=q[i][2];
        if(x==dest[0] and y==dest[1]):return dep;
        else:
            if(judge(x+1,y)==1 and ((x+1,y) not in vis)):
                q.append([x+1,y,dep+1]);iq+=1;vis.add((x+1,y));
            if(judge(x-1,y)==1 and ((x-1,y) not in vis)):
                q.append([x-1,y,dep+1]);iq+=1;vis.add((x-1,y));
            if(judge(x,y+1)==1 and ((x,y+1) not in vis)):
                q.append([x,y+1,dep+1]);iq+=1;vis.add((x,y+1));
            if(judge(x,y-1)==1 and ((x,y-1) not in vis)):
                q.append([x,y-1,dep+1]);iq+=1;vis.add((x,y-1));
        i+=1;

move=input();
m=[];
dest=[100,100];
for i in range(210):
    m.append([]);
    for j in range(210):m[i].append(1);
m[100][100]=0;
for i in move:
    if(i=="U"):dest[1]+=1;
    if(i=="D"):dest[1]-=1;
    if(i=="L"):dest[0]-=1;
    if(i=="R"):dest[0]+=1;
    m[dest[0]][dest[1]]=0;
if(bfs()==len(move)):print("OK");
else:print("BUG");

cf#9a

def gcd(a,b):
    if(a<b):a^=b;b^=a;a^=b;
    if(b==0):return a;
    return  gcd(b,a%b);
a=input().split(" ");
x=int(a[0]);y=int(a[1]);
tmp=max(x,y);
if(tmp==1):print("1/1");
else:
    zi=6-tmp+1;
    g=gcd(zi,6);
    print("%d/%d" % (zi//g,6//g));

cf#9b
这道题不错,学到了python的数学运算,特别是开方,原先不知道怎么开方,查了下可以用math.sqrt(),但是直接**0.5更方便。
第二个是list的sort方法,可以通过参数key实现多关键字排序,非常方便。

inp=input().split();
n=int(inp[0]);vb=int(inp[1]);vs=int(inp[2]);
x=input().split();
for i in range(n):x[i]=int(x[i]);
dest=input().split();
dest[0]=int(dest[0]);dest[1]=int(dest[1]);
ans=[];
for i in range(1,n):
    tmp=(((dest[0]-x[i])**2)+(dest[1]**2))**0.5;
    ans.append((x[i]/vb+tmp/vs,tmp,i+1));
ans.sort(key=lambda x:(x[0],x[1]));
print(ans[0][2]);