当前位置：首页 > news >正文

洛谷题解 | CF111C Petya and Spiders

news 来源：原创 2025/5/18 21:09:42

题目描述

Little Petya loves training spiders. Petya has a board $ n×m $ in size. Each cell of the board initially has a spider sitting on it. After one second Petya chooses a certain action for each spider, and all of them humbly perform its commands. There are 5 possible commands: to stay idle or to move from current cell to some of the four side-neighboring cells (that is, one command for each of the four possible directions). Petya gives the commands so that no spider leaves the field. It is allowed for spiders to pass through each other when they crawl towards each other in opposite directions. All spiders crawl simultaneously and several spiders may end up in one cell. Petya wants to know the maximum possible number of spider-free cells after one second.

输入格式

The first line contains two space-separated integers $ n $ and $ m $ ( $ 1<=n,m<=40,n·m<=40 $ ) — the board sizes.

输出格式

In the first line print the maximum number of cells without spiders.

输入输出样例 #1

输入 #1

1 1

输出 #1

输入输出样例 #2

输入 #2

2 3

输出 #2

说明/提示

In the first sample the only possible answer is:

In the second sample one of the possible solutions is:

 rdl rul s denotes command “stay idle”, l, r, d, u denote commands “crawl left”, “crawl right”, “crawl down”, “crawl up”, correspondingly.

题目简化

求在一个地图上放置障碍物的最小数量，使得所有空白格子都能被覆盖到。

题目思路

搜索。

首先遍历棋盘找到第一个没有蜘蛛的格子，如果找不到这样的格子，则更新最优解为当前留空格子数量 $x$ 。

对于没有蜘蛛的格子，尝试在其周围放置蜘蛛，调用搜索函数，更新留空格子数量 $x$ ，直到所有格子都被蜘蛛占满或者当前留空格子数量 $\ge$ 最优解（也就是说一定是最优解法）时终止。

在尝试放置蜘蛛后，恢复棋盘。

AC 代码

#include<bits/stdc++.h>
using namespace std;
int n,m,best,dx[5] = {0,1,0,-1,0},dy[5] = {-1,0,1,0,0},a[45][45];
///判断坐标是否在棋盘范围内
bool ok(int x,int y){return x >= 0 && x < n && y >= 0 && y < m;
}
void dfs(int x){vector<pair<int,int> > tmp;int xx = -1,yy = -1;//寻找没有蜘蛛的格子for(int i = 0;i < n;i++){for(int j = 0;j < m;j++){if(!a[i][j]){xx = i,yy = j;break;}}if(xx != -1) break;}//没有找到if(xx == -1){best = x;return;}if(x + 1 >= best) return;for(int i = 0;i < 5;i++){//尝试在空格子周围放置蜘蛛int x1 = xx + dx[i];int y1 = yy + dy[i];if(ok(x1,y1)){tmp.clear();for(int j = 0;j < 5;j++){//遍历当前位置(x1, y1)周围的五个点int x2 = x1 + dx[j];int y2 = y1 + dy[j];if(ok(x2,y2) && !a[x2][y2]){ //判断该点是否在棋盘范围内且没有蜘蛛tmp.push_back(make_pair(x2,y2)); //保存当前可以放置蜘蛛的位置a[x2][y2] = 1; //将蜘蛛标记为已占据}}dfs(x + 1); //搜索下一个没有蜘蛛的位置for(int j = 0;j < tmp.size();j++) a[tmp[j].first][tmp[j].second] = 0; //恢复之前放置蜘蛛后的状态}}
}
int main()
{cin >> n >> m;best = n * m;dfs(0);cout << n * m - best;return 0;
}

创作不易，白嫖不好，各位的支持和认可，就是我创作的最大动力，如果喜欢我的文章，给个关注吧！

冰焰狼 | 文

如果本篇博客有任何错误，请批评指教，不胜感激！

洛谷题解 | CF111C Petya and Spiders

