11 皓首不倦

尚未进行身份认证

我要认证

算法爱好者 码农一枚 欢迎志同道合 技术爱好者加微信CODER-GRH 非技术人员勿扰

等级
TA的排名 1w+

AcWing DFS相关问题 165. 小猫爬山

import syssys.stdin = open('data.txt', 'r')'''先降序排序,然后递归枚举每一只猫放到哪辆车上,要么放在已经存在的车上,要么重新加一辆车,放到新车上'''arr = []n, w = map(int, input().split())for i in range(n): arr.append(int(input()))arr.sort(reverse=True)sum_weight = [0] * 20ans = [0x7.

2020-08-06 01:21:41

AcWing BFS相关问题 1107. 魔板

import syssys.stdin = open('data.txt', 'r')'''BFS 状态拓展应用'''from collections import dequetarget = list( map(int, input().split()) )def hash(arr): ans = 0 base = 1 for i in range(8): ans += arr[i] * base base *= 10 .

2020-08-06 01:20:32

AcWing BFS相关问题 1100. 抓住那头牛

import syssys.stdin = open('data.txt', 'r')'''简单BFS找最短路长度'''from collections import dequem, n = map(int, input().split())def bfs(m, n): que = deque() que.append(m) visited = {m} step = 0 while len(que) > 0: node..

2020-08-06 01:18:28

AcWing BFS相关问题 1098. 城堡问题

import syssys.stdin = open('data.txt', 'r')from collections import dequegrid = []m, n = map(int, input().split())for i in range(m): grid.append( list(map(int, input().split())) )def bfs(i, j) -> int: que = deque() que.append((i, j.

2020-08-06 01:17:35

AcWing BFS相关问题 1097. 池塘计数

import syssys.stdin = open('data.txt', 'r')from collections import dequegrid = []m, n = map(int, input().split())for i in range(m): s = input() grid.append( [val for val in s] )def bfs(i, j): que = deque() que.append((i, j)) .

2020-08-06 01:16:35

AcWing BFS相关问题 1076. 迷宫问题

import syssys.stdin = open('data.txt', 'r')'''简单bfs应用'''from collections import dequegrid = []n = int(input())for i in range(n): grid.append( list(map(int, input().split())) )prev = {(0, 0): None} # 记录路径que = deque()que.append((0, 0).

2020-08-06 01:15:43

AcWing BFS相关问题 188. 武士风度的牛

import syssys.stdin = open('data.txt', 'r')'''BFS层次遍历,求最短路径长度'''from collections import dequen, m = map(int, input().split())si, sj = -1, -1ei, ej = -1, -1grid = []for i in range(m): s = input() grid.append( [ch for ch in s] ) ..

2020-08-06 01:14:26

AcWing BFS相关问题 173. 矩阵距离

import syssys.stdin = open('data.txt', 'r')'''多源BFS应用'''from collections import dequem, n = map(int, input().split())one_pos = []for i in range(m): s = input() for j in range(n): if s[j] == '1': one_pos.append((i, ..

2020-08-06 01:12:56

AcWing A*算法相关问题 179. 八数码

import syssys.stdin = open('data.txt', 'r')from copy import deepcopyfrom queue import PriorityQueuedef arr2grid(arr): return [ [arr[0], arr[1], arr[2]], [arr[3], arr[4], arr[5]], [arr[6], arr[7], arr[8]] ]def distance(grid): m = {1:(0, 0.

2020-08-06 01:11:20

AcWing A*算法相关问题 178. 第K短路

import syssys.stdin = open('data.txt', 'r')'''先利用反向边用单元最短路求所有点到终点的最短距离,把这个距离作为预估值做A*,第k次出队列的状态中的距离就是答案'''from typing import List, Tuplefrom queue import PriorityQueueclass DijkStra: # start_node 是单源最短路起点 edges是边的三元组(节点1, 节点2, 边权重) nodes是..

2020-08-06 01:09:55

AcWing 状态压缩DP相关问题 1064. 小国王

'''原点加上任意两个点可以确定一条抛物线,先把所有抛物线全部算出来然后计算落到每条抛物线上的点信息,转换成一个区间覆盖问题求解用状态压缩DP解决'''# 计算点是否在抛物线上def is_match(x, y, a, b): val = a* x * x + b * x return abs(val - y) <= 1e-6# 1的数量def one_cnt(val): ans = 0 while val: ans += ..

2020-08-03 14:06:46

AcWing 状态压缩DP相关问题 524. 愤怒的小鸟

'''原点加上任意两个点可以确定一条抛物线,先把所有抛物线全部算出来然后计算落到每条抛物线上的点信息,转换成一个区间覆盖问题求解用状态压缩DP解决'''# 计算点是否在抛物线上def is_match(x, y, a, b): val = a* x * x + b * x return abs(val - y) <= 1e-6# 1的数量def one_cnt(val): ans = 0 while val: ans += ..

2020-08-03 14:05:48

AcWing 状态压缩DP相关问题 327. 玉米田

'''状态压缩DP求解'''M, N = map(int, input().split())grid = [0] * Mfor line_idx in range(M): arr = list(map(int, input().split())) for i, val in enumerate(arr): if val == 1: grid[line_idx] |= (1 << i)# dp(i, j) 表示前i行进行放.

2020-08-03 14:04:32

AcWing 状态压缩DP相关问题 292. 炮兵阵地

import syssys.stdin = open('data.txt', 'r')from functools import lru_cacheN = int(input())link = {}weight = {}parent = {}for _ in range(N): arr = list( map(int, input().split()) ) link[arr[0]] = arr[3:] weight[arr[0]] = arr[1] ..

2020-08-03 14:03:40

AcWing 树形DP相关问题 1077. 皇宫看守

import syssys.stdin = open('data.txt', 'r')from functools import lru_cacheN = int(input())link = {}weight = {}parent = {}for _ in range(N): arr = list( map(int, input().split()) ) link[arr[0]] = arr[3:] weight[arr[0]] = arr[1] ..

2020-08-03 13:54:25

AcWing 树形DP相关问题 1075. 数字转换

import syssys.stdin = open('data.txt', 'r')'''树形DP, 树的最长路径的应用, 求一个森林里面所有树的最长路径的最大值'''N = int(input())# 先求所有值的约数factor = {}for i in range(1, N+1): for j in range(2, N // i + 1): # 约数不能是自己,所以从2开始枚举,如果约数可以是自己,从1开始枚举 if i*j not in fact.

2020-08-03 13:52:51

AcWing 树形DP相关问题 1074. 二叉苹果树

import syssys.stdin = open('data.txt', 'r')N, Q = map(int, input().split())link = {}for i in range(1, N): a, b, w = map(int, input().split()) if a not in link: link[a] = [] if b not in link: link[b] = [] link[a].a..

2020-08-03 13:51:25

AcWing 树形DP相关问题 1073. 树的中心

N = int(input())link = {}for i in range(1, N): a, b, w = map(int, input().split()) if a not in link: link[a] = [] if b not in link: link[b] = [] link[a].append((b, w)) link[b].append((a, w))# 随便选一个节点作为树的根,递归算每个节点到.

2020-08-03 13:50:09

AcWing 树形DP相关问题 1072. 树的最长路径

N = int(input())link = {}for i in range(1, N): a, b, w = map(int, input().split()) if a not in link: link[a] = [] if b not in link: link[b] = [] link[a].append((b, w)) link[b].append((a, w))# 随便选一个节点作为树的根,递归算每个节点到.

2020-08-03 13:49:16

AcWing 树形DP相关问题 323. 战略游戏

import syssys.stdin = open('data.txt', 'r')'''题目意思本质就是一条边上至少要选一个节点dp(i, j) 表示在以i为根的子树上做放置士兵的选择,在根节点i选择状态是j的情况下所有可能的选择中最少的士兵数量(j 只有0, 1两种选择)'''def dp(i, j, memo): if (i, j) in memo: return memo[(i, j)] if len(link[i]) == 0: .

2020-08-03 13:48:19

查看更多

勋章 我的勋章
  • 持之以恒
    持之以恒
    授予每个自然月内发布4篇或4篇以上原创或翻译IT博文的用户。不积跬步无以至千里,不积小流无以成江海,程序人生的精彩需要坚持不懈地积累!
  • 勤写标兵Lv4
    勤写标兵Lv4
    授予每个自然周发布9篇以上(包括9篇)原创IT博文的用户。本勋章将于次周周三上午根据用户上周的博文发布情况由系统自动颁发。
  • 分享精英
    分享精英
    成功上传11个资源即可获取