目录

一、带分数

题干

解答

二、李白打酒

题干

解答

三、第39级台阶

题干

解答

四、穿越雷区

题干

解答

*五、迷宫

题干

解答

六、跳马

题干

解答

*七、路径之谜

题干

解答

八、未名湖边的烦恼

题干

解答

*九、大臣的旅费

题干

解答

*十、2n皇后问题

题干

解答

一、带分数

题干

100 可以表示为带分数的形式：100 = 3 + 69258 / 714。 还可以表示为：100 = 82 + 3546 / 197。 注意特征：带分数中，数字 1~9 分别出现且只出现一次（不包含 0）。 类似这样的带分数，100 有 11 种表示法。从标准输入读入一个正整数 N (N<1000*1000），程序输出该数字用数码 1~9 不重复不遗漏地组成带分数表示的全部种数。 注意：不要求输出每个表示，只统计有多少表示法！

解答

def count(n):
    sum=0
    for i in range(1,n):
        rest=n-i       #97=100-3
        for k in range(1,1000):    #倍数（同一个数不止一种情况）
            t=rest*k
            if judge(i,t,k):     
                sum = sum+1
    return sum

def judge(a,b,c):
    flag=True
    n = [False for _ in range(10)]
    n[0]=True

    while (a>0):   #懒得收纳了，凑合着看吧
        temp=a%10
        if n[temp] == False:
            n[temp] = True
        elif n[temp] == True:
            flag=False
            break
        a=a//10

    while (b>0):
        temp=b%10
        if n[temp] == False:
            n[temp] = True
        elif n[temp] == True:
            flag=False
            break
        b=b//10

    while (c>0):
        temp=c%10
        if n[temp] == False:
            n[temp] = True
        elif n[temp] == True:
            flag=False
            break
        c=c//10

    if False in n:
        flag=False

    return flag

x=int(input())
print(count(x))

二、李白打酒

题干

话说大诗人李白，一生好饮。幸好他从不开车。 一天，他提着酒壶，从家里出来，酒壶中有酒 2 斗。他边走边唱： 无事街上走，提壶去打酒。 逢店加一倍，遇花喝一斗。 这一路上，他一共遇到店 5 次，遇到花 10 次，已知最后一次遇到的是花，他正 好把酒喝光了。 请你计算李白遇到店和花的次序，可以把遇店记为 a，遇花记为 b。则： babaabbabbabbbb 就是合理的次序。像这样的答案一共有多少呢？请你计算出 所有可能方案的个数（包含题目给出的）

解答

def count(a,b,wine):           
    global sum
    if a>0:
        count(a-1,b,wine*2)   
    if b>0:
        count(a,b-1,wine-1)
    if a==0 and b==0 and wine==1:
        sum=sum+1
    return sum
sum=0
print(count(5,9,2) )   #14

三、第39级台阶

题干

小明刚刚看完电影《第 39 级台阶》，离开电影院的时候，他数了数礼堂前的 台阶数，恰好是 39 级! 站在台阶前，他突然又想着一个问题： 如果我每一步只能迈上 1 个或 2 个台阶。先迈左脚，然后左右交替，最后一步是迈右脚，也就是说一共要走偶数步。那么，上完 39 级台阶，有多少种不同的上法呢？

解答

def f(n,step):
    sum=0
    if n>0 and step==0:
        return f(n-1,1)+f(n-2,1)
    if n>0 and step==1:
        return f(n-1,0)+f(n-2,0)
    if n==0 and step==1:     #最后一步为右脚
        sum=sum+1
    return sum

print(f(39,0))   #第一步迈左脚,输出51167077

四、穿越雷区

题干

X星的坦克战车很奇怪，它必须交替地穿越正能量辐射区和负能量辐射区才能保持正常运转，否则将报废。
某坦克需要从A区到B区去（A，B区本身是安全区，没有正能量或负能量特征），怎样走才能路径最短？

已知的地图是一个方阵，上面用字母标出了A，B区，其它区都标了正号或负号分别表示正负能量辐射区。
例如：
A + - + -
- + - - +
- + + + -
+ - + - +
B + - + -

坦克车只能水平或垂直方向上移动到相邻的区。

数据格式要求：

输入第一行是一个整数n，表示方阵的大小， 4<=n<100
接下来是n行，每行有n个数据，可能是A，B，+，-中的某一个，中间用空格分开。
A，B都只出现一次。

要求输出一个整数，表示坦克从A区到B区的最少移动步数。
如果没有方案，则输出-1

例如：
用户输入：
5
A + - + -
- + - - +
- + + + -
+ - + - +
B + - + -

则程序应该输出：
10

解答

import copy

def f(x,y,step):
    global min
    if mat[x][y]=="B" and min>step:    #x=4,y=0
        min=step

    vis[x][y] = 1
    if y>0 and mat[x][y]!=mat[x][y-1] and vis[x][y-1]!=1:   #左移
        f(x,y-1,step+1)
    if y<n-1 and mat[x][y]!=mat[x][y+1] and vis[x][y+1]!=1:   #右移
        f(x,y+1,step+1)
    if x>0 and mat[x][y]!=mat[x-1][y] and vis[x-1][y]!=1:   #上移
        f(x-1,y,step+1)
    if x<n-1 and mat[x][y]!=mat[x+1][y] and vis[x+1][y]!=1:   #下移
        f(x+1,y,step+1)
    vis[x][y] = 0
    return min

mat=[]
min=10000
n=int(input())

for i in range(n):
    temp=input().split(" ")
    mat.append(temp)
    if "A" in temp:       #从哪里开始
        x1=i
        y1=temp.index('A')
vis=copy.deepcopy(mat)   #懒得新生成一个二维数组了，之前那个拿来凑合着用吧
 
if f(x1,y1,0)==10000:
    print("-1")
else:
    print(f(x1,y1,0))

*五、迷宫

题干

下图给出了一个迷宫的平面图，其中标记为 1 的为障碍，标记为 0 的为可 以通行的地方。

010000

000100

001001

110000

迷宫的入口为左上角，出口为右下角，在迷宫中，只能从一个位置走到这 个它的上、下、左、右四个方向之一。

对于上面的迷宫，从入口开始，可以按DRRURRDDDR 的顺序通过迷宫，一共 10 步。其中 D、U、L、R 分别表示向下、向上、向左、向右走。

对于下面这个更复杂的迷宫（30 行 50 列），请找出一种通过迷宫的方式， 其使用的步数最少，在步数最少的前提下，请找出字典序最小的一个作为答案。 请注意在字典序中D<L<R<U。（如果你把以下文字复制到文本文件中，请务必检查复制的内容是否与文档中的一致。在试题目录下有一个文件 maze.txt，内容与下面的文本相同）

01010101001011001001010110010110100100001000101010

00001000100000101010010000100000001001100110100101

01111011010010001000001101001011100011000000010000

01000000001010100011010000101000001010101011001011

00011111000000101000010010100010100000101100000000

11001000110101000010101100011010011010101011110111

00011011010101001001001010000001000101001110000000

10100000101000100110101010111110011000010000111010

00111000001010100001100010000001000101001100001001

11000110100001110010001001010101010101010001101000

00010000100100000101001010101110100010101010000101

11100100101001001000010000010101010100100100010100

00000010000000101011001111010001100000101010100011

10101010011100001000011000010110011110110100001000

10101010100001101010100101000010100000111011101001

10000000101100010000101100101101001011100000000100

10101001000000010100100001000100000100011110101001

00101001010101101001010100011010101101110000110101

11001010000100001100000010100101000001000111000010

00001000110000110101101000000100101001001000011101

10100101000101000000001110110010110101101010100001

00101000010000110101010000100010001001000100010101

10100001000110010001000010101001010101011111010010

00000100101000000110010100101001000001000000000010

11010000001001110111001001000011101001011011101000

00000110100010001000100000001000011101000000110011

10101000101000100010001111100010101001010000001000

10000010100101001010110000000100101010001011101000

00111100001000010000000110111000000001000000001011

10000001100111010111010001000110111010101101111000

解答

fine...我一直以为我写的是广搜...难怪搜不出来

import copy
def way(x,y,forward):
    global min
    if x==29 and y==49 and min>=len(forward):
        dic[forward]=len(forward)
        min=len(forward)
        print(dic)

    vis[x][y]=3
    if x>0 and map[x-1][y]=='0' and vis[x-1][y]!=3:   #上
        way(x-1, y, forward+"U")
    if x<29 and map[x+1][y]=='0' and vis[x+1][y]!=3:   #下
        way(x+1, y, forward+"D")
    if y>0 and map[x][y-1]=='0' and vis[x][y-1]!=3:   #左
        way(x, y-1, forward+"L")
    if y<49 and map[x][y+1]=='0' and vis[x][y+1]!=3:   #右
        way(x, y+1, forward+"R")
    vis[x][y]=4

    return dic

map=[]
dic={}
min=10000
for i in range(30):
    temp=input()
    map.append([])
    for j in range(50):
        map[i].append(temp[j])
vis=copy.deepcopy(map)

print(way(0,0,""))

六、跳马

题干

中国象棋半张棋盘如图 1 所示。马自左下角(0,0)向右上角（m,n）跳。规定只能 往右跳，不准往左跳。比如图 1 中所示为一种跳行路线，并将路径总数打印出来。

输入格式：只有一行，两个数m,n

输出格式： 只有一个数：总方案数

解答

def jump(x,y):
    global sum

    if x==n and y==m:
        sum=sum+1
    print(x,y)

    if x>1 and y<m:   #右上
        jump(x-2,y+1)
    if x>0 and y<m-1:   #右中上
        jump(x-1,y+2)
    if x<n and y<m-1:
        jump(x+1,y+2)
    if x<n-1 and y<m:
        jump(x+2,y+1)

    return sum

sum=0
n,m = map(int, input().split())   #棋盘的高和宽
print(jump(0,0))

*七、路径之谜

题干

小明冒充X星球的骑士，进入了一个奇怪的城堡。

城堡里边什么都没有，只有方形石头铺成的地面。

假设城堡地面是 n x n 个方格。【如图1.png】所示。

按习俗，骑士要从西北角走到东南角。
可以横向或纵向移动，但不能斜着走，也不能跳跃。
每走到一个新方格，就要向正北方和正西方各射一箭。
（城堡的西墙和北墙内各有 n 个靶子）

同一个方格只允许经过一次。但不必走完所有的方格。

如果只给出靶子上箭的数目，你能推断出骑士的行走路线吗？

有时是可以的，比如图1.png中的例子。

 本题的要求就是已知箭靶数字，求骑士的行走路径（测试数据保证路径唯一）

输入
第一行一个整数N(0<N<20)，表示地面有 N x N 个方格
第二行N个整数，空格分开，表示北边的箭靶上的数字（自西向东）
第三行N个整数，空格分开，表示西边的箭靶上的数字（自北向南）

输出
一行若干个整数，表示骑士路径。

为了方便表示，我们约定每个小格子用一个数字代表，从西北角开始编号: 0,1,2,3…
比如，图1.png中的方块编号为：

0 1 2 3
4 5 6 7
8 9 10 11
12 13 14 15

样例输入
4
2 4 3 4
4 3 3 3
样例输出
0 4 5 1 2 3 7 11 10 9 13 14 15

解答

这两天事有点多...容我对着答案再琢磨琢磨

八、未名湖边的烦恼

题干

每年冬天，北大未名湖上都是滑冰的好地方。北大体育组准备了许多冰鞋， 可是人太多了，每天下午收工后，常常一双冰鞋都不剩。 每天早上，租鞋窗口都会排起长龙，假设有还鞋的 瀀 个，有需要租鞋的 瀁 个。现在的问题是，这些人有多少种排法，可以避免出现体育组没有冰鞋可租的 尴尬场面。（两个同样需求的人（比如都是租鞋或都是还鞋）交换位置是同一种 排法）

解答

def shoes(z,h,num):
    sum=0
    if z==0 and h==0 and num>=0: 
        sum=sum+1

    if num>0 and z>0 and h>0:
        return shoes(z-1,h,num-1)+shoes(z,h-1,num+1)
    elif num>0 and z>0 and h==0:
        return shoes(z-1,h,num-1)
    elif num>=0 and z==0 and h>0:
        return shoes(z,h-1,num+1)
    elif num==0 and h>0:
        return shoes(z, h - 1, num + 1)
    return sum

z,h = map(int, input().split())
print(shoes(z,h-1,1))

*九、大臣的旅费

题干

很久以前，T王国空前繁荣。为了更好地管理国家，王国修建了大量的快速路，用于连接首都和王国内的各大城市。

为节省经费，T国的大臣们经过思考，制定了一套优秀的修建方案，使得任何一个大城市都能从首都直接或者通过其他大城市间接到达。同时，如果不重复经过大城市，从首都到达每个大城市的方案都是唯一的。

J是T国重要大臣，他巡查于各大城市之间，体察民情。所以，从一个城市马不停蹄地到另一个城市成了J最常做的事情。他有一个钱袋，用于存放往来城市间的路费。

聪明的J发现，如果不在某个城市停下来修整，在连续行进过程中，他所花的路费与他已走过的距离有关，在走第x千米到第x+1千米这一千米中（x是整数），他花费的路费是x+10这么多。也就是说走1千米花费11，走2千米要花费23。

J大臣想知道：他从某一个城市出发，中间不休息，到达另一个城市，所有可能花费的路费中最多是多少呢？

输入格式

输入的第一行包含一个整数n，表示包括首都在内的T王国的城市数

城市从1开始依次编号，1号城市为首都。

接下来n-1行，描述T国的高速路（T国的高速路一定是n-1条）

每行三个整数Pi, Qi, Di，表示城市Pi和城市Qi之间有一条高速路，长度为Di千米。

输出格式

输出一个整数，表示大臣J最多花费的路费是多少。

样例输入1

5
1 2 2
1 3 1
2 4 5
2 5 4

样例输出1

135

输出格式

大臣J从城市4到城市5要花费135的路费。

解答

*十、2n皇后问题

题干

给定一个n*n的棋盘，棋盘中有一些位置不能放皇后。现在要向棋盘中放入n个黑皇后和n个白皇后，使任意的两个黑皇后都不在同一行、同一列或同一条对角线上，任意的两个白皇后都不在同一行、同一列或同一条对角线上。问总共有多少种放法？n小于等于8。
输入格式
输入的第一行为一个整数n，表示棋盘的大小。
接下来n行，每行n个0或1的整数，如果一个整数为1，表示对应的位置可以放皇后，如果一个整数为0，表示对应的位置不可以放皇后。
输出格式
输出一个整数，表示总共有多少种放法。
样例输入
4
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
样例输出
2
样例输入
4
1 0 1 1
1 1 1 1
1 1 1 1
1 1 1 1
样例输出
0

解答