目录题目描述输入格式输出格式输入输出样例 #1输入 #1输出 #1 输入输出样例 #2输入 #2输出 #2 说明/提示题目简化题目思路AC 代码题目描述 Little Petya loves training spiders. Petya has a board $ nm $ in size. Each cell of the board initially has a spider sitting…...

编程日记 2025/5/18 21:09:42

【深度对比】Google Play与IOS 马甲包处理差异分析

在移动应用发布与推广过程中，马甲包（Cloned App / Alternate Version） 曾被广泛用于流量测试、风险隔离、多品牌运营等场景中。随着 Google Play 与 Apple App Store 审核政策不断收紧，开发者们越来越关注两个平台对“马甲包”的态…...

编程日记 2025/4/30 12:19:01

【C++】C++11新特性（二）

目录完美转发引用折叠： lambda表达式完美转发引用折叠： 引用折叠是 C的类型系统规则，用于处理“引用的引用”（如 T& &）。在推导过程中，必须折叠成有效的单一引用类型。直接声明引用的引用…...

编程日记 2025/5/18 21:06:48

高等数学-第七版-下册选做记录习题9-4

1. 3. 4. 8....

编程日记 2025/5/18 21:08:09

特殊权限管理

特殊权限的类型 SUID（Set User ID）：当一个可执行文件设置了 SUID 权限后，在执行该文件时，进程会以文件所有者的身份运行，而不是以执行用户的身份。例如，/usr/bin/passwd文件用于修改用户密码&a…...

编程日记 2025/5/18 21:08:10

牛客周赛 Round 91

赛时成绩如下： A. while 题目描述小歪找到了一个由五个字符构成的字符串，它一次可以选择任意一个字符，将其修改为另一个字符，他想要知道，将这个字符串修改为 "while" 需要的最少操作次数。解题思路&#x…...

编程日记 2025/4/30 12:16:47

Kafka 的服务端的物理存储架构是什么？零拷贝，mmap，sendfile、DMA gather又是什么？

Kafka 服务端的物理存储架构 Kafka 的物理存储架构设计旨在支持高吞吐、低延迟的数据处理，其核心特点包括： 1. 分区与日志段主题（Topic）与分区（Partition）： Kafka 将每个主题划分为多个分区&…...

编程日记 2025/5/18 21:06:49

1.7 点云数据获取方式——视觉SLAM

图1-7-1 Visual SLAM生成的点...

编程日记 2025/5/16 7:41:17

双向流热固耦合的收敛

1 收敛性如果想把流固耦合计算过程的收敛性弄清楚，必须理解流固耦合的求解过程和对流场与固体场的定义设置： -这个与其他的真实物理场可能有所不同 -例如你的初始条件可能是不同的当遇到收敛困难时，需要看一下的求解过程用户使用监测点和…...

编程日记 2025/4/30 12:13:25

C++之类和对象：构造函数，析构函数，拷贝构造，赋值运算符重载

前提：如果一个类是空类，C中空类中真的什么都没有吗，不是的，编译器会自动生成6个默认成员函数。默认成员函数：用户没有显式实现，编译器会生成的成员函数称为默认成员函数。默认成员函数：构造函…...

编程日记 2025/5/6 20:49:35

Vue2 相关知识点整理

一、Vue2 核心机制 1. Vue2 的响应式原理是什么？ 答案： Vue2 通过 Object.defineProperty 给对象的每个属性添加 getter 和 setter，当数据被访问或修改时，自动触发视图更新。通俗解释： 就像给每个数据绑了一个“监控…...

编程日记 2025/4/30 12:11:14

CSS：编写位置分类及优先级

文章目录一、行内样式二、内部样式三、外部样式（推荐）四、优先级五、编码风格一、行内样式最好不这样写二、内部样式可以使用三、外部样式（推荐） 四、优先级行内样式 > 内部样式外部样式五、编码风格...

编程日记 2025/4/30 12:11:13

Tauri 跨平台开发指南及实战：用前端技术征服桌面应用（合集-万字长文）

