2024年春季学期《算法分析与设计》练习13

问题 A: 菱形图案

[命题人 : admin]

时间限制 : 1.000 sec 内存限制 : 128 MB

提交问题列表

解决: 1041提交量: 2744统计

题目描述

KiKi学习了循环，BoBo老师给他出了一系列打印图案的练习，该任务是打印用“*”组成的菱形图案。

输入

多组输入，一个整数（2~20）。

输出

针对每行输入，输出用“*”组成的菱形，每个“*”后面有一个空格。每输出一个菱形的后面需要空一行。

样例输入 Copy

2
3
4

样例输出 Copy

  * 
 * * 
* * * 
 * * 
  * 

   * 
  * * 
 * * * 
* * * * 
 * * * 
  * * 
   * 

    * 
   * * 
  * * * 
 * * * * 
* * * * * 
 * * * * 
  * * * 
   * * 
    *

def solve(n):
    t = n
    for i in range(n + 1):
        print(t * ' ' + '* ' * (i + 1))
        t -= 1
    t = n
    for j in range(1, n + 1):
        print(j * ' ' + t * '* ')
        t -= 1
while True:
    solve(int(input()))
    print()

问题 B: X星人的礼物

[命题人 : admin]

时间限制 : 1.000 sec 内存限制 : 128 MB

提交问题列表

解决: 335提交量: 1241统计

题目描述

六一儿童节到了，X星人宝宝收到了很多很多礼物。他决定把这些礼物装到自己的礼物箱中。为此，他准备了很多个型号相同的礼物箱，每个礼物箱能够装礼物的最大重量都是一样的。但是X星人宝宝不希望在一个礼物箱里面装太多礼物（可能担心礼物会被压坏吧），每个礼物箱最多只允许装2个礼物。
假设X星人宝宝收到了N个礼物，现在给出每一个礼物的重量和一个礼物箱的最大装载量，请你编写一个程序计算X星人宝宝最少要用多少个礼物箱才能够把所有的礼物都装完。

输入

单组输入。
每组两行，第1行输入两个正整数，分别表示礼物的数量N和每个礼物箱的最大装载量C，其中1<=N<=1000，1<=C<=100，两者之间用英文空格隔开。
第2行输入N个不超过100的正整数，分别表示每一个礼物的重量，两两之间用英文空格隔开。
输入保证最重的礼物的重量<=C。

输出

针对所输出的数据，输出将所有的礼物全部都装完所需的礼物箱的最少个数。

样例输入 Copy

5 80
20 70 40 30 10

样例输出 Copy

while True:
    n, c = map(int, input().split())
    arr = list(map(int, input().split()))
    arr.sort()
    ans = 0
    i = 0
    j = n - 1
    while i < j:
        if arr[i] + arr[j] <= c:
            i += 1
            j -= 1
        else:
            j -= 1
        ans += 1
    if i == j:
        print(ans+1)
    else:
        print(ans)

问题 C: 隔离14天

[命题人 : 201501010119]

时间限制 : 1.000 sec 内存限制 : 128 MB

提交问题列表

解决: 1388提交量: 2431统计

题目描述

现在假定编号为0的乘客冠状病毒核酸检验呈阳性，请编写一个程序统计需隔离的总人数（包括编号为0的乘客）。

输入

第1行的第1个数字n表示总人数，第2个数字m表示汽车数量；从第2行开始，接下来的m行表示每辆汽车的司乘人员总人数和人员编号（人员编号是一个固定值，可以对应于我们的身份证号码），每一行的第1个数字k表示该汽车的司乘人员总数，接下来的k个数字表示每一个人的编号。

输出

需要被隔离的总人数。

样例输入 Copy

<span style="background-color:#ffffff"><span style="color:#333333"><span style="background-color:#ffffff"><span style="color:#333333"><span style="background-color:#f5f5f5">100 4
2 1 2
5 10 13 11 12 14
2 0 1
2 99 2
</span></span></span></span></span>

样例输出 Copy

<span style="background-color:#ffffff"><span style="color:#333333"><span style="background-color:#ffffff"><span style="color:#333333"><span style="background-color:#f5f5f5">4</span></span></span></span></span>

