程序设计实习

【程序设计实习】第九次上机复盘

02:慈善晚宴排座次

描述

富豪们参加慈善晚宴，每个人都要捐款，首先按捐款数目从多到少排座次。
在捐款数目相同的富豪中，名字首字母是’P’、‘K’或 ‘U’的三大传统慈善家族人士，都会排在其它人前面。而捐款相同的传统慈善家族人士互相比较，以及非传统慈善家族人士互相比较时，谁先捐款谁就排在前面。

输入

第一行是整数 n , 表示富豪人数 （0 < n < 100）
接下来n行，每行有一个大写字母字符串和一个整数，分别代表一位富豪的名字和捐款数目。
先出现的就是先捐款的。

输出

按座次前后输出所有富豪名字及其捐款数目。每行一个富豪

样例输入 

1
2
3
4
5
6
7

6
SS 10
AE 10
JACK 20
UDI 10
PBC 10
LNO 30

样例输出 

1
2
3
4
5
6

LNO 30
JACK 20
UDI 10
PBC 10
SS 10
AE 10

提示

如果sort的key参数写成一个lambda表达式不太容易，就专门写一个key函数，例如叫f。f返回一个构造出来的列表或元组，其中有元素能体现是不是属于三大家族

Solution

老师这个给的提示其实没有用
我们直接用lambda表达式就可以了

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

n=int(input())
ma=[]
for i in range(0,n):
    lst=input().split()
    id=i
    pd=0
    k=lst[0]
    value=int(lst[1])
    if k[0]=='P' or k[0]=='K' or k[0]=='U':
        pd=1
    ma.append([k,value,pd,id])
ma.sort(key=lambda x:(-x[1],-x[2],x[3]))
for l in ma:
    print(l[0],end=' ')
    print(l[1])

04:访问的ip地址

描述

某网站统计了最近一段时间访问该网站的ip地址，但是由于意外，访问的记录被打乱了顺序。每一条访问记录包含三个信息：访问次序，访问ip地址，访问是否成功，保证输入数据每一条记录的访问次序均不相同。

请你统计这一段时间访问了该网站的所有ip地址，并统计每个ip地址的成功访问次数和失败访问次数。输出按照ip地址成功访问次数降序排序，成功访问次数相同的则按失败访问次数降序排序。如果两者均相同则按照每个ip地址的最初访问次序，早的在前，晚的在后。

输入

第一行是整数n（<=10000），表示记录数量。
下面n行每行是一条ip地址访问记录，包括访问次序（最早的访问次序从1开始），访问的ip地址，是否成功访问（1为成功，0为失败），用空格隔开。

输出

多行排序后的结果，每一行包括：ip地址，成功访问的次数，访问失败的次数。

样例输入 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

10
6 179.196.37.246 0
4 179.196.37.246 0
7 128.156.5.132 0
5 128.156.5.132 0
8 128.156.5.132 1
2 128.156.5.132 1
9 119.95.172.179 1
3 119.95.172.179 0
1 128.156.5.132 1
10 179.196.37.246 0

样例输出 

1
2
3

128.156.5.132 3 2
119.95.172.179 1 1
179.196.37.246 0 3

Solution

这里就讲一个，dict.items()，返回的是一个列表，元素是一个元组，元组的第一个元素是键，第二个是值
字典的值类型也可以是别的数据结构

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

n=int(input())
dict={}
for i in range(0,n):
    lst=input().split()
    x=int(lst[0])
    y=int(lst[2])
    if lst[1] not in dict:
        if y==0:
            dict[lst[1]]=[0,1,x]
        else:
            dict[lst[1]]=[1,0,x]
    else:
        if y==0:
            dict[lst[1]][1]+=1
        else:
            dict[lst[1]][0]+=1
        dict[lst[1]][2]=min(dict[lst[1]][2],x)
dict_2=sorted(dict.items(),key=lambda x:(-x[1][0],-x[1][1],x[1][2]))
for l in dict_2:
    print(l[0],end=' ')
    print(l[1][0],end=' ')
    print(l[1][1])

06:逃出迷宫

描述

“Boom!” 小锅一觉醒来发现自己落入了一个N*N(2 <= N <= 20)的迷宫之中，为了逃出这座迷宫，小锅需要从左上角(0, 0)处的入口跑到右下角(N-1, N-1)处的出口逃出迷宫。由于小锅每一步都想缩短和出口之间的距离，所以他只会向右和向下走。假设我们知道迷宫的地图（以0代表通路，以1代表障碍），请你编写一个程序，判断小锅能否从入口跑到出口？

输入

第一行为一个整数N，代表迷宫的大小
接下来N行为迷宫地图，迷宫地块之间以空格分隔
输入保证(0, 0)和(N - 1, N - 1)处可以通过

