天天快乐编程杯中学生信奥联赛(202002) 题解(Python版)

此博客原文地址：https://www.cnblogs.com/BobHuang/p/12312134.html

1.6172: Alice视察

本题目比较困难，我们将信息传递出去，而且是最短的其实只需要n-1条边，他其实就是一棵无向树。在数据结构中有一专有名词最小生成树，有两个算法，分别是kruskal（加边）及Prime(加点)。这个题目数据量比较小，不卡算法，你可以实现任一算法AC。题解所用的是Kruskal。

class UDFS:
 
    def __init__(self, n):
        self.n = n
        self.parents = [i for i in range(n)]
        self.ranks = [0 for i in range(n)]
 
    def Find(self, a):
        if a == self.parents[a]:
            return a
        
        self.parents[a] = self.Find(self.parents[a])
        return self.parents[a]
 
    def join(self, a, b):
        parent_a = self.Find(a)
        parent_b = self.Find(b)
        if(parent_a!=parent_b):
            self.parents[parent_a] = parent_b
            return 1
        return 0


n_nodes, n_edges = map(int, input().split())
edges = list()
for i in range(n_edges):
        a, b, w = map(int, input().split())
        edges.append((w, a , b))

dsu = UDFS(n_nodes+1) 
edges.sort()
tot = 1
mi = 0

for edge in edges:
  if(dsu.join(edge[1],edge[2])!=0):
      mi = mi + edge[0]
      tot = tot + 1
      if(tot==n_nodes):
        break
print (mi)

2.6178: Alice运快递

这是一个很经典的01背包问题，一个物品可以选一次，所以我们这时候的状态是从dp[i-1][j]过来的，当前物品是否可以放下，是不是更大。只能选一次第二重循环要倒着进行。
第二问是个很简单的贪心问题，我们可以选择体积最小的货物装上。

while True:
    try:
        m,n=map(int,input().split())
        w=[0]*n
        c=[0]*n
        for i in range(n):
            w[i],c[i]=map(int,input().split())
        dp=[0]*(m+5)
        for i in range (n):
            for j in range(m, w[i]-1,-1):
                dp[j]=max(dp[j],dp[j-w[i]]+c[i])
        w.sort()
        ans = 0
        sum = 0
        for i in range (n):
            if sum+w[i] <= m :
                 sum += w[i]
                 ans = ans+1
            else:
                 break
        print(dp[m],ans)
    except EOFError:
        break

3.6173: 相同行程查询

这个题目有些困难，我们需要知道这个人的车次，之后我们会找到人然后对应到这个车次。最终我们要查询的是车次，当然我们可以进行排序之后二分。不过这个题目有个更好用的东西，叫dict字典。<key,value>也叫键值对，前面可以把放键，可以理解为就是一个下标，后面放值。所以就是人和车次的dict以及车次和人数的dict。这个“None”不能强转为数字，自己可以写个函数处理下。

def xstr(s):
    if s is None:
        return 0
    return int(s)
n=int(input())
peo=dict()
for i in range(n):
    data=list(map(str,input().split()))
    peo.update(dict([(k,data[0]) for k in data[2:]]))
m=int(input())
trains=dict()
peos=list(map(str,input().split()))
for i in range(m):
    t=xstr((trains.get(peo.get(peos[i]))))+1
    trains.update({peo.get(peos[i]):t})
q=int(input())
for i in range(q):
    train=input()
    print(xstr((trains.get(train))))

4.6177: Alice玩汉诺

这个题目我们可以采用常规做法，就是我们递归的时候可以统计移动次数。当然也可以找到递推式，是这样的，数量级大的情况就必须使用递推式了
A->B=(上一次)A->C->B
B->C=(上一次)B->A->C
c->A=(上一次)C>B->A
我们可以设置变量去统计他们
我这里用了递归写法