n, m = map(int, input().split())
a = []
for i in range(m):
    a.append(list(map(int, input().split()))[1:])
p = []
q = []
for i in range(m):
    if 0 in a[i]:
        p.append(i)
        q.extend(a[i])
t = 0
i = 0
while True:
    flag = False
    for i in range(m):
        if i not in p and set(q).intersection(a[i]):
            p.append(i)
            q.extend(a[i])
            flag = True
    if not flag:
        break
    t += 1
print(len(set(q)))

问题 D: 最小生成树（Kruskal）

[命题人 : 201501010119]

时间限制 : 1.000 sec 内存限制 : 128 MB

提交问题列表

解决: 1000提交量: 1940统计

题目描述

编程实现Kruskal算法，求图的最小生成树(MST)的权重。

输入

每组数据分为两个部分，第一部分为图的点数n，和边数m,
第二部分为m行，每一行输入三个数字，前两个为两个顶点的编号，第三个为边权重。

输出

最小生成树的权重。

样例输入 Copy

样例输出 Copy

while True:
    INF = 1 << 31 - 1
  
  
    def make_set(x):
        par[x] = x
        rank[x] = 0
  
  
    def find_set(x):
        if x != par[x]:
            par[x] = find_set(par[x])
        return par[x]
  
  
    def union_set(x, y, w):
        global sum
        x = find_set(x)
        y = find_set(y)
        if x == y:
            return 0
        if rank[x] > rank[y]:
            par[y] = x
        else:
            if rank[x] == rank[y]:
                rank[y] += 1
            par[x] = y
        sum += w
        return 1
  
  
    n, m = map(int, input().split())
    graph = []
    rank = [0] * m
    par = [0] * m
    for i in range(n):
        x, y, w = map(int, input().split())
        graph.append([x, y, w])
        make_set(i)
    graph.sort(key=lambda x: x[2])
    sum = 0
    for i in range(m):
        res = union_set(graph[i][0], graph[i][1], graph[i][2])
        # if res == 1:
        #     print(*graph[i])
    print(sum)

问题 E: 搭建电路

[命题人 : admin]

时间限制 : 1.000 sec 内存限制 : 128 MB

提交问题列表

解决: 781提交量: 3060统计

题目描述

明明迷上了一个搭建电路的游戏。
在游戏中，每次在两个电子元件之间增加一条有效电路（两个元件之间先前没有电路相连）都将获得相应的积分奖励。
已知电子元件数量n和部分电子元件之间的奖励积分值。如何构建一个有效电路将所有元件全部连接起来，并且可以得到最多的积分奖励。

输入

每组输入数据包含m+1行。
第1行输入两个正整数n和m，其中n表示电子元件数量（n<=100），m表示提供了m对电子元件之间的奖励积分值（m<=1000）。两个正整数之间用空格隔开。
第2行到第m+1行对应m对电子元件及其对应的奖励积分值，每一行包含三个正整数，第1个和第2个整数表示电子元件编号（从1开始），第3个整数表示两个元件之间搭建电路的奖励积分num(num<1e9)。整数之间用空格隔开。

输出

每组输出占1行，输出一个正整数，即最多可以得到的积分奖励值。如果没有办法把所有元件全部连接起来，则输出“No solution.”。

样例输入 Copy

样例输出 Copy

def judge(a, b, c, vis):
    if (a not in vis or b not in vis) and (a in vis or b in vis):
        return 1
    return 0
 
while True:
    n, m = map(int, input().split())
    arr = [list(map(int, input().split())) for _ in range(m)]
    arr.sort(reverse=True, key=lambda x: x[2])
    vis = []
    res = 0
    cnt = 1
    a, b, c = arr.pop(0)
    vis.extend([a, b])
    res += c
    flag = 1
    while cnt < n - 1 and flag:
        flag = 0
        for i in range(len(arr)):
            a, b, c = arr[i]
            if judge(a, b, c, vis):
                vis.append(a) if a not in vis else vis.append(b)
                res += c
                arr.pop(i)
                cnt += 1
                flag = 1
                break
    if flag:
        print(res)
    else:
        print("No solution.")