输出

一行字符串，如果能跑到出口则输出Yes，否则输出No

样例输入 

1
2
3
4
5
6

5
0 0 1 1 0
0 0 0 0 0
0 1 1 1 0
0 1 1 1 0
0 1 1 1 0

样例输出 

1

Yes

提示

用递归解。设计函数ok(r,c)，返回True或False，表示从位置(r,c)出发能否走到终点。
从(r,c）出发可以想办法往前走一步，然后看问题变成什么

Solution

这道题我知道肯定都会写
但是还是要注意审题，题目写着"只会向右和向下走"

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

def dfs(x,y):
    global n,ma,vis,dx,dy,flag
    if x==n and y==n:
        flag=1
        return 
    for i in range(1,3):
        ax=x+dx[i]
        ay=y+dy[i]
        if ax>=1 and ay>=1 and ax<=n and ay<=n and vis[ax][ay]==0 and ma[ax][ay]==0:
            vis[ax][ay]=1
            dfs(ax,ay)
            vis[ax][ay]=0
n=int(input())
ma=[[]]
vis=[[]]
dx=[0,1,0]
dy=[0,0,1]
for i in range(0,n):
    ma.append([0])
    vis.append([0])
for i in range(1,n+1):
    lst=input().split()
    for j in range(0,n):
        ma[i].append(int(lst[j]))
        vis[i].append(0)
vis[1][1]=1
flag=0
dfs(1,1)
if flag==1:
    print("Yes")
else:
    print("No")

08:垂直直方图

描述

输入4行全部由大写字母组成的文本，输出一个垂直直方图，给出每个字符出现的次数。注意：只用输出字符的出现次数，不用输出空白字符，数字或者标点符号的输出次数。

输入

输入包括4行由大写字母组成的文本，每行上字符的数目不超过80个。

输出

输出包括若干行。其中最后一行给出26个大写英文字母，这些字母之间用一个空格隔开。前面的几行包括空格和星号，每个字母出现几次，就在这个字母的上方输出一个星号。注意：输出的第一行不能是空行。

样例输入 

1
2
3
4

THE QUICK BROWN FOX JUMPED OVER THE LAZY DOG.
THIS IS AN EXAMPLE TO TEST FOR YOUR
HISTOGRAM PROGRAM.
HELLO!

样例输出 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

                            *
                            *
        *                   *
        *                   *     *   *
        *                   *     *   *
*       *     *             *     *   *
*       *     * *     * *   *     * * *
*       *   * * *     * *   * *   * * * *
*     * * * * * *     * * * * *   * * * *     * *
* * * * * * * * * * * * * * * * * * * * * * * * * *
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z

来源

翻译自USACO 2003 February Orange的试题。

Solution

我的第一反应，竖着输出？我们考虑横着怎么输出
找到最大的那个数，然后一步步减，如果能输出就输出不就好了？

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

lst=['A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z']
cnt=[]
for i in range(0,26):
    cnt.append(0)
for i in range(1,5):
    k=input()
    for j in range(0,len(k)):
        if ord(k[j])-ord('A')>=0 and ord(k[j])-ord('A')<=25:
            cnt[ord(k[j])-ord('A')]+=1
ans=0
for i in range(0,26):
    ans=max(ans,cnt[i])
for i in range(0,ans):
    for j in range(0,26):
        if cnt[j]<ans:
            print(' ',end=' ')
        else:
            print('*',end=' ')
    print()
    ans-=1
for i in range(0,26):
    print(lst[i],end=' ')

09:垃圾炸弹

描述

2018年俄罗斯世界杯（2018 FIFA World Cup）开踢啦！为了方便球迷观看比赛，莫斯科街道上很多路口都放置了的直播大屏幕，但是人群散去后总会在这些路口留下一堆垃圾。为此俄罗斯政府决定动用一种最新发明——“垃圾炸弹”。这种“炸弹”利用最先进的量子物理技术，爆炸后产生的冲击波可以完全清除波及范围内的所有垃圾，并且不会产生任何其他不良影响。炸弹爆炸后冲击波是以正方形方式扩散的，炸弹威力（扩散距离）以d给出，表示可以传播d条街道。 假设莫斯科的布局为严格的1025*1025的网格状，由于财政问题市政府只买得起一枚“垃圾炸弹”，希望你帮他们找到合适的投放地点，使得一次清除的垃圾总量最多（假设垃圾数量可以用一个非负整数表示，并且除设置大屏幕的路口以外的地点没有垃圾）。

输入

第一行给出“炸弹”威力d(1 <= d <= 50)。第二行给出一个数组n(1 <= n <= 20)表示设置了大屏幕(有垃圾)的路口数目。接下来n行每行给出三个数字x, y, i, 分别代表路口的坐标(x, y)以及垃圾数量i. 点坐标(x, y)保证是有效的（区间在0到1024之间），同一坐标只会给出一次。

输出

输出能清理垃圾最多的投放点数目，以及能够清除的垃圾总量。

样例输入 

1
2
3
4

1
2
4 4 10
6 6 20

样例输出 

1

1 30

Solution

我们考试一般不会考艰深算法，这点老师强调过了
那么，直接枚举啊
就是$O(n*1024^{2})$
这样当然够

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

d=int(input())
n=int(input())
mx=[]
my=[]
ma=[]
for i in range(0,n):
    k=input().split()
    mx.append(int(k[0]))
    my.append(int(k[1]))
    ma.append(int(k[2]))
ans=0
ret=0
for i in range(0,1025):
    for j in range(0,1025):
        temp=0
        for k in range(0,n):
            if abs(mx[k]-i)<=d and abs(my[k]-j)<=d:
                temp+=ma[k]
        if temp==ans:
            ret+=1
        if temp>ans:
            ret=1
            ans=temp
print(ret,end=' ')
print(ans)

10:画家问题

描述

有一个正方形的墙，由N*N个正方形的砖组成，其中一些砖是白色的，另外一些砖是黄色的。Bob是个画家，想把全部的砖都涂成黄色。但他的画笔不好使。当他用画笔涂画第(i, j)个位置的砖时， 位置(i-1, j)、 (i+1, j)、 (i, j-1)、 (i, j+1)上的砖都会改变颜色。请你帮助Bob计算出最少需要涂画多少块砖，才能使所有砖的颜色都变成黄色。

输入

第一行是一个整数n (1≤n ≤15)，表示墙的大小。接下来的n行表示墙的初始状态。每一行包含n个字符。第i行的第j个字符表示位于位置(i,j)上的砖的颜色。“w”表示白砖，“y”表示黄砖。

输出

一行，如果Bob能够将所有的砖都涂成黄色，则输出最少需要涂画的砖数，否则输出“inf”。

样例输入 

1
2
3
4
5
6

5
wwwww
wwwww
wwwww
wwwww
wwwww

样例输出 

1

15

Solution

这道题倒是卡了一下，但是，我们要记住，考暴力，也不过就是有技巧的暴力罢了
探求规律，会发现：每一层的状态由上一层决定（想想为什么）
于是，我们直接开始写，注意这里是开关灯题目
同时，还有一个坑的数据，$n=1$
下次要注意一下极端数据，尤其是$n=1$这种

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72

def dfs(x):
    global n,ma,pa,dx,dy,mi,tem,flag
    for i in range(1,n+1):
        if pa[x-1][i]==0:
            pa[x][i]=(pa[x][i]+1)%2
            tem+=1
            for k in range(1,5):
                ax=x+dx[k]
                ay=i+dy[k]
                if ax>=1 and ay>=1 and ax<=n and ay<=n:
                    pa[ax][ay]=(pa[ax][ay]+1)%2
    if x!=n:
        dfs(x+1) 
    if x==n:
        f=0
        for i in range(1,n+1):
            if pa[n][i]==0:
                return 
        if tem<mi:
            mi=tem
        flag=1
        return 
    return 
    
n=int(input())
ma=[[]]
pa=[[]]
dx=[0,1,-1,0,0]
dy=[0,0,0,1,-1]
mi=9999
tem=0
for i in range(0,n):
    ma.append([0])
    pa.append([0])
for i in range(1,n+1):
    k=input()
    for j in range(0,n):
        if k[j]=='w':
            ma[i].append(0)
        else:
            ma[i].append(1)
        pa[i].append(0)
for i in range(1,n+1):
    for j in range(1,n+1):
        pa[i][j]=ma[i][j]
if n==1:
    if ma[1][1]==0:
        print(1)
    else:
        print(0)
else:
    flag=0
    for i in range(0,1<<n):
        temp=i
        tem=0
        for j in range(1,n+1):
            if ((temp>>(j-1))&1)==1:
                tem+=1
                pa[1][j]=(pa[1][j]+1)%2
                for k in range(1,5):
                    ax=1+dx[k]
                    ay=j+dy[k]
                    if ax>=1 and ax<=n and ay>=1 and ay<=n:
                        pa[ax][ay]=(pa[ax][ay]+1)%2
        dfs(2)
        for j in range(1,n+1):
            for k in range(1,n+1):
                pa[j][k]=ma[j][k]
    if flag==0:
        print("inf")
    else:
        print(mi)
本博客已稳定运行
发表了27篇文章 · 总计103.29k字
© 2025 elainafan
使用 Hugo 构建
主题 Stack 由 Jimmy 设计