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

题解:ABC275 C-Counting Squares

题解:ABC275 C-Counting Squares

·题目

链接:Atcoder。

链接:洛谷。

·难度

算法难度:入门。

思维难度:普及。

调码难度:普及。

综合评价:简单。

·算法

dfs+数论。

·思路

由数学方法可严谨证明,给定四边形其中三个顶点u、v、w,当满足以下条件时,可添加一个顶点other(o)使得四边形uvwo为正方形。

条件:u.x-v.x==v.y-w.y&&u.y-v.y==-(v.x-w.x)||-(u.x-v.x)==v.y-w.y&&u.y-v.y==v.x-w.x

可以通过dfs遍历三个顶点,判断他们能否构成正方形,若可以,就通过正方形边长相等的性质求出一个顶点(o),判断在坐标系中是否存在为“#”的该点,若存在,则该情况算数,否则忽略不计。

最终统计的个数应该除以8再输出,因为假设正方形四个顶点分别为ABCD,在dfs中会分别遍历它8次。(ABC、BCD、CDA、DAB、CBA、DCB、ADC、BAD)

·细节

输入字符串时如果不想以0项开始就用以下方式。

方式:scanf("%s",字符串名称+1);

·代码

今天不做过多解释,毕竟有些人只想看空白的代码,然后“借鉴(也就是copy)”一下。

#include<bits/stdc++.h>
using namespace std;
struct Place{int x,y;
};
Place a[20]={};
int ans=0;
char mp[20][20]={};
bool bl[20][20]={};
Place other(Place u,Place v,Place w);
bool be_square(Place u,Place v,Place w);
inline void dfs(int d);
int main(){for(int i=1;i<=9;i++){scanf("%s",mp[i]+1);}dfs(1);printf("%d\n",ans/8);return 0;
}
Place other(Place u,Place v,Place w){Place ret={};ret.x=w.x-v.x+u.x;ret.y=w.y-v.y+u.y;if(ret.x>=1&&ret.x<=9&&ret.y>=1&&ret.y<=9){return ret;}return {0,0};
}
bool be_square(Place u,Place v,Place w){if(u.x-v.x==v.y-w.y&&u.y-v.y==-(v.x-w.x)||-(u.x-v.x)==v.y-w.y&&u.y-v.y==v.x-w.x){return true;}return false;
}
inline void dfs(int d){if(d==4){if(be_square(a[1],a[2],a[3])==true){if(mp[other(a[1],a[2],a[3]).x][other(a[1],a[2],a[3]).y]=='#'){ans++;a[4]=other(a[1],a[2],a[3]);}}return;}for(int i=1;i<=9;i++){for(int j=1;j<=9;j++){if(bl[i][j]==false&&mp[i][j]=='#'){bl[i][j]=true;a[d].x=i;a[d].y=j;dfs(d+1);bl[i][j]=false;}}}
}

·注意

other函数的边界需要特判。

dfs要回溯。

数学推导不要推理错误。

相关文章:

题解:ABC275 C-Counting Squares

题解&#xff1a;ABC275 C-Counting Squares 题目 链接&#xff1a;Atcoder。 链接&#xff1a;洛谷。 难度 算法难度&#xff1a;入门。 思维难度&#xff1a;普及。 调码难度&#xff1a;普及。 综合评价&#xff1a;简单。 算法 dfs数论。 思路 由数学方法可严谨…...

加载已训练好的目标检测YOLOv8,v5,v3,v6模型,对数据集中某张图片中的object打上方框、标出类别,并将图片保存到本地

参考的教程&#xff1a;Python - Ultralytics YOLOv8 Docs 在与ultralytics代码同一层级下新建 predict.py 里面写下面的内容。运行即可 from ultralytics import YOLO from PIL import Image import cv2# 加载计划使用的模型 model YOLO("yolov8n.pt") # load a…...

《零基础入门学习Python》第073讲:GUI的终极选择:Tkinter10

我们不难发现&#xff0c;几乎每一个应用程序都有一些相同的地方&#xff0c;比如说&#xff1a;标题栏、状态栏、边框、滚动条、工作区。还有的就是 菜单。 传统的菜单有大家熟悉的 File&#xff0c;Edit&#xff0c;Help等&#xff0c;点开之后&#xff0c;是下拉菜单&#…...

Shell脚本实现分库分表操作

目录 一&#xff0c;分库备份 二&#xff0c;分库操作 三&#xff0c;分库分表备份 四&#xff0c;备份还原 一&#xff0c;分库备份 #!/bin/bash mysql_cmd-uroot -pzly666666 bak_path/backup/db [ -d ${bak_path} ] || mkdir -p ${bak_path}mysql ${mysql_cmd} -e show…...

区块链实验室(12) - 网络拓扑对PBFT共识流量的影响

区块链实验室(10) - 实例说明PBFT的共识过程说明了1个简单又极端的网络&#xff0c;在这个网络中完成1个交易的共识&#xff0c;需要26次通信&#xff0c;见下图所示。 换1个网络&#xff0c;这个网络是强连通图&#xff0c;见下图。 在这个网络中完成1次交易&#xff0c;流量见…...