厌倦了笨重的Electron应用？想要构建体积小、性能高、安全可靠的跨平台桌面应用？Tauri将是你的不二之选！本教程带你从入门到精通，掌握这个下一代桌面应用开发框架，并通过实战APK分析工具项目，将理论知识转化…...

编程日记 2025/4/30 12:10:09

深入解析 Linux 进程池：原理、实现与高并发优化

引言当你的服务器需要同时处理 10,000 个客户端请求时，传统的"来一个请求创建一个进程"模式会导致严重的性能瓶颈。此时，进程池（Process Pool） 便成为关键解决方案。它像一支训练有素的特种部队，通过预先创…...

编程日记 2025/4/30 12:09:03

[Python]非零基础的快速上手

从js转的python，没有从初学者阶段开始，主打一个快速上手能写再说. pycharm:一种编辑器数据类型基本数据类型:整型(整数)、浮点型、字符型、布尔型复杂数据类型:列表(数组)、集合区{1,2,3}、元组(1,3.4)字典{n’:2,b:1} 模板字符串输出模板字符串…...

编程日记 2025/4/30 12:09:00

《算法笔记》10.5小节——图算法专题-＞最小生成树问题 E: Jungle Roads

题目描述 The Head Elder of the tropical island of Lagrishan has a problem. A burst of foreign aid money was spent on extra roads between villages some years ago. But the jungle overtakes roads relentlessly, so the large road network is too expensive to mai…...

编程日记 2025/4/30 12:07:57

数据中心网络架构：高效规划与自动化设计实践

在数据中心网络架构规划设计中，面临如下难点： 设备数量庞大： 服务器、交换机等设备数量多，如何合理规划机柜布局和空间分配，避免资源浪费或密度超标，成为设计难点。线缆设计复杂： 海量线缆…...

编程日记 2025/4/30 12:07:53

Mysql存储引擎、锁机制

Mysql存储引擎 InnoDB（MySQL 5.5 及以后版本中的默认存储引擎） 事务支持：支持 ACID 事务，适合需要高可靠性的场景（如支付、订单）。锁机制：默认使用行级锁…...

编程日记 2025/4/30 12:06:51

UVA1537 Picnic Planning

目录题目算法标签: 最小生成树, k r u s k a l kruskal kruskal重构树, 树形 d p dp dp思路重构树代码题目 UVA1537 Picnic Planning 算法标签: 最小生成树, k r u s k a l kruskal kruskal重构树, 树形 d p dp dp 思路将 1 1 1号点设置为终点, 然后执行重构树计算度数…...

编程日记 2025/4/30 12:06:46

通过AWS Console连接服务器，简化运维过程

简单通过AWS Console连接您的Linux服务器本文作者: 封磊 Eclicktech SA | AWS Community Builder DevTool | AWS UGL | 亚马逊云科技云博主阿里云&InfoQ&CSDN签约作者文章目录简单通过AWS Console连接您的Linux服务器本文作者: 封磊Eclicktech SA | AWS Community …...

编程日记 2025/4/30 12:05:44

公交实时查询小程序功能点开发

线路查询：用户可输入公交线路号码，小程序实时显示该线路车辆位置与发车信息，能一键切换行驶方向，助用户依实时情况选合适候车站点。站点查询：输入车站信息，小程序呈现经过该站所有公交线路及公交信息&#…...

编程日记 2025/4/30 12:05:43

nginx配置集群服务器中的tcp负载均衡器

文章目录前言1. Ubuntu下nginx安装2. nginx的tcp负载配置前言假设一台机器支持两万的并发量，现在我们需要保证八万的并发量。首先想到的是升级服务器的配置，比如提高 CPU 执行频率，加大内存等提高机器的物理性能来解决此问题。但是单台机…...

编程日记 2025/5/5 16:58:52

Qt/C++开发监控GB28181系统/获取设备信息/设备配置参数/通道信息/设备状态

一、前言设备注册成功后，接下来要做的就是获取设备的信息，尤其是通道信息，根据国标协议，永远只有两个层级，一个是设备，然后就是设备下面多个通道，设备编码在整个系统中唯一，通道编…...

