【思特奇杯·云上蓝桥-算法集训营】第二周

带分数

def add_grades(n):
    i = 1
    time = 0
    while i < n-1:
        grades = n - i
        for x in range(1,1000):
            denominator = x
            numerator = x * (n - i)
            ls = []
            for j in str(i):
                ls.append(int(j))
            for j in str(denominator):
                ls.append(int(j))
            for j in str(numerator):
                ls.append(int(j))
            if 0 not in ls and ls.count(1) == ls.count(2) == ls.count(3) == ls.count(4) == ls.count(5)\
                 == ls.count(6) == ls.count(7) == ls.count(8) == ls.count(9) == 1:
                time += 1
                #print(i,denominator,numerator)
                
        i += 1
 
    return time

n = int(input())
print(add_grades(n))

李白打酒

num = 0
def drink(jiu,dian,hua):
    if dian > 0:
        drink(jiu*2,dian-1,hua)
    if hua > 0:
        drink(jiu-1,dian,hua-1)
    if jiu==1 and dian==0 and hua==1:
        global num
        num += 1
    return num

print(drink(2,5,10))

第39级台阶

ls = []
for x in range(1,40):
    for y in range(1,20):
        num = x + 2 * y
        if num == 39 and (x+y) % 2 == 0:
            #print(x,y,x+y)
            ls.append((y,x+y))

def factor(m):
    if m == 1:
        return 1
    elif m > 1:
        return m * factor(m - 1)

def C(x,y):
    return factor(y)//(factor(x) * factor(y-x))

time = 0
for i in ls:
    time += C(i[0],i[1])
print(time)

穿越雷区

迷宫

import collections
f=open("maze.txt","r")
s=f.readlines()
position={}
for y_wall in range(0,32):
    position[(0,y_wall)]='1'
    position[(51,y_wall)]='1'
for x_wall in range(0,52):
    position[(x_wall,0)]='1'
    position[(x_wall,31)]='1'
y=1
for y_position in s:
    for xy_index in range(len(y_position)-1):
        position[(xy_index+1,y)]=y_position[xy_index]
    y=y+1
m_deque=collections.deque()
start=(1,1)
end=(50,30)
checked_position=[]
m_deque.append(start)
while m_deque:
    to_check_position=m_deque.popleft()
    if to_check_position not in checked_position:
        if to_check_position==end:
            print("ok!")
            break
        else:
            checked_position.append(to_check_position)
            up_position=(to_check_position[0],to_check_position[1]-1)
            down_position=(to_check_position[0],to_check_position[1]+1)
            left_position=(to_check_position[0]-1,to_check_position[1])
            right_position=(to_check_position[0]+1,to_check_position[1])
            if position.get(up_position)=="0" and up_position not in checked_position:
                m_deque.append(up_position)
            if position.get(down_position)=="0" and down_position not in checked_position:
                m_deque.append(down_position)     
            if position.get(left_position)=="0" and left_position not in checked_position:
                m_deque.append(left_position)
            if position.get(right_position)=="0" and right_position not in checked_position:
                m_deque.append(right_position)
all_line=checked_position+[end]
every_end=(end)
line=[]
line_dulr=[]
while every_end!=start:
    up_xy=(every_end[0],every_end[1]-1)
    down_xy=(every_end[0],every_end[1]+1)
    left_xy=(every_end[0]-1,every_end[1])
    right_xy=(every_end[0]+1,every_end[1])
    if position.get(up_xy)=="0" and up_xy in all_line:
        index=all_line.index(up_xy)
        all_line=all_line[:index]
        line.append(up_xy)
        line_dulr.append("D")
        every_end = up_xy 
    elif position.get(down_xy)=="0" and down_xy in all_line:
        index=all_line.index(down_xy)
        all_line=all_line[:index]
        line.append(down_xy)
        every_end=down_xy
        line_dulr.append("U")
    elif position.get(left_xy)=="0" and left_xy in all_line:
        index=all_line.index(left_xy)
        all_line=all_line[:index]
        line.append(left_xy)
        every_end=left_xy
        line_dulr.append("R")
    elif position.get(right_xy)=="0" and right_xy in all_line:
        index=all_line.index(right_xy)
        all_line=all_line[:index]
        line.append(right_xy)
        every_end=right_xy
        line_dulr.append("L")    
