w这套题，重点考察图和搜索，考察对应用问题的抽象能力。
一、依赖分析工具
题目描述
你正在开发一个代码依赖分析工具。这个工具需要分析软件模块之间的依赖关系,用来优化代码的编译和构建过程。
在该工具中,"批量构建"是指将多个没有依赖关系的模块一次性进行编译和构建。例如,如果模块 A 依赖模块 B 和 C,模块 D 依赖模块 C,但模块 B 和 D 之间没有依赖关系,则需要先"批量构建"模块 B 和 C,再分别构建模块 A 和 D。
现在,给定一组模块间的依赖关系,请你计算需要"批量构建"的最少次数。
输入格式
第一行只有一个正整数 NN,表示模块总数。
随后的 N 行依次表示模块 1 到 N 的依赖关系。每行的第一个数据 KiKi 表示模块 ii 依赖的模块数量,之后跟着 Ki 个整数,表示模块 i 依赖的模块编号。模块编号的取值范围为 [1,N]且每行中的模块编号各不相同。
输出格式
输出"批量构建"的最少次数。若存在循环依赖导致无法完成构建,则输出 −1。
样例输入1
5
3 2 3 4
1 5
1 5
1 5
0
样例输出1
3
样例输入2
3
1 2
1 3
1 1
样例输出2
-1
评测数据与规模
- 1≤N≤10001≤N≤1000
- 0≤Ki<N0≤Ki<N
- 输入数据保证模块编号在 [1,N][1,N] 范围内,且不存在自依赖的情况。
题目分析：
【题目类型：图】
很直观的我们可以将依赖关系描述为有向图，每一次批构建就是处理入度为0的节点，然后将其从图中删除。如果最后图删空了，则删除的次数就是批构建的次数。如果图中没有入度为0的节点了，但是图不为空，则说明存在环，则无法构建，返回-1。
代码：
N = int(input())G = {}
top_list = []
ans = 0
for i in range(1, N+1):temp_in = input().split()cnt = int(temp_in[0])G[i] = []if cnt == 0:top_list.append(i)else:for j in range(1, cnt+1):G[i].append(int(temp_in[j]))while True:if len(top_list) == 0:if len(G.keys()) != 0:ans = -1breakans += 1next_top_list = []for node in top_list:del G[node]for node in G.keys():i = 0while i < len(G[node]):if G[node][i] in top_list:G[node].pop(i)else:i += 1if i == 0:next_top_list.append(node)top_list = next_top_list
print(ans)二、字符串重排
问题描述
字符串重排游戏规则如下：给定一个由小写字母组成的字符串 s,通过重新排列 s 中的字母,看看最多能组成多少个不同的回文字符串。回文字符串是指一个字符串正着读和反着读完全一样,例如"level"和"noon"都是回文字符串,而"code"不是。
请你写一个程序,计算给定字符串 s 经过重排后最多能组成的不同回文字符串数量。
输入格式
输入一行,包含一个由小写字母组成的字符串 s,表示初始字符串。
输出格式
输出一个整数,表示字符串s 经过重排后最多能组成的不同回文字符串数量。如果无法组成任何回文字符串,则输出 0。
样例输入
aabb
样例输出
2
评测数据与规模
- 1≤∣s∣≤10001≤∣s∣≤1000
- 字符串 ss 只包含小写字母
题目分析：
【题目类型：回文、全排序、找规律、大数计算】
统计每种字符的数量，超过1种字符的数量为奇数则无法组成回文。其余情况的我们计算一半字符的全排序即可。这里注意需要除以A(重复字符)的累乘。
【注意1】：这里由于s的长度回到达1000，那么就会存在A(500)的情况，存在大数计算。在python中整数位数是无限的，但是小数精度为64位。因为这里不涉及小数，所以应该使用整数除法 '//'，如使用小数除法'/'，会出现无法计算的情况。
【注意2】：这道题直接计算就能跑通，但是全排列A，是可以通过 A[i] = A[i-1]*i来保留中间计算过程的，达到空间换时间的作用，某些题目需要这样的方式加速。
代码：
def A(x):ans = 1for i in range(1, x+1):ans *= ireturn ansdef calc(table):extra = 1cnt = 0for k in table:temp = int(table[k]/2)cnt += tempextra *= A(temp)return int(A(cnt)//extra)str_in = input()
table = {}
for char in str_in:if char not in table.keys():table[char] = 1else:table[char] += 1OddCharCnt = 0
for k in table.keys():if table[k] % 2 != 0:OddCharCnt += 1ans = 0
if OddCharCnt == 0 or OddCharCnt == len(str_in)%2:ans = calc(table)
print(ans)三、农田修复
问题描述
农田受到地震的破坏，农田中的一些网点断开了联系。假设原本的农田网构成一个矩形，其中未被破坏的网点标记为 1，被破坏的网点标记为 0。标记为 1 的网点连在一起构成一个子网。现在，需要找到一个目标网点，并找出离它最近的其他子网。请注意，两个网点相连只能通过上下左右四个方向，不可以通过斜对角相连。两个网点的距离定义为从一个网点（假设网点名为 C）到达另一个网点（假设网点名为 D）需要经过相连网点的最小数目（C 和 D 这两个网点不计算在内）。两个子网（假设分别为 A 网和 B 网）不相连，A 网中所有的网点与 B 网中所有的网点的距离中最小的那个即为 A 网和 B 网的最小距离。
输入格式
第一行包含两个正整数 x,y，表示目标网点的坐标位置（x 表示行号，y 表示列号）。
第二行包含两个正整数 n,m，表示农田矩形的行数 n 和列数 m。
接下来的 n 行每行包含 m 个以空格分隔的整数 0 或 1，表示农田网点的破坏情况。
输出格式
输出一个整数，表示最近的未被破坏子网的距离。如果整网中只有一个子网，则返回 −1。
样例输入
1 1
6 6
1 1 0 0 1 0
1 1 0 0 1 1
0 0 0 0 1 0
0 1 0 1 0 0
1 1 0 0 0 0
1 1 1 0 1 1
样例输出
1
评测数据与规模
- 1≤n,m≤10001≤n,m≤1000。
- 输入保证目标网点是未被破坏的网点，且目标网点所在子网是一个子网。
题目分析：
【题目类型：BFS、曼哈顿距离、大水漫灌】
首先，用BFS找到当前位置的子区域，然后不断BFS，直到找到其他子区域为止。
代码：
# 1. 处理输入
temp_in = input().split()
x, y = int(temp_in[0])-1, int(temp_in[1])-1
temp_in = input().split()
n, m = int(temp_in[0]), int(temp_in[1])matirx = [ [ 1 for j in range(m)] for i in range(n) ]
visited = [ [ False for j in range(m)] for i in range(n) ]
for i in range(n):temp_in = input().split()for j in range(m):matirx[i][j] = int(temp_in[j])# 2. 向四个方向拓展
def explore(x_in,y_in):record = []for a, b in [[x_in-1, y_in], [x_in+1, y_in], [x_in, y_in-1], [x_in, y_in+1]]:if -1<a<n and -1<b<m and not visited[a][b]:record.append([a,b])return record# 3. 找寻当前子图全部的点
queue_i = 0
queue = [[x,y]]
while queue_i < len(queue):temp = queue[queue_i] if not visited[temp[0]][temp[1]]:visited[temp[0]][temp[1]] = Truearr = explore(temp[0],temp[1])i = 0while i < len(arr):if matirx[arr[i][0]][arr[i][1]] == 0:arr.pop(i)else:i+=1queue += arrqueue_i += 1else:queue.pop(queue_i)# 5. 子图BFS找到最近的其他子图
ans = -1
record = 0
while len(queue) > 0:# 寻找外边界next_queue = [] for a, b in queue:next_pos = explore(a,b)for temp_pos in next_pos:if temp_pos not in next_queue:next_queue.append(temp_pos)# 判断是否触及其他子图flag = Falsefor a,b in next_queue:if matirx[a][b] == 1:ans = recordflag = Truebreakelse: visited[a][b] = Trueif flag:breakqueue = next_queuerecord +=1print(ans)