我的博客

2020-04-20 笔试

目录
  1. 选择
  2. 编程
    1. 第一题
    2. 第二题

某所的 python 开发的笔试题,编程题很简单,选择题还有几个不错的。

选择

只记录几道看代码写输出的题目:

1
2
3
a ={} 
a.fromkeys(['a', 'b', 'c', 'd'], 100)
print (a)

{}

1
2
print(0.5 + 0.5 == 1)
print(0.1 + 0.2 == 0.3)

True
False

实际上 0.1 + 0.2 的结果是:0.30000000000000004,浮点数比较可以通过两数相减,取绝对值,如果小于一个很小的数(如 1e-6)就认为相等。

编程

第一题

题目描述
疫情正在某大洋岛国蔓延,且有失控之势。为了保证该国人民的安全,该国元首决定发挥该国岛屿众多的优势,将健康的人群送到该国的各个岛屿上去,这样就可以有效对人群进行隔离。

作为一名政府公务员,现在你被授命统计本国的岛屿数量。陆地和海洋已经在地图上按照网格的方式给标注出来了,例如:

11110
11010
11001
00000

其中,1表示陆地,0表示海洋,而所谓岛屿,是由若干块连续的陆地连接成的区域。当然,作为处于大洋中的岛国,在网格之外的四个边缘都是海洋区域。因此,上面这块地图中,有2个岛屿,第一个岛屿一共占9块网格,第二个岛屿占1块网格。下面是另一个区域的网格图:

11000
10000
00100
00010

可以看到,这个地图上,有三个岛屿,分别占3块、1块、1块网格。

为了提高效率,现在你准备用一个程序来统计任一区域中的岛屿数量,请写出程序。

输入描述:
输入一个二维数组,只有0和1,分别表示该区域的海洋和陆地。

输出描述:
输出一个数字,表示该数组表示的区域的岛屿数量。

示例 (输入输出示例仅供调试,后台判题数据一般不包含示例)
示例1
输入

1,1,1,1,0
1,1,0,1,0
1,1,0,0,1
1,0,0,0,0

输出

2

示例2

输入
1,0,0,1,0
1,1,0,1,0
0,0,1,0,1
0,0,0,0,1
0,1,1,1,1

输出

4

题目提示
1.本系统是构建在Ubuntu 14.04 64位操作系统之上,所有文件名大小写敏感,在c/c++引用头文件时尤其需要注意;

  1. 请不要自行输出提示信息,例如:printf(“Please input two numbers: “)、raw_input(‘Please input two numbers: ‘)等等,这将会导致您的答案不正确,因为任何的输出到屏幕都会作为您答案的一部分;

3.系统对于每一道编程试题均提供实时评测结果,您可在考试允许时间内多次提交您的代码以获得您所希望得到的结果,系统将以您的最后一次提交结果为准,但提交次数也将作为考试成绩的一部分。

4.请严格依照题目描述的格式输入输出数据,尤其参照试题所提供的样例,当然试题的样例输入/输出并不代表评测试题的全部数据。

5.关于自测,您可在页面左下角的输入框内填写输入数据,再点击保存并调试,即可看到程序输出的结果。

6.Python使用的是2.7&3两个版本,缩进可以使用tab、4个空格或2个空格,但是只能任选其中一种,不能多种混用;如果使用sys.stdin.readline,因为默认会带换行符,所以要strip(‘\n’)进行截取;建议使用raw_input()。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
import sys
mp = []
for l in sys.stdin:
l = l.strip()
if not l:
break
mp.append(list(map(int, l.strip().split(','))))
n = len(mp)
m = len(mp[0])
f = [[False] * m for _ in range(n)]
def vis(i, j):
f[i][j] = True
for x, y in [(0,1), (1,0), (0,-1), (-1,0)]:
if 0 <= i + x < n and 0 <= j + y < m and f[i+x][j+y] == False and mp[i+x][j+y] == 1:
vis(i+x, j+y)
c = 0
for i in range(n):
for j in range(m):

if f[i][j] == False and mp[i][j] == 1:
vis(i, j)
c += 1
print(c)

第二题

题目描述
你在读的经营课程上,老师布置了一道作业。在一家公司的日常运营中,是会对一些商品的价格走势根据一些经验和数据进行预估,并据此进行决策。例如,假设某商品每天的价格都有可能变动,我们要做的就是低买高卖获得最高利润。比如假设我们预估该商品接下来七天内的价格走势如下:

