博客
关于我
NYOJ325 zb的生日(01背包,深搜DFS) NYOJ27 水池数目(深搜DFS) 简单题目【代码未经评测】
阅读量:765 次
发布时间:2019-03-23

本文共 2540 字,大约阅读时间需要 8 分钟。

题目防止横向.script的执行,慎重处理

问题一:分组西瓜

要给两个好友分西瓜,使两堆的质量差最小。每个西瓜的重量已知。

思路:使用动态规划求所有可能的子集和,找出最接近总重量的一半的那个和,两堆差值最小。

解决方案代码:

def min_difference():    import sys    input = sys.stdin.read().split()    ptr = 0    N = int(input[ptr])    ptr += 1    w = [int(input[ptr + i]) for i in range(N)]    sum_all = sum(w)    target = sum_all // 2    max_mask = 1 << N    dp = [float('inf')] * (max_mask)    dp[0] = 0    for mask in range(max_mask):        if dp[mask] == float('inf'):            continue        s = dp[mask]        for i in range(N):            if not (mask & (1 << i)):                new_mask = mask | (1 << i)                new_s = s + w[i]                diff = abs(sum_all - 2 * new_s)                if diff < dp[new_mask]:                    dp[new_mask] = diff    min_diff = min(dp)    print(min_diff)min_difference()

解释:

  • 读取输入并处理数据: 读取西瓜数量和每个西瓜的重量。
  • 计算总重量: 计算总重量,并计算目标值,即两堆应尽量接近的重量。
  • 动态规划数组初始化: 使用位mask表示子集,dp[mask]记录对应子集的重量。
  • 遍历所有子集: 对每个子集,扩展并更新可能的子集和。
  • 记录最小差值: 遍历所有可能的子集,找出使得两堆重量差最小的值,并输出结果。
  • 问题二:水池计数

    在二维地图中,计算连通的水池数量。每个水池周围的4个方向相邻的水池属于同一池。

    思路:使用BFS或DFS遍历每个地图中的水池,标记已访问的水池,统计不同连通区域的数量。

    解决方案代码:

    import sysfrom collections import dequedef count_water_pools():    input = sys.stdin.read().split()    ptr = 0    T = int(input[ptr])    ptr += 1    for _ in range(T):        m = int(input[ptr])        n = int(input[ptr + 1])        ptr +=2        grid = []        for i in range(m):            row = list(map(int, input[ptr:ptr+n]))            ptr +=n            grid.append(row)                visited = [ [False for _ in range(n)] for __ in range(m)]        count = 0                for i in range(m):            for j in range(n):                if grid[i][j] == 1 and not visited[i][j]:                    count +=1                    # BFS                    q = deque()                    q.append( (i,j) )                    visited[i][j] = True                    while q:                        x, y = q.popleft()                        for dx, dy in [ (-1,0), (1,0), (0,-1), (0,1) ]:                            nx = x + dx                            ny = y + dy                            if 0 <= nx < m and 0 <= ny < n:                                if grid[nx][ny] ==1 and not visited[nx][ny]:                                    visited[nx][ny] = True                                    q.append( (nx, ny) )        print(count)count_water_pools()

    解释:

  • 读取输入处理数据: 解析多组测试用例,读取地图数据。
  • 初始化结构: 创建一个标记已访问的矩阵,初始化计数器。
  • 遍历地图: 对于每个未被访问的水池(1),启动BFS,标记所有相连的水池为已访问。
  • 计数连通水池: 每次启动BFS时,计数加一。
  • 输出结果: 输出所有测试用例的水池数量。
  • 这两个问题通过动态规划和图遍历分别解决,分别找到最优的分组方式和连通的水池数量。

    转载地址:http://pugzk.baihongyu.com/

    你可能感兴趣的文章
    MySQL 中随机抽样:order by rand limit 的替代方案
    查看>>
    MySQL 为什么需要两阶段提交?
    查看>>
    mysql 为某个字段的值加前缀、去掉前缀
    查看>>
    mysql 主从
    查看>>
    mysql 主从 lock_mysql 主从同步权限mysql 行锁的实现
    查看>>
    mysql 主从互备份_mysql互为主从实战设置详解及自动化备份(Centos7.2)
    查看>>
    mysql 主从关系切换
    查看>>
    MYSQL 主从同步文档的大坑
    查看>>
    mysql 主键重复则覆盖_数据库主键不能重复
    查看>>
    Mysql 事务知识点与优化建议
    查看>>
    Mysql 优化 or
    查看>>
    mysql 优化器 key_mysql – 选择*和查询优化器
    查看>>
    MySQL 优化:Explain 执行计划详解
    查看>>
    Mysql 会导致锁表的语法
    查看>>
    mysql 使用sql文件恢复数据库
    查看>>
    mysql 修改默认字符集为utf8
    查看>>
    Mysql 共享锁
    查看>>
    MySQL 内核深度优化
    查看>>
    mysql 内连接、自然连接、外连接的区别
    查看>>
    mysql 写入慢优化
    查看>>