编程日记 2025/5/4 15:27:23

Linux系统基础：基础指令简介（网络概念部分）

简介：Linux 是一种开源的类 Unix 操作系统内核，由 Linus Torvalds 于 1991 年首次发布。经过多年发展，它已成为服务器、嵌入式设备和个人计算机领域的重要操作系统。网络基础概念初始协议简单来说，协议是一种约定&#xff0…...

编程日记 2025/4/30 12:04:38

labview项目文件架构

为了使 LabVIEW 项目更具可扩展性和易于维护，合理规划和设计项目文件结构是非常重要的。以下是一些基于行业经验和最佳实践的建议： 1. ### 文件夹层次划分将不同的功能模块分开存储在一个清晰的分层目录结构中是一个常见的做法。通常情况下&#xff…...

编程日记 2025/4/30 12:04:37

nuxt项目中引入并配置 iview

安装iview npm install iview --save注：想要加入其它的配置，可以在 nuxt.config.js 的 plugins 配置项中加入，同时在 plugins 文件夹下加入引入逻辑。在nuxt.config.js文件中写： {src: ~plugins/iview, ssr: true}同时新建 plugi…...

编程日记 2025/5/10 18:51:51

Origin绘图操作：点线图符号显示不全解决方法

一、问题说明在用origin绘制点线图时，图表刻度线处的点符号显示不完全，如图所示： 二、解决方法方法一：调整坐标轴刻度，使其能够显示全部数据点。方法二：有时为了图表美观，则不对坐标轴刻…...

编程日记 2025/4/30 12:02:25

【进程与线程】

文章目录一、实验目的二、实验内容与设计思想实验内容设计思路三、实验代码实现四、总结一、实验目的 1.深刻理解进程和线程的概念，掌握线程与进程在组成成分上的差别； 2.进一步认识并发执行的实质。二、实验内容与设计思想实验内容用pipe()创…...

编程日记 2025/4/30 12:02:24

项目实战-飞机大战【补档】

和项目实战-贪吃蛇大作战【补档】-CSDN博客一样，这也是一个我在大一和网友完成的项目的补档。Dont waste your youth—time flies. 目录 1.工具&环境 2.项目简介 3.需求文档 4.流程图 5.产品原型图 6.可行性分析 7.源代码 8.实战效果编辑 9.心得…...

编程日记 2025/4/30 12:02:23

算法基础学习|02归并排序——分治

一、思路 （1）确定分界点：mid(lr)/2 ——这里和快排不同 （2）递归排序（left right） （3）归并——合二为一时间复杂度nlogn 二、题目练习三、模板归并排序 …...

编程日记 2025/4/30 12:02:22

测试基础笔记第十六天

提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档文章目录一、UI自动化介绍1.认识UI自动化测试2.实施UI自动化测试前置条件3.UI自动化测试执行时机4.UI自动化测试核心作用和劣势二、认识Web自动化测试工具-Selenium021.Sel…...

编程日记 2025/4/30 12:02:21

Android项目中使用ComposeUI