4,1,2,3,6,4,8

那我们采取的最佳策略是在价格1块钱的时候买入,在价格8块钱的时候卖出。为了简化整个过程,我们限定在此周期内只能有一次买入一次卖出,且商品在没有购入前是无法卖出的,即该商品不是期货而是现货。

现要求你用程序来实现自动决策。输入一定天数的商品预估价格,自动计算出最优利润值。例如,上面的例子中,最优利润值为8-1=7。

输入描述:
输入一个数组,分别表示各天的预估价格

输出描述:
根据输入的预估价格,算出并输出最优的利润值。

示例 (输入输出示例仅供调试,后台判题数据一般不包含示例)
示例1
输入

4,1,2,3,6,4,8

输出

7

示例2
输入

5,3,8,2,5,8,4

输出

6

示例3
输入

10,8,7,5,4,2

输出

0

题目提示

  1. 本系统是构建在Ubuntu 14.04 64位操作系统之上,所有文件名大小写敏感,在c/c++引用头文件时尤其需要注意;

  2. 请不要自行输出提示信息,例如:printf(“Please input two numbers: “)、raw_input(‘Please input two numbers: ‘)等等,这将会导致您的答案不正确,因为任何的输出到屏幕都会作为您答案的一部分;

  3. 系统对于每一道编程试题均提供实时评测结果,您可在考试允许时间内多次提交您的代码以获得您所希望得到的结果,系统将以您的最后一次提交结果为准,但提交次数也将作为考试成绩的一部分。

  4. 请严格依照题目描述的格式输入输出数据,尤其参照试题所提供的样例,当然试题的样例输入/输出并不代表评测试题的全部数据。

  5. 关于自测,您可在页面左下角的输入框内填写输入数据,再点击保存并调试,即可看到程序输出的结果。

  6. Python使用的是2.7&3两个版本,缩进可以使用tab、4个空格或2个空格,但是只能任选其中一种,不能多种混用;如果使用sys.stdin.readline,因为默认会带换行符,所以要strip(‘\n’)进行截取;建议使用raw_input()。

1
2
3
4
5
6
7
8
9
10
p = list(map(int, input().split(',')))
mp = []
m = p[0]
for x in p:
m = min(m, x)
mp.append(m)
a = 0
for m, x in zip(mp, p):
a = max(x-m, a)
print(a)

python 同时向屏幕(stdout)和文件输出的方法

目录

以前知道有 tee 命令可以在实现,但是用的很少。

而且我的需求是,最近在 Jupyter Notebook 中执行脚本,需要关掉文件以后仍能看到期间的输出。