line_s=""
for i in line_dulr:
    line_s=line_s+i
print(line_s[::-1])

 跳马

m,n = map(int,input().split(','))
total = 0
def jump(r,c,a,b):
    global total
    if r<0 or r>m or c<0 or c>n:
        return
    elif r+a== m and c+b== n:
        total += 1
    jump(r+a,c+b,1,2)
    jump(r+a,c+b,1,-2)
    jump(r+a,c+b,2,1)
    jump(r+a,c+b,2,-1)

jump(0,0,0,0)
print(total)

路径之谜

未名湖边的烦恼 

import itertools
m,n = map(int,input().split(','))
ls = [1]*m + [-1]*n
def check(li):
    stack = []
    for i in li:
        if i == 1:
            stack.append(i)
        else:
            if stack == []:
                return False
            else:
                stack.pop()
    if sum(stack) >= 0:
        return True
    else:
        return False

need = set()
time = 0
for i in itertools.permutations(ls):
    need.add(i)

for m in need:
    if check(m):
        time += 1
print(time)

大臣的旅费

cnt=0
node=0
def dfs(v,k):   #进行dfs搜索
    global cnt
    global node
    global vis
    if k>cnt:
        cnt=k
        node=v
    for i in range(len(E[v])):
        if vis[E[v][i][0]]==False: #没访问过的点都进行一次dfs
            vis[E[v][i][0]]=True #进行标记
            dfs(E[v][i][0],k+E[v][i][1])
            vis[E[v][i][0]]=False #回溯
n=int(input())
E=[[]for i in range(n+1)]
vis=[False for i in range(n+1)]
for i in range(n-1):
    x,y,z=map(int,input().split())
    E[x].append((y,z))
    E[y].append((x,z)) #将各个点进行连接,用列表数组的方式进行
vis[1]=True
dfs(1,0)  #找到距离1最远的点node
vis[1]=False
cnt=0
vis[node]=True
dfs(node,0)  #从node出发,找到最远的点,就是所要求的最远距离
res=0
for i in range(1,cnt+1):
    res+=i+10
print(res)

2n皇后问题

nums = eval(input())
n = 0
list_empty = []
while n < nums:
    hang = [int(i) for i in input().split()]
    list_empty.append(hang)
    n +=1
def conflict(queen_list,new_queen,black=None):
    num = len(queen_list)
    try:
        col = black[num]
    except:
        pass
    try:
        if len(black) != 0:
            if new_queen == col:
                return True
    except:
        pass
    if list_empty[num][new_queen] == 0:
        return True
    for index,queen in enumerate(queen_list):
        if abs(new_queen-queen) in (0,num-index):
            return True

    return False


def queen(num, queen_list=[]):
    for new_queen in range(num):
        if not conflict(queen_list, new_queen):
            if len(queen_list) == num -1:
                yield [new_queen]

            else:
                for result in queen(num,queen_list+[new_queen]):
                    yield [new_queen]+result

black_queen = list(queen(nums))
def queen_white(num,black,queen_list=[]):
    for new_queen in range(num):
        if not conflict(queen_list,new_queen,black):
            if len(queen_list) == num -1:
                yield [new_queen]

            else:
                for result in queen_white(num,black,queen_list+[new_queen]):
                    yield [new_queen]+result
end_num = []
sum = 0
for black in black_queen:
    white_queens = list(queen_white(nums,black))
    if len(white_queens)==0:
        continue
    end_num.append(len(white_queens))


for i in end_num:
    sum +=i

print(sum)

上一篇:画笔盒的智慧(享元模式)


下一篇:【新手上路】LeetCode刷题之“杨辉三角”