聊聊这几年的科技风口

作者&#xff1a;朱金灿 来源&#xff1a;clever101的专栏 为什么大多数人学不会人工智能编程&#xff1f;>>> 数数这几年的科技风口&#xff1a;AR&#xff08;包括什么MR、VR&#xff09;、区块链(包括后来的什么web3)、元宇宙到现在的AI&#xff0c;下面逐一谈谈…...

【力扣每日一题】2023.7.30 环形链表2

题目&#xff1a; 示例&#xff1a; 分析&#xff1a; 这道题属于是那种知道解法就很简单&#xff0c;不知道解法就很难独立想出来的那种&#xff0c;我们只需要稍微记住这类题的固定解法就可以。 所以接下来我先说解法&#xff0c;再解释为什么解法可以解出来。 那么我们都…...

Flink状态的理解

Flink是一个带状态的数据处理系统&#xff1b;系统在处理数据的过程中&#xff0c;各算子所记录的状态会随着数据的处理而不断变化&#xff1b; 1. 状态 所谓状态State&#xff0c;一般指一个具体的 Task 的状态&#xff0c;即线程处理过程中需要保存的历史数据或历史累计数据…...

6.3.tensorRT高级(1)-yolov5模型导出、编译到推理(无封装)

目录 前言1. YOLOv5导出2. YOLOv5推理3. 补充知识总结 前言 杜老师推出的 tensorRT从零起步高性能部署 课程&#xff0c;之前有看过一遍&#xff0c;但是没有做笔记&#xff0c;很多东西也忘了。这次重新撸一遍&#xff0c;顺便记记笔记。 本次课程学习 tensorRT 高级-yolov5模…...

如何利用设备数字化平台推动精益制造?

人工智能驱动技术的不断发展&#xff0c;尤其是基于机器学习的预测分析工具的使用&#xff0c;为制造业带来了全新的效率和价值水平。一直以来&#xff0c;精益生产&#xff08;也叫精益制造&#xff09;在制造业中扮演着重要角色&#xff0c;而现在通过与工业 4.0的融合&#…...

使用Wps减小PDF文件的大小

第一步、打开左上角的文件 第二步、点击打印选项 第三步、点击打印按钮...

【深度学习】GPT-3

2020年5月&#xff0c;OpenAI在长达72页的论文《https://arxiv.org/pdf/2005.14165Language Models are Few-Shot Learners》中发布了GPT-3&#xff0c;共有1750亿参数量&#xff0c;需要700G的硬盘存储&#xff0c;(GPT-2有15亿个参数)&#xff0c;它比GPT-2有了极大的改进。根…...

在登录界面中设置登录框、多选项和按钮(HTML和CSS)

登录框&#xff08;Input框&#xff09;的样式&#xff1a; /* 设置输入框的宽度和高度 */ input[type"text"], input[type"password"] {width: 200px;height: 30px; }/* 设置输入框的边框样式、颜色和圆角 */ input[type"text"], input[type&q…...

【语音识别】- 声学,词汇和语言模型

一、说明 语音识别是指计算机通过处理人类语言的音频信号&#xff0c;将其转换为可理解的文本形式的技术。也就是说&#xff0c;它可以将人类的口语语音转换为文本&#xff0c;以便计算机能够进一步处理和理解。它是自然语言处理技术的一部分&#xff0c;被广泛应用于语音识别助…...

【考研英语语法及长难句】小结

【 考场攻略汇总 】 考点汇总 考场攻略 #1 断开长难句只看谓语动词&#xff0c;不考虑非谓语动词先找从句&#xff0c;先看主句 考场攻略 #2 抓住谓语动词&#xff0c;抓住句子最核心的表述动作或内容通过定位谓语动词&#xff0c;找到复杂多变的主语通过谓语动词的数量&…...

C# 反射

反射的概念&#xff1a;C#通过类型&#xff08;Type&#xff09;来创建对象&#xff0c;调用对象中的方法&#xff0c;属性等信息&#xff1b;B超就是利用了反射原理将超声波打在人的肚子上&#xff0c;然后通过反射波进行体内器官的成员&#xff1b; 反射提供的类&#xff1a;…...

Pytorch(二)

一、分类任务 构建分类网络模型 必须继承nn.Module且在其构造函数中需调用nn.Module的构造函数无需写反向传播函数&#xff0c;nn.Module能够利用autograd自动实现反向传播Module中的可学习参数可以通过named_parameters()返回迭代器 from torch import nn import torch.nn.f…...

Python 使用http时间同步设置系统时间源码

Python方式实现使用http时间同步设置系统时间源码&#xff0c;系统环境是ubuntu 12.04、Python2.7版本。需要使用到time、os及httplib方法。 Python使用http时间同步设置系统时间&#xff0c;源码如下&#xff1a; #-*-coding:utf8 -*- import httplib as client import time…...