我自己的实现是写一个 log 函数代替 print,今天读到一个别人的方法。(代码

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

run_log_counter = 0

while(os.path.exists(args.folder + '/run_{}.log'.format(run_log_counter))):
run_log_counter += 1

file_log = open(args.folder + '/run_{}.log'.format(run_log_counter),'w') # File where you need to keep the logs
file_log.write("")
class Unbuffered:
def __init__(self, stream):
self.stream = stream
def write(self, data):
self.stream.write(data)
self.stream.flush()
file_log.write(data) # Write the data of stdout here to a text file as well
def flush(self):
pass

sys.stdout = Unbuffered(sys.stdout)

这样 print 的结果都会被写入到文件里了。

文本+视觉模型复现

目录
  1. LXMERT
  2. vilbert-multi-task

LXMERT

论文:LXMERT: Learning Cross-Modality Encoder Representations from Transformers

https://arxiv.org/abs/1908.07490

先预处理提取图片特征:通过物件识别得到 ROI(region of interest),和图片特征

https://codeplot.top/2020/04/11/%E5%9C%A8-multimodal-Twitter-dataset-%E4%B8%8A%E4%BD%BF%E7%94%A8-LXMERT/

vilbert-multi-task

论文:ViLBERT: Pretraining Task-Agnostic Visiolinguistic Representations for Vision-and-Language Tasks

https://arxiv.org/abs/1908.02265

https://codeplot.top/2020/04/05/%E5%9C%A8-multimodal-Twitter-dataset-%E4%B8%8A%E4%BD%BF%E7%94%A8-vilbert-multi-task/

4 月 12 日笔试

目录
  1. 第一题
  2. 第二题
  3. 第三题
  4. 第四题

一共四道题,2 小时,快手笔试

第一题

输入一个字符串,返回一个字符串,返回的字符串中把原字符串连续的超过两个相同字母删掉,如果一次删除后还有连续超过两个相同字母则继续删除。

例如:输入 'abbcccba' 输出 'aa'

字符串长度 10 ^ 5

我只想到模拟方法,虽然过了,但是实际上极端数据是过不了的例如:

1
2
3
4
5
6
7
8
9
l = []
x = 10 ** 5 // 3
for i in range(x):
l.append('a')
l.append('b')
for i in range(x):
l.append('bb')
l.append('aa')
s = ''.join(l)

我的代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
s = list(input())
while True:
skip = []
i = 2
while i < len(s):
if s[i-1] == s[i-2] == s[i]:
j = i
while j < len(s) and s[j] == s[i]:
j += 1
skip.append((i-2, j))
i = j + 2
else:
i += 1
if not skip:
break
ss = []
i = 0
for x, y in skip:
ss += s[i:x]
i = y
ss += s[i:]
s = ss
print(''.join(s))

第二题

用火柴棒摆数字,要求只能且必须移动一根火柴棒,问能得到的最大的数是多少。输入一个正数,输出一个整数。所有移动都无效时输出 -1

样例:109 输出 705

我先写了表示火柴棒数字的代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def pn(n):
assert len(n) == 7
if n[0]:
print(' _ ')
else:
print(' ')
l = '| ' if n[1] else ' '
l += '| ' if n[2] else ' '
print(l)
print(' _ ' if n[3] else ' ')
l = '| ' if n[4] else ' '
l += '| ' if n[5] else ' '
print(l)
print(' - ' if n[6] else ' ')

num = [[1,1,1,0,1,1,1], [0,0,1,0,0,1,0], [1, 0, 1, 1, 1, 0, 1],[1, 0, 1, 1, 0, 1, 1],[0, 1, 1, 1, 0, 1, 0],[1, 1, 0, 1, 0, 1, 1],[1, 1, 0, 1, 1, 1, 1],[1, 0, 1, 0, 0,1, 0],[1,1,1,1,1,1,1],[1,1,1,1,0,1,1]]
for i in range(10):
print('----', i, '----')
pn(num[i])
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
---- 0 ----
_
| |

| |
-
---- 1 ----

|

|

---- 2 ----
_
|
_
|
-
---- 3 ----
_
|
_
|
-
---- 4 ----

| |
_
|

---- 5 ----
_
|
_
|
-
---- 6 ----
_
|
_
| |
-
---- 7 ----
_
|

|

---- 8 ----
_
| |
_
| |
-
---- 9 ----
_
| |
_
|
-

然后写了搜索数字间转换关系的代码:

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
selfx = [[] for _ in range(10)]
def change(i):
cn = num[i]
for j in range(7):
if cn[j] == 1:
for k in range(7):
if k == j:
continue
if cn[k] == 0:
cx = num[i][::]
cx[j] = 0
cx[k] = 1
if cx in num:
nn = num.index(cx)
# print(nn)
# if nn > i:
selfx[i].append(nn)
for i in range(10):
change(i)
selfx # [[6, 9], [], [3], [5, 2], [], [3], [0, 9], [], [], [6, 0]]

remove = [[] for _ in range(10)]
def change(i):
cn = num[i]
for j in range(7):
if cn[j] == 1:
cx = num[i][::]
cx[j] = 0
if cx in num:
nn = num.index(cx)
remove[i].append(nn)
for i in range(10):
change(i)
remove # [[], [], [], [], [], [], [5], [1], [6, 0, 9], [3, 5]]
add = [[] for _ in range(10)]
def change(i):
cn = num[i]
for j in range(7):
if cn[j] == 0:
cx = num[i][::]
cx[j] = 1
if cx in num:
nn = num.index(cx)
add[i].append(nn)
for i in range(10):
change(i)
add # [[8], [7], [], [9], [], [9, 6], [8], [], [], [8]]

selfx:当前数字自身移动可以变成哪些数字

add:当前数字加上一根变成哪些数字

remove:当前数字去掉一根可以变成哪些数字

这题过了 97 %,最后是 WA。估计是第二种情况的问题,原来只考虑了数字变大的情况,实际上是不对的,因为题意要求(开始没读好题意)无论变大变小,必须移动,只有所有移动都无效时才输出 -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
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
add = [[8], [7], [], [9], [], [9, 6], [8], [], [], [8]]
remove = [[], [], [], [], [], [], [5], [1], [6, 0, 9], [3, 5]]
selfx = [[6, 9], [], [3], [5], [], [], [9], [], [], []]
selfx2 = [[6, 9], [], [3], [5, 2], [], [3], [0, 9], [], [], [6, 0]]
n = list(map(int, list(input())))
# n = [1, 0, 9]
# print(n)

def find_inc(i,e, x, ii=99999, s=1):
for j in range(i, e, s):
if j == ii: continue
if x[n[j]] and max(x[n[j]]) > n[j]:
return j, max(x[n[j]])
def find_dec(i, e, x, ii=99999, s=-1):
# print(i, e)
for j in range(i, e, s):
if j == ii: continue
if x[n[j]]:
return j, max(x[n[j]])

for i in range(len(n)):
# print('iiii', i)
op = []
if add[n[i]] and max(add[n[i]]) > n[i]:
op.append([max(add[n[i]]), 'a'])
if remove[n[i]] and max(remove[n[i]]) > n[i]:
op.append([max(remove[n[i]]), 'r'])
if selfx[n[i]] and max(selfx[n[i]]) > n[i]:
op.append([max(selfx[n[i]]), 's'])
op.sort(reverse=True)
# print(n[i], op)
f = False
for o in op:
if o[1] == 's':
n[i] = o[0]
f = True
break
elif o[1] == 'a':
xx = find_inc(i+1, len(n), remove)
if not xx:
xx = find_dec(len(n)-1, i, remove)
if xx:
n[i] = o[0]
n[xx[0]] = xx[1]
f = True
break
else:
xx = find_inc(i+1, len(n), add)
if not xx:
xx = find_dec(len(n)-1, i, add)
if xx:
n[i] = o[0]
n[xx[0]] = xx[1]
f = True
break
if f:
break
if f:
break
if f:
break
if f:
print(''.join(map(str,n)))
else:
for i in range(len(n)-1, -1, -1):
# print('iiii', i)
op = []
if add[n[i]] and max(add[n[i]]) < n[i]:
op.append([max(add[n[i]]), 'a'])
if remove[n[i]] and max(remove[n[i]]) < n[i]:
op.append([max(remove[n[i]]), 'r'])
if selfx2[n[i]] and max(selfx2[n[i]]) < n[i]:
op.append([max(selfx2[n[i]]), 's'])
op.sort(reverse=True)
# print(n[i], op)
f = False
for o in op:
if o[1] == 's':
n[i] = o[0]
f = True
break
elif o[1] == 'a':
xx = find_inc(0, len(n), remove, i)
if not xx:
xx = find_dec(len(n)-1, -1, remove, i)
if xx:
n[i] = o[0]
n[xx[0]] = xx[1]
f = True
break
else:
xx = find_inc(0, len(n), add, i)
if not xx:
xx = find_dec(len(n)-1, -1, add, i)
if xx:
n[i] = o[0]
n[xx[0]] = xx[1]
f = True
break
if f:
break
if f:
break
if f:
break
if f:
print(''.join(map(str,n)))
else:
print(-1)

第三题

输入两个数 k,n,返回数列的第 n 项模 397 的结果。

数列规则如下,前 k 项(0 ~ k-1)都是 1。第 k+1 项开始,每一项都是前面 k 项的和(那么说第 k + 1 项一定等于 k)

样例是:

2 4 输出 5

解释: 1 1 2 3 5 8 13 ……

我写了模拟,只出了 10%

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
n = 6
x = [k]
cur = k
for i in range(k - 1):
kk = (sum(x) + k-i-1) % 397
x.append(kk)
i = 0
j = k*2 - 1
while j < n:
j += 1
# print(x, i)
x[i] = sum(x) % 397
# print(x)
i = (i + 1)% k
print(x[i-1])

第四题

物资分配,n 个物资集散中心,有一个蓝对勾中心负责分配物资,物资都要运到蓝对勾,现在要额外修建 k 个蓝对勾分部,分部都建立在物质中心。

输入:第一行 n,k

以后 n 行每行四个数:物资中心编号(从 1 开始),货物数量,距离最近的物资中心编号,距离

单位货物运输单位距离需要 100 块。求如何修建分部使运输成本最小,输出最小成本。

每个物资中心能直接到达临近物资中心或者直接到蓝对勾总部(用编号 0 代表)保证无环。

这题没记下样例,也没写出来

在 multimodal Twitter dataset 上使用 LXMERT

目录
  1. 数据预处理
    1. 下载模型
    2. 启动并进入 docker 容器

LXMERT 代码仓库:https://github.com/airsplay/lxmert

论文:LXMERT: Learning Cross-Modality Encoder Representations from Transformers

支持的数据集:VQA、GQA、NLVR2

数据预处理

Faster R-CNN

安装 nvidia-docker:https://github.com/NVIDIA/nvidia-docker

先建立一个存放处理后的特征的文件夹:mkdir /tmp/sarcasm_image

把特征提取代码复制过去:cp data/vg_gqa_imgfeat/extract_gqa_image.py /tmp/sarcasm_image/

下载模型

1
wget 'https://www.dropbox.com/s/nu6jwhc88ujbw1v/resnet101_faster_rcnn_final_iter_320000.caffemodel?dl=1' -O data/nlvr2_imgfeat/resnet101_faster_rcnn_final_iter_320000.caffemodel

但是我得到的是 404 错误。

所以我到这里(https://github.com/peteanderson80/bottom-up-attention#demo)下载了模型 ,这个模型的 md5 是 53dec87566b0efc9648ffdfa8b81a6ee,我后来在 issue 里发现百度网盘的链接里有这个文件,于是又到百度网盘里下载, md5 是:6edf1e9f7a6e0bd7ca2af53390000b05,文件名 resnet101_faster_rcnn_final_iter_320000.caffemodel

再把模型拷贝过去:

1
cp resnet101_faster_rcnn_final_iter_320000.caffemodel /tmp/sarcasm_image/

启动并进入 docker 容器

1
docker run --gpus all -v /home/sxw/jupyter_workspace/Data/sarcasm/dataset_image/:/workspace/images:ro -v /tmp/sarcasm_image:/workspace/features --rm -it airsplay/bottom-up-attention bash

进入容器后,确认正确挂在了需要的文件:

root@800084edae63:/workspace# ls

features images

root@800084edae63:/workspace# ls features/ -lht

total 259M
-rw-rw-r– 1 1002 1002 259M Apr 11 06:18 resnet101_faster_rcnn_final_iter_320000.caffemodel
-rw-r–r– 1 root root 6.4K Apr 11 04:41 extract_gqa_image.py

root@800084edae63:/workspace# ls images/ -lht | head

total 2.6G
-rw-rw-r– 1 1002 1002 137K Mar 9 06:33 940985374565953537.jpg
-rw-rw-r– 1 1002 1002 157K Mar 9 06:33 941003843675942913.jpg
-rw-rw-r– 1 1002 1002 47K Mar 9 06:33 941028485794955264.jpg
-rw-rw-r– 1 1002 1002 31K Mar 9 06:33 941062957185744896.jpg
-rw-rw-r– 1 1002 1002 42K Mar 9 06:33 941083385396695041.jpg
-rw-rw-r– 1 1002 1002 79K Mar 9 06:33 941430864038174720.jpg
-rw-rw-r– 1 1002 1002 79K Mar 9 06:33 941434627436302336.jpg
-rw-rw-r– 1 1002 1002 28K Mar 9 06:33 941443078115774464.jpg
-rw-rw-r– 1 1002 1002 40K Mar 9 06:33 941756290635665408.jpg

然后开始提取特征:

cd features/

CUDA_VISIBLE_DEVICES=0 python extract_gqa_image.py --caffemodel ./resnet101_faster_rcnn_final_iter_320000.caffemodel

在 multimodal Twitter dataset 上使用 vilbert-multi-task

目录
  1. 图片特征提取:
  2. 依赖安装

https://github.com/facebookresearch/vilbert-multi-task

https://gitlab.com/vedanuj/vqa-maskrcnn-benchmark

http://lil.nlp.cornell.edu/nlvr/NLVR2BiasAnalysis.html

https://github.com/lil-lab/nlvr/tree/master/nlvr2

Foil 也是二分类问题,所以我从 Foil 任务改造出 multimodal Twitter dataset 任务

Foil 数据集:

https://foilunitn.github.io/

图片特征提取:

说明:https://github.com/facebookresearch/vilbert-multi-task/tree/master/data

代码:https://github.com/facebookresearch/vilbert-multi-task/blob/master/script/extract_features.py

使用了 maskrcnn_benchmark 得到图片中物体的位置

依赖安装

项目的 requirements.txt 有问题

https://github.com/facebookresearch/vilbert-multi-task/issues/14

pytorch-transformers==1.0.0 要改为 pytorch-transformers==1.1.0

需要安装 h5py

(vilbert-multi-task) (base) xxx@xxxx-xxx:~/multimodal_sarcasm_detection/Code/related_work/vilbert-multi-task/vilbert-multi-task$ python train_tasks.py –bert_model bert-base-uncased –from_pretrained ../multi_task_model.bin –config_file config/bert_base_6layer_6conect.json –tasks 19 –lr_scheduler ‘warmup_linear’ –train_iter_gap 4 –task_specific_tokens –save_name multi_task_model

python eval_tasks.py –bert_model bert-base-uncased –from_pretrained ../multi_task_model.bin –config_file config/bert_base_6layer_6conect.json –tasks 19 –lr_scheduler ‘warmup_linear’ –train_iter_gap 4 –task_specific_tokens –save_name multi_task_model

1
python train_tasks.py --bert_model bert-base-uncased --from_pretrained ../multi_task_model.bin --config_file config/bert_base_6layer_6conect.json --tasks 19 --lr_scheduler 'warmup_linear' --train_iter_gap 4 --task_specific_tokens --save_name multi_task_model

attention 可视化

目录

matplotlib 图像叠加显示热力图

https://blog.csdn.net/nkhgl/article/details/103183978

1
2
plt.imshow(np.hstack(img[i].cpu().numpy().reshape(3,224*224, 1)).reshape(224,224,3))
plt.imshow(rescale(xx), alpha=0.4, cmap=plt.cm.hot, vmin=0, vmax=1)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
i = 1
xx = []
for l in attentions[i][-49:].reshape(7,7):
x = []
for v in l:
x += [v] * 32
xx += [x] * 32
cimg = np.hstack(img[i].cpu().numpy().reshape(3,224*224, 1)).reshape(224,224,3)
plt.imshow(cimg)
heatmap = np.array(rescale(attentions[i][-49:].reshape(7,7)))
# heatmap = np.array(attentions[i][-49:].reshape(7,7))
heatmap = cv2.resize(100-heatmap, (224, 224))
# heatmap = np.uint8(255 * heatmap) # 将热力图转换为RGB格式
# heatmap = cv2.applyColorMap(heatmap, cv2.COLORMAP_JET) # 将热力图应用于原始图像
# plt.imshow(heatmap, alpha=0.4, vmin=0, vmax=1)
# plt.imshow(heatmap, alpha=0.4, cmap=plt.cm.hot, vmin=0, vmax=1)
# plt.imshow(heatmap, alpha=0.4, cmap='rainbow', vmin=0, vmax=1)
plt.imshow(heatmap, alpha=0.4, cmap=plt.cm.RdBu, vmin=0, vmax=100)

cnn 热力图

https://zhuanlan.zhihu.com/p/53683453

https://blog.csdn.net/Einstellung/article/details/82858974

https://www.jianshu.com/p/0431d6d89d8e

https://www.cnblogs.com/taotingz/p/11309333.html

华为云 ARM 服务器(鲲鹏)基本使用(Ubuntu 系统)

目录
  1. 换源
  2. 安装 pip 和 常用 python 库
  3. cpu info

选了默认的 ubuntu 18.04 系统结果默认的 apt 源没法用。

可以直接换成 清华源,但是注意要使用 ports 镜像,这是是为 arm 架构系统准备的,不能使用普通的 apt 源。

换源

清华源 https://mirrors.tuna.tsinghua.edu.cn/ubuntu-ports/

直接编辑 vi /etc/apt/sources.list

可以直接用命令替换

1
:%s/ports.ubuntu.com/mirrors\.tuna\.tsinghua\.edu.cn/g

也可以备份原文件后,重写文件内容为:

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
## Note, this file is written by cloud-init on first boot of an instance
## modifications made here will not survive a re-bundle.
## if you wish to make changes you can:
## a.) add 'apt_preserve_sources_list: true' to /etc/cloud/cloud.cfg
## or do the same in user-data
## b.) add sources in /etc/apt/sources.list.d
## c.) make changes to template file /etc/cloud/templates/sources.list.tmpl

# See http://help.ubuntu.com/community/UpgradeNotes for how to upgrade to
# newer versions of the distribution.
deb http://mirrors.tuna.tsinghua.edu.cn/ubuntu-ports bionic main restricted
deb-src http://mirrors.tuna.tsinghua.edu.cn/ubuntu-ports bionic main restricted

## Major bug fix updates produced after the final release of the
## distribution.
deb http://mirrors.tuna.tsinghua.edu.cn/ubuntu-ports bionic-updates main restricted
deb-src http://mirrors.tuna.tsinghua.edu.cn/ubuntu-ports bionic-updates main restricted

## N.B. software from this repository is ENTIRELY UNSUPPORTED by the Ubuntu
## team. Also, please note that software in universe WILL NOT receive any
## review or updates from the Ubuntu security team.
deb http://mirrors.tuna.tsinghua.edu.cn/ubuntu-ports bionic universe
deb-src http://mirrors.tuna.tsinghua.edu.cn/ubuntu-ports bionic universe
deb http://mirrors.tuna.tsinghua.edu.cn/ubuntu-ports bionic-updates universe
deb-src http://mirrors.tuna.tsinghua.edu.cn/ubuntu-ports bionic-updates universe

## N.B. software from this repository is ENTIRELY UNSUPPORTED by the Ubuntu
## team, and may not be under a free licence. Please satisfy yourself as to
## your rights to use the software. Also, please note that software in
## multiverse WILL NOT receive any review or updates from the Ubuntu
## security team.
deb http://mirrors.tuna.tsinghua.edu.cn/ubuntu-ports bionic multiverse
deb-src http://mirrors.tuna.tsinghua.edu.cn/ubuntu-ports bionic multiverse
deb http://mirrors.tuna.tsinghua.edu.cn/ubuntu-ports bionic-updates multiverse
deb-src http://mirrors.tuna.tsinghua.edu.cn/ubuntu-ports bionic-updates multiverse

## N.B. software from this repository may not have been tested as
## extensively as that contained in the main release, although it includes
## newer versions of some applications which may provide useful features.
## Also, please note that software in backports WILL NOT receive any review
## or updates from the Ubuntu security team.
deb http://mirrors.tuna.tsinghua.edu.cn/ubuntu-ports bionic-backports main restricted universe multiverse
deb-src http://mirrors.tuna.tsinghua.edu.cn/ubuntu-ports bionic-backports main restricted universe multiverse

deb http://mirrors.tuna.tsinghua.edu.cn/ubuntu-ports bionic-security main restricted
deb-src http://mirrors.tuna.tsinghua.edu.cn/ubuntu-ports bionic-security main restricted
deb http://mirrors.tuna.tsinghua.edu.cn/ubuntu-ports bionic-security universe
deb-src http://mirrors.tuna.tsinghua.edu.cn/ubuntu-ports bionic-security universe
deb http://mirrors.tuna.tsinghua.edu.cn/ubuntu-ports bionic-security multiverse
deb-src http://mirrors.tuna.tsinghua.edu.cn/ubuntu-ports bionic-security multiverse

## Uncomment the following two lines to add software from Canonical's
## 'partner' repository.
## This software is not part of Ubuntu, but is offered by Canonical and the
## respective vendors as a service to Ubuntu users.
# deb http://archive.canonical.com/ubuntu bionic partner
# deb-src http://archive.canonical.com/ubuntu bionic partner

我也不知道为啥这么多,我是直接替换的。

安装 pip 和 常用 python 库

apt install python3-pip

虽然装了 pip 但是用 pip 装 numpy 会失败,可能还是源的问题。

所以用 apt 安装 numpy

apt install python3-numpy

tqdm,jupyter 可以用 pip 装,但是 sklearn 也不行

apt install python3-sklearn

cpu info

1
2
3
4
5
6
7
8
processor       : 0
BogoMIPS : 200.00
Features : fp asimd evtstrm aes pmull sha1 sha2 crc32 atomics fphp asimdhp cpuid asimdrdm jscvt fcma dcpop asimddp
CPU implementer : 0x48
CPU architecture: 8
CPU variant : 0x1
CPU part : 0xd01
CPU revision : 0

Round A 2020 - Kick Start 2020 - python 版代码

目录
  1. Allocation
  2. Plates
  3. Workout
  4. Bundling
    1. 字典树
    2. 递归(测试数据 2 会超过递归层数限制)

https://codingcompetitions.withgoogle.com/kickstart/round/000000000019ffc7

Allocation

T 组数据,每组两行,第一行 N,B 代表有 N 个待售房屋,你拥有的钱是 B。第二行是 N 个整数,代表每个房屋的价格。
求能购买的最多房屋数量。

1
2
3
4
5
6
7
8
9
10
11
12
T = int(input())
for t in range(T):
N, B = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
cnt = 0
for x in a:
if B < x:
break
cnt += 1
B -= x
print('Case #%d: %d' % (t+1, cnt))

Plates

T 组数据。每组数据 N + 1 行:第一行 N, K, P,代表有 N 摞盘子,每摞都是 K 个。一共需要挑出 P 个。后面 N 行每行是 K 个整数代表这摞盘子中每个盘子的颜值,顺序是从上到下。

需要保证挑出的盘子的颜值的和最大。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
T = int(input())
for t in range(T):
N, K, P = map(int, input().split())
s = []
for _ in range(N):
s.append(list(map(int, input().split())))
for i in range(N):
for j in range(1, K):
s[i][j] += s[i][j-1]
s[i].append(0)
dp = [[0] * (P+1) for _ in range(N+1)]
for i in range(1, N+1):
for j in range(1, P+1):
for x in range(0, min(j, K)+1):
dp[i][j] = max(dp[i][j], dp[i-1][j-x] + s[i-1][x-1])
print('Case #%d: %d' % (t+1, dp[N][P]))

Workout

T 组数据,每组两行,第一行 N,K 代表一个严格递增数列中有 N 个数,我们可以向其中插入 K 个任意数字。第二行是这 N 个整数。
插入数字后我们希望数列的相邻数字差的最大值尽可能小,求这个最小值。

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
import math
T = int(input())
for t in range(T):
N, K = map(int, input().split())
s = list(map(int, input().split()))
d = []
for i in range(1, len(s)):
d.append(s[i]-s[i-1])
maxv = max(d)
if maxv < 2:
print('Case #%d: %d' % (t+1, maxv))
else:
d.sort(reverse=True)
l, r = 1, maxv
while l < r:
m = l + r >> 1
ks = 0
for dd in d:
if dd <= m:
break
ks += math.ceil(dd/m)-1
if ks > K:
l = m + 1
else:
r = m
print('Case #%d: %d' % (t+1, r))

Bundling

把 N 个字符串分成 K 个组(N 一定被 K 整除)。每组的分数是这一组字符串最长公共前缀的和。求全局分数最大

字典树

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
T = int(input())
for tt in range(T):
N, K = map(int, input().split())
ss = []
for _ in range(N):
ss.append(input())
base = ord('A')
class TrieNode:
def __init__(self):
self.cnt = 0
self.children = [None] * 26
def add(self, s):
self.cnt += 1
if not s:
return

if not self.children[i]:
self.children[i] = TrieNode()
self.children[i].add(s[1:])
root = TrieNode()
for s in ss:
t = root
for ch in s:
t.cnt += 1
i = ord(ch) - base
if not t.children[i]:
t.children[i] = TrieNode()
t = t.children[i]
t.cnt += 1
cnt = 0
root.cnt = 0
stack = [root]
while stack:
t = stack.pop()
cnt += t.cnt // K
for c in t.children:
if c and c.cnt >= K:
stack.append(c)
print('Case #%d: %d' % (tt+1, cnt))

递归(测试数据 2 会超过递归层数限制)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
T = int(input())
for t in range(T):
N, K = map(int, input().split())
ss = []
for _ in range(N):
ss.append(input())
ss.sort()
cnt = [0]
def find(i, j, k):
s = i
while s < j and k >= len(ss[s]):
s += 1
x = s
while s < j:
while x < j and ss[x][k] == ss[s][k]:
x += 1
if x - s >= K:
cnt[0] += (x - s) // K
find(s, x, k+1)
s = x
find(0, len(ss), 0)
print('Case #%d: %d' % (t+1, cnt[0]))