首先确认项目环境kotlin版本，以下是本机的版本使用命令 ./gradlew -version 这里kotlin 版本是1.5.31 然后查看build.gradle sdk版本这里是32 属于低版本然后需要添加以下配置 buildFeatures {compose true}composeOptions {kotlinCompilerExtensionVersio…...

编程日记 2025/5/6 14:42:48

springboot中有关数据库信息转换的处理

现代项目一般都是前后端分离的，前端只负责展示数据，不负责对数据处理，所以所有数据处理工作都由后端进行比如在仿京东中的status，审核信息展示，数据库中是以0/1显示，但是前端需要以"审核/未审核&quo…...

编程日记 2025/4/30 12:01:14

HHsuite同源序列搜索数据库构建

HHsuite 可用的数据库格式简介 HHsuite 是用于蛋白质序列比对和同源性检测的工具套件，它使用特定的数据库格式以实现高效的数据存储和快速的检索。HHsuite 常用的数据库格式主要基于 FFINDEX（Flat-File Index），这是一种简单而高效的文件索引系统，它将数据文件（如蛋白质序…...

编程日记 2025/5/2 23:19:21

大模型推理：Qwen3 32B vLLM Docker本地部署

Qwen3基础知识此次Qwen3开源8个模型（MOE架构：Qwen3-235B-A22B、Qwen3-30B-A3B，Dense架构：Qwen3 0.6B/1.7B/4B/8B/14B/32B），新版本的Qwen3特性包括： 支持混合思维模式，即推理/非推…...

编程日记 2025/4/30 12:00:04

第十六届蓝桥杯 2025 C/C++B组第二轮省赛全部题解（未完结）

目录前言： 试题A：密密摆放试题B：脉冲强度之和试题C：25之和试题D：旗帜试题H：破解信息前言： 这是我后续刷到的第二轮省赛的题目，我自己也做了一下，和第一轮省赛…...

编程日记 2025/4/30 11:59:00

域名转移：什么是转移码/EPP码/授权码？

关于Dynadot Dynadot是通过ICANN认证的域名注册商，自2002年成立以来，服务于全球108个国家和地区的客户，为数以万计的客户提供简洁，优惠，安全的域名注册以及管理服务。 Dynadot平台操作教程索引（包括域名邮…...

编程日记 2025/4/30 11:58:59

Android 系统发展史

Android 1.0：2008年9月全球第一台安卓设备是 HTC Dream Google地图、YouTube、HTML浏览器、Gmail、即使消息、短信、彩信、日历等 Android Market（应用程序商店） Android 1.1：2009年2月（Petit Four 花色小蛋糕&am…...

编程日记 2025/5/14 13:57:22

Python中的defaultdict方法

文章目录核心特点基本语法常见使用场景1. 分组数据（默认值为列表）2. 计数（默认值为整数）3. 集合操作（默认值为集合）4. 嵌套字典注意事项与普通字典对比总结1. 键（Key）的类型2. 值&…...

编程日记 2025/4/30 11:55:46

Android启动应用时屏蔽RecyclerView滑动，延时后再允许滑动，Kotlin

Android启动应用时屏蔽RecyclerView滑动，延时后再允许滑动，Kotlin var bCanScrollVertically falselifecycleScope.launch(Dispatchers.Default) {repeatOnLifecycle(Lifecycle.State.CREATED) {Log.d(TAG, "Lifecycle.State.CREATED")delay(…...

编程日记 2025/4/30 11:55:45

2025运维工程师面试题1(答案在后一张)

一、逻辑思维能力考核： 问题1： 3个人去投宿，一晚30元三个人每人掏了10元凑够30元交给了老板后来老板说今天优惠只要25元就够了，拿出5元命令服务生退还给他们，服务生偷偷藏起了2元，然后，把剩下…...

编程日记 2025/5/16 7:08:45

在网页中使用【LaTeX 数学公式块】的完整步骤总结

以下是在网页中使用 LaTeX 数学公式块的完整步骤总结，记录如何让网页正确渲染 LaTeX 数学表达式（如 $H(X) -\sum p(x) \log p(x)$ 这样的公式）： ✅ 使用 LaTeX 数学公式块的完整步骤（以 KaTeX 为例） &am…...

编程日记 2025/5/12 23:04:03

新人销售如何找精准客户？

深入了解自身产品或服务。清晰掌握产品优势、应用场景和解决的问题，比如销售办公软件，要熟知其提升办公效率的具体功能，以此定位需求客户。利用社交媒体平台。像领英可完善资料，加入行业群组分享内容吸引潜在客户&#xff1…...

编程日记 2025/4/30 11:53:36

【Unity】使用Socket建立客户端和服务端并进行通信的例子

Socket服务端: using System; using System.Collections.Generic; using System.Net; using System.Net.Sockets; using System.Text; using System.Threading; public class SocketServer { public static Socket listenSocket;//监听Socket public static List<Socket>…...

编程日记 2025/4/30 11:53:33