当前位置: 首页 > 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;只有经常会用到的东西才有可能真正记…...

电商客服外包怎么选|避坑指南[特殊字符]2026 商家必看

做电商绕不开客服外包&#xff0c;但低价陷阱、转包兼职、大促掉链、响应超时、售后甩锅真的太坑了&#xff01;今天整理一套不踩雷选型攻略&#xff0c;全是行业干货&#xff0c;新手也能直接抄作业&#x1f447; &#x1f6ab;先避坑&#xff1a;这些雷区千万别碰 超低价诱惑…...

KityMinder:可视化思维的协作引擎 | 高效工作者必备工具

KityMinder&#xff1a;可视化思维的协作引擎 | 高效工作者必备工具 【免费下载链接】kityminder 百度脑图 项目地址: https://gitcode.com/gh_mirrors/ki/kityminder 在信息爆炸的时代&#xff0c;如何将零散的想法系统化、复杂的项目结构化&#xff1f;作为一款开源免…...

别再只记*#*#284#*#*了!揭秘小米手机日志抓取的‘售后模式’:CIT工具(*#*#6484#*#*)的隐藏用法与解读

解锁小米手机CIT工具的隐藏潜能&#xff1a;从硬件诊断到日志深度解析 在智能手机高度普及的今天&#xff0c;用户对设备问题的自主排查需求日益增长。小米手机内置的CIT工具&#xff08;Customer Interface Test&#xff09;作为售后服务的核心诊断利器&#xff0c;其实蕴藏着…...

告别重复劳动:用快马AI智能生成OpenCode风格的高效工具函数

最近在开发一个需要大量表单验证的项目时&#xff0c;我发现每次都要重复写类似的验证逻辑&#xff0c;既浪费时间又容易出错。于是我开始寻找更高效的解决方案&#xff0c;最终在InsCode(快马)平台上找到了理想的工具。 需求分析 表单验证是每个Web项目都绕不开的基础功能。常…...

DeepSeek-Coder-V2本地化部署指南:构建你的专属AI编程助手

DeepSeek-Coder-V2本地化部署指南&#xff1a;构建你的专属AI编程助手 【免费下载链接】DeepSeek-Coder-V2 DeepSeek-Coder-V2: Breaking the Barrier of Closed-Source Models in Code Intelligence 项目地址: https://gitcode.com/GitHub_Trending/de/DeepSeek-Coder-V2 …...

给RV1126开发板写个‘WiFi管家’:一个脚本搞定连接、断开、状态查看与网络切换

RV1126开发板WiFi管家&#xff1a;打造智能网络管理工具链 在嵌入式开发领域&#xff0c;效率工具的价值往往被严重低估。想象一下这样的场景&#xff1a;当你需要在RV1126开发板上频繁切换测试环境、调试不同AP配置时&#xff0c;每次都要手动输入一长串命令&#xff0c;不仅…...

从分类影像到Fragstats输入:搞定景观格局分析前处理的完整避坑指南

景观格局分析前处理全流程&#xff1a;从分类影像到Fragstats输入的实战避坑指南 当你完成遥感影像分类&#xff0c;准备计算景观指数时&#xff0c;是否遇到过Fragstats报错"Invalid input format"&#xff1f;或是发现计算结果与预期不符却找不到原因&#xff1f;本…...

音乐版权检测新方案:CCMusic模型与MySQL数据库集成

音乐版权检测新方案&#xff1a;CCMusic模型与MySQL数据库集成 用AI技术解决音乐版权保护难题&#xff0c;让每一首作品都能得到应有的尊重 1. 引言&#xff1a;音乐版权保护的现实挑战 音乐创作者们经常面临这样的困境&#xff1a;自己的作品在各大平台被无授权使用&#xff…...

从‘发快递’到‘收快递’:手把手拆解RocketMQ 5.x中Producer Group的变迁与最佳实践

从‘发快递’到‘收快递’&#xff1a;手把手拆解RocketMQ 5.x中Producer Group的变迁与最佳实践 在消息中间件的世界里&#xff0c;RocketMQ一直以其高吞吐、低延迟的特性占据着重要地位。随着5.x版本的发布&#xff0c;一个看似微小的改动——生产者匿名化&#xff0c;却在实…...

告别Keil5刺眼白屏!保姆级教程教你配置VS Code同款暗黑主题(附3套配色方案)

Keil5暗黑主题终极改造指南&#xff1a;从护眼原理到深度定制 凌晨三点的实验室里&#xff0c;显示屏刺眼的白光让我的眼球开始灼烧般疼痛——这是许多嵌入式开发者共同的噩梦。Keil5作为单片机开发的主流工具&#xff0c;其默认的亮色主题在长时间编码时带来的视觉负担远超你的…...