pdd2020-09-01

给一个m*n的矩阵，矩阵由0和1组成，1表示一个士兵，相连(上下左右视为相连)的士兵组成一个团队，现在可以移动一个已有士兵到任何位置，求一个团队最多能有多少个士兵

个人思路：

• 1.首先统计所有1的数量one_count，发现矩阵全部是1，直接返回矩阵size；全部是0，返回0
• 2.否则说明有士兵，也有空位可以供士兵移动。对每一个0，可以尝试把一个1换到这个位置，dfs搜索该区域，更新ans
• 3.如果最终ans比所有1的数量one_count还多1，说明填充的1是凭空填充的，填充后原来所有的1会联通。这时直接返回step1中统计的1的数量one_count，否则返回ans

结果：部分超时
原因分析：对于不同的0，可能连接了同一区域内不同位置的1，从而对同一区域进行了多次dfs搜索，产生了重复计算

代码如下：

import sys 
content = list(sys.stdin)
matrix = []
content_size = len(content)
for i in range(1, content_size):
    matrix.append(content[i].strip().split())

# 主函数
def func(matrix):
    r = len(matrix)
    c = len(matrix[0])
    res = 0
    one_count = 0
    for i in range(r):
        for j in range(c):
            if matrix[i][j] == '1':
                one_count += 1
    # 如果全是1，直接返回
    if one_count == r*c:
        return r*c
    if one_count == 0:
        return 0
    
    # 如果存在0和1
    for i in range(r):
        for j in range(c):
            if matrix[i][j] == '0':
                visited_pos = set()
                visited_pos.add((i,j))
                dfs(matrix, i, j, visited_pos)
                res = max(res, len(visited_pos))
    # 如果res比所有1的数量还多1，说明填充的1是凭空填充的，填充后原来所有的1会联通
    if res == one_count + 1:
        return one_count
    return res 

def dfs(matrix, i, j, visited_pos):
    for p, q in getNei(matrix, i, j):
        if matrix[p][q] == '1':
            if (p, q) not in visited_pos:
                visited_pos.add((p,q))
                dfs(matrix, p, q, visited_pos)
    
def getNei(matrix, i, j):
    r = len(matrix)
    c = len(matrix[0])
    for p, q in [1,0],[-1,0],[0,1],[0,-1]:
        if 0 <= i + p < r and 0 <= j + q < c:
            yield i + p, q +j
            
print(func(matrix))

借鉴别人的思路，

• 1.先dfs/bfs搜索矩阵每一块士兵区域，编号并记录大小。这样每个区域只需计算一次
• 2.找到0，如果周围有2块区域且仍有其他区域，那么可以从任一其他区域拿一个1换到当前的0位置，更新ans
• 3.如果周围只有2块区域，那么可以从任一区域拿一个1换到当前的0位置，更新ans为区域总和

给一个n(n<=1e9)和m(m<=10)个数，一个数能被这m个数中的某个数整除的数被称为好数，求[1,n]中有多少个好数

输入
10 2
2
3
返回 7

说明
n=10, m=2, 对应2和3
10内被2整除的2，4，6，8，10；被3整除的3，6，9。合并后共7个

import sys 
content = list(sys.stdin)
feature = []
content_size = len(content)
num = int(content[0].strip().split()[0])
for i in range(1, content_size):
    feature.append(int(content[i].strip()))

# 用数组模拟32位的bitmap，一个int为32位，可以用来表示32个数，如在首个int中，000...0001表示32，1000...000表示1
bit32_map = [0 for i in range(num//32+1)]
for i in range(len(feature)):
    ele = feature[i]
    k = 1
    t = ele*k
    while t <= num:
        # 求出t对应的索引
        index = (t+32) // 32 - 1
        # 或运算
        bit32_map[index] = bit32_map[index] | (1 << (32-t%32)%32)
        k += 1
        t = ele*k
ans = 0
for ele in bit32_map:
    while ele:
        if ele & 1:
            ans += 1
        ele = ele >> 1
print(ans)