golang sync.singleflight 解决热点缓存穿透问题

在 go 的 sync 包中&#xff0c;有一个 singleflight 包&#xff0c;里面有一个 singleflight.go 文件&#xff0c;代码加注释&#xff0c;一共 200 行出头。内容包括以下几块儿&#xff1a; Group 结构体管理一组相关的函数调用工作,它包含一个互斥锁和一个 map,map 的 key 是…...

4、Linux驱动开发:设备-设备号设备号注册

目录 &#x1f345;点击这里查看所有博文 随着自己工作的进行&#xff0c;接触到的技术栈也越来越多。给我一个很直观的感受就是&#xff0c;某一项技术/经验在刚开始接触的时候都记得很清楚。往往过了几个月都会忘记的差不多了&#xff0c;只有经常会用到的东西才有可能真正记…...

golang循环变量捕获问题​​

在 Go 语言中&#xff0c;当在循环中启动协程&#xff08;goroutine&#xff09;时&#xff0c;如果在协程闭包中直接引用循环变量&#xff0c;可能会遇到一个常见的陷阱 - ​​循环变量捕获问题​​。让我详细解释一下&#xff1a; 问题背景 看这个代码片段&#xff1a; fo…...

最新SpringBoot+SpringCloud+Nacos微服务框架分享

文章目录 前言一、服务规划二、架构核心1.cloud的pom2.gateway的异常handler3.gateway的filter4、admin的pom5、admin的登录核心 三、code-helper分享总结 前言 最近有个活蛮赶的&#xff0c;根据Excel列的需求预估的工时直接打骨折&#xff0c;不要问我为什么&#xff0c;主要…...

【JavaSE】绘图与事件入门学习笔记

-Java绘图坐标体系 坐标体系-介绍 坐标原点位于左上角&#xff0c;以像素为单位。 在Java坐标系中,第一个是x坐标,表示当前位置为水平方向&#xff0c;距离坐标原点x个像素;第二个是y坐标&#xff0c;表示当前位置为垂直方向&#xff0c;距离坐标原点y个像素。 坐标体系-像素 …...

select、poll、epoll 与 Reactor 模式

在高并发网络编程领域&#xff0c;高效处理大量连接和 I/O 事件是系统性能的关键。select、poll、epoll 作为 I/O 多路复用技术的代表&#xff0c;以及基于它们实现的 Reactor 模式&#xff0c;为开发者提供了强大的工具。本文将深入探讨这些技术的底层原理、优缺点。​ 一、I…...

ip子接口配置及删除

配置永久生效的子接口&#xff0c;2个IP 都可以登录你这一台服务器。重启不失效。 永久的 [应用] vi /etc/sysconfig/network-scripts/ifcfg-eth0修改文件内内容 TYPE"Ethernet" BOOTPROTO"none" NAME"eth0" DEVICE"eth0" ONBOOT&q…...

嵌入式学习笔记DAY33(网络编程——TCP)

一、网络架构 C/S &#xff08;client/server 客户端/服务器&#xff09;&#xff1a;由客户端和服务器端两个部分组成。客户端通常是用户使用的应用程序&#xff0c;负责提供用户界面和交互逻辑 &#xff0c;接收用户输入&#xff0c;向服务器发送请求&#xff0c;并展示服务…...

推荐 github 项目:GeminiImageApp(图片生成方向,可以做一定的素材)

推荐 github 项目:GeminiImageApp(图片生成方向&#xff0c;可以做一定的素材) 这个项目能干嘛? 使用 gemini 2.0 的 api 和 google 其他的 api 来做衍生处理 简化和优化了文生图和图生图的行为(我的最主要) 并且有一些目标检测和切割(我用不到) 视频和 imagefx 因为没 a…...

【JVM】Java虚拟机(二)——垃圾回收

目录 一、如何判断对象可以回收 &#xff08;一&#xff09;引用计数法 &#xff08;二&#xff09;可达性分析算法 二、垃圾回收算法 &#xff08;一&#xff09;标记清除 &#xff08;二&#xff09;标记整理 &#xff08;三&#xff09;复制 &#xff08;四&#xff…...

实战三:开发网页端界面完成黑白视频转为彩色视频

​一、需求描述 设计一个简单的视频上色应用&#xff0c;用户可以通过网页界面上传黑白视频&#xff0c;系统会自动将其转换为彩色视频。整个过程对用户来说非常简单直观&#xff0c;不需要了解技术细节。 效果图 ​二、实现思路 总体思路&#xff1a; 用户通过Gradio界面上…...

自然语言处理——文本分类

文本分类 传统机器学习方法文本表示向量空间模型 特征选择文档频率互信息信息增益&#xff08;IG&#xff09; 分类器设计贝叶斯理论&#xff1a;线性判别函数 文本分类性能评估P-R曲线ROC曲线 将文本文档或句子分类为预定义的类或类别&#xff0c; 有单标签多类别文本分类和多…...