ans = []
def cal(a,c):
    if(a=="A" and c=="B"):
        ans[0] = ans[0]+1
    if(a=="A" and c=="C"):
        ans[1] = ans[1]+1
    if(a=="B" and c=="A"):
        ans[2] = ans[2]+1
    if(a=="B" and c=="C"):
        ans[3] = ans[3]+1
    if(a=="C" and c=="A"):
        ans[4] = ans[4]+1
    if(a=="C" and c=="B"):
        ans[5] = ans[5]+1
def Hanoi(n,a,b,c):
    if n==0:
        return
    Hanoi(n-1, a, c, b)
    cal(a,c)
    Hanoi(n-1, b, a, c)

while True:
    try:
        n=int(input())
        ans=[0]*6 
        Hanoi(n, "A", "B", "C")
        print("A->B: ",ans[0])
        print("A->C: ",ans[1])
        print("B->A: ",ans[2])
        print("B->C: ",ans[3])
        print("C->A: ",ans[4])
        print("C->B: ",ans[5])
    except EOFError:
        break

5.6179: Alice排数字

其实我们可以给其中的8和2拿出来看看有多少个282，排列一定是282828282····
也就是28不断循环的，其中282的个数和2和8均有关，n个2就有n-1个282，m个8就有m个282，两者取小，当然不能是负数。
取值是ord函数

while True:
    try:
        s=input()
        a=[0]*10
        for c in s:
            t = ord(c)-ord('0')
            a[t] = a[t] + 1
        print(max(0,min(a[2]-1,a[8])))
        print('Happy Birthday!')
    except EOFError:
        break

6.6181: Alice与闪电

这个一个比较复杂的循环题，我们可以将其分两三输出，前m/2行，中间行，后m/2行，前m/2行前面的空格分析下，为m-i个，*为i+1个，中间行全是是n个，然后依次类推。至于中间用空行隔开，我们可以用一个旗子来表示，刚开始没有插旗子，不能输出空行，执行一次就插上了旗子，当然是否要输出空行要在插旗子之前。详见代码flag的操作。
python直接把字符串乘起来，很方便

flag = 0
while True:
    try:
        n = int(input())
        if flag==1:
            print()
        flag = 1
        m = n//2
        for i in range (-m,m + 1):
            if i < 0:
                print(' ' * abs(i) + '*' *(m - abs(i) + 1))
            elif i == 0:
                print('*' * n)
            else:
                print(' ' * m + '*' * (m - i + 1))
    except EOFError:
        break

7.6180: Alice玩井棋

这是一个比较有趣的游戏，但是不同的思路实现起来难度可能不同，在这里推荐了一个比较简单的实现，
1.横或竖坐标均相同
2.在左上到右下的对角线上
3.在右上到左下对角线上
我的代码实现是把他们进行编号
0 1 2
4 5 6
8 9 10

while True:
    try:
        c=[]
        for i in range(3):
            a,b=map(int,input().split())
            c.append((a-1)*4+(b-1))
        c.sort()
        if c[1]-c[0]==1 and c[2]-c[1]==1:
            print('Win')
        elif c[1]-c[0]==4 and c[2]-c[1]==4:
            print('Win')
        elif c[0]==0 and c[1]==5 and c[2]==10:
            print('Win')
        elif c[0]==2 and c[1]==5 and c[2]==8:
            print('Win')
        else:
            print('Continue')
    except EOFError:
        break

8.6174: Alice与甜甜圈

空圆柱体的体积，体积为底面积高，
圆环面积为(R*R-r*r)PI
可以使用math包里的PI

import math
while True:
    try:
        R,r,h = map(float,input().split())
        print ('%.2f' %(math.pi*h*(R*R-r*r)))
    except EOFError:
        break

9.6175: Alice买口罩

10个口罩一定会浪费掉，所以你买到y个口罩，买x个一次，次数为y/x
python的整数除法需要//

n,m=map(int,input().split())
print (m//n)

10.6176: 武汉加油！中国加油！

简单C语言输出，可以复制粘贴，尽量减少错误

print ("Fighting, Wuhan! Stay strong, China!")

天天快乐编程杯中学生信奥联赛(202002) 题解(Python版)

原文：https://www.cnblogs.com/BobHuang/p/12312134.html