问题 F: 最小生成树（Prim）

[命题人 : 201501010119]

时间限制 : 1.000 sec 内存限制 : 128 MB

提交问题列表

解决: 1019提交量: 5024统计

题目描述

使用Prim算法求图的最小生成树(MST)

输入

每组数据分为两个部分，第一部分为图的点数n，和边数m,
第二部分为m行，每一行输入三个数字，前两个为两个顶点的编号，第三个为边权重。

输出

最小生成树，输出时按照边的两个端点的升序输出。（先看左端点，再看右端点，端点不换位置）

样例输入 Copy

样例输出 Copy

0 1 10
0 2 15

def judge(a, b, c, vis):
    if (a not in vis or b not in vis) and (a in vis or b in vis):
        return 1
    return 0
 
 
while True:
    n, m = map(int, input().split())
    arr = []
    for i in range(m):
        arr.append(list(map(int, input().split())))
    arr.sort(key=lambda x: x[2])
    cnt = 1
    vis = []
    res = []
    a, b, c = arr.pop(0)
    vis.extend([a, b])
    res.append([a, b, c])
 
    while cnt < n - 1:
        for i, (a, b, c) in enumerate(arr):
            if judge(a, b, c, vis):
                vis.append(a) if a not in vis else vis.append(b)
                res.append([a, b, c])
                arr.pop(i)
                cnt += 1
                break
 
    res.sort()
    for i in range(len(res)):
        print(*res[i])

问题 G: 台球碰撞

[命题人 : 外部导入]

时间限制 : 1.000 sec 内存限制 : 128 MB

提交问题列表

解决: 29提交量: 88统计

题目描述

在平面直角坐标系下，台球桌是一个左下角在(0,0)，右上角在(L,W)的矩形。有一个球心在(x,y)，半径为R的圆形母球放在台球桌上（整个球都在台球桌内）。受撞击后，球沿极角为a的射线（即：x正半轴逆时针旋转到此射线的角度为a）飞出，每次碰到球桌时均发生完全弹性碰撞（球的速率不变，反射角等于入射角）。

如果球的速率为v，s个时间单位之后球心在什么地方？

输入

输入文件最多包含25组测试数据，每个数据仅一行，包含8个正整数L,W,x,y,R,a,v,s（100<=L,W<=105,1<=R<=5, R<=x<=L-R, R<=y<=W-R, 0<=a<360, 1<=v,s<=105），含义见题目描述。L=W=x=y=R=a=v=s=0表示输入结束，你的程序不应当处理这一行。

输出

对于每组数据，输出仅一行，包含两个实数x, y，表明球心坐标为(x,y)。x和y应四舍五入保留两位小数。

样例输入 Copy

<span style="background-color:#ffffff"><span style="color:#333333"><span style="background-color:#ffffff"><span style="color:#333333"><span style="background-color:#f5f5f5">100 100 80 10 5 90 2 23
110 100 70 10 5 180 1 9999
0 0 0 0 0 0 0 0</span></span></span></span></span>

样例输出 Copy

<span style="background-color:#ffffff"><span style="color:#333333"><span style="background-color:#ffffff"><span style="color:#333333"><span style="background-color:#f5f5f5">80.00 56.00
71.00 10.00</span></span></span></span></span>

import math
 
while True:
    L, W, x, y, R, a, v, s = map(int, input().split())
    if L == W == x == y == R == a == v == s == 0:
        break
    dis = v * s
    re_x = x + dis * math.cos(math.radians(a))
    re_y = y + dis * math.sin(math.radians(a))
    while re_x - R < 0 or re_x + R > L:
        if re_x - R < 0:
            a = 180 - a
            re_x = R + (R - re_x)
        elif re_x + R > L:
            a = 180 - a
            re_x = L - R - (re_x + R - L)
    while re_y - R < 0 or re_y + R > W:
        if re_y - R < 0:
            a = -a
            re_y = R + (R - re_y)
        elif re_y + R > W:
            a = -a
            re_y = W - R - (re_y + R - W)
    print("%.2f" % re_x, "%.2f" % re_y)