题解: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
题解:ABC275 C-Counting Squares 题目 链接:Atcoder。 链接:洛谷。 难度 算法难度:入门。 思维难度:普及。 调码难度:普及。 综合评价:简单。 算法 dfs数论。 思路 由数学方法可严谨…...
加载已训练好的目标检测YOLOv8,v5,v3,v6模型,对数据集中某张图片中的object打上方框、标出类别,并将图片保存到本地
参考的教程: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
我们不难发现,几乎每一个应用程序都有一些相同的地方,比如说:标题栏、状态栏、边框、滚动条、工作区。还有的就是 菜单。 传统的菜单有大家熟悉的 File,Edit,Help等,点开之后,是下拉菜单&#…...
Shell脚本实现分库分表操作
目录 一,分库备份 二,分库操作 三,分库分表备份 四,备份还原 一,分库备份 #!/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个简单又极端的网络,在这个网络中完成1个交易的共识,需要26次通信,见下图所示。 换1个网络,这个网络是强连通图,见下图。 在这个网络中完成1次交易,流量见…...
聊聊这几年的科技风口
作者:朱金灿 来源:clever101的专栏 为什么大多数人学不会人工智能编程?>>> 数数这几年的科技风口:AR(包括什么MR、VR)、区块链(包括后来的什么web3)、元宇宙到现在的AI,下面逐一谈谈…...
【力扣每日一题】2023.7.30 环形链表2
题目: 示例: 分析: 这道题属于是那种知道解法就很简单,不知道解法就很难独立想出来的那种,我们只需要稍微记住这类题的固定解法就可以。 所以接下来我先说解法,再解释为什么解法可以解出来。 那么我们都…...
Flink状态的理解
Flink是一个带状态的数据处理系统;系统在处理数据的过程中,各算子所记录的状态会随着数据的处理而不断变化; 1. 状态 所谓状态State,一般指一个具体的 Task 的状态,即线程处理过程中需要保存的历史数据或历史累计数据…...
6.3.tensorRT高级(1)-yolov5模型导出、编译到推理(无封装)
目录 前言1. YOLOv5导出2. YOLOv5推理3. 补充知识总结 前言 杜老师推出的 tensorRT从零起步高性能部署 课程,之前有看过一遍,但是没有做笔记,很多东西也忘了。这次重新撸一遍,顺便记记笔记。 本次课程学习 tensorRT 高级-yolov5模…...
如何利用设备数字化平台推动精益制造?
人工智能驱动技术的不断发展,尤其是基于机器学习的预测分析工具的使用,为制造业带来了全新的效率和价值水平。一直以来,精益生产(也叫精益制造)在制造业中扮演着重要角色,而现在通过与工业 4.0的融合&#…...
使用Wps减小PDF文件的大小
第一步、打开左上角的文件 第二步、点击打印选项 第三步、点击打印按钮...
【深度学习】GPT-3
2020年5月,OpenAI在长达72页的论文《https://arxiv.org/pdf/2005.14165Language Models are Few-Shot Learners》中发布了GPT-3,共有1750亿参数量,需要700G的硬盘存储,(GPT-2有15亿个参数),它比GPT-2有了极大的改进。根…...
在登录界面中设置登录框、多选项和按钮(HTML和CSS)
登录框(Input框)的样式: /* 设置输入框的宽度和高度 */ input[type"text"], input[type"password"] {width: 200px;height: 30px; }/* 设置输入框的边框样式、颜色和圆角 */ input[type"text"], input[type&q…...
【语音识别】- 声学,词汇和语言模型
一、说明 语音识别是指计算机通过处理人类语言的音频信号,将其转换为可理解的文本形式的技术。也就是说,它可以将人类的口语语音转换为文本,以便计算机能够进一步处理和理解。它是自然语言处理技术的一部分,被广泛应用于语音识别助…...
【考研英语语法及长难句】小结
【 考场攻略汇总 】 考点汇总 考场攻略 #1 断开长难句只看谓语动词,不考虑非谓语动词先找从句,先看主句 考场攻略 #2 抓住谓语动词,抓住句子最核心的表述动作或内容通过定位谓语动词,找到复杂多变的主语通过谓语动词的数量&…...
C# 反射
反射的概念:C#通过类型(Type)来创建对象,调用对象中的方法,属性等信息;B超就是利用了反射原理将超声波打在人的肚子上,然后通过反射波进行体内器官的成员; 反射提供的类:…...
Pytorch(二)
一、分类任务 构建分类网络模型 必须继承nn.Module且在其构造函数中需调用nn.Module的构造函数无需写反向传播函数,nn.Module能够利用autograd自动实现反向传播Module中的可学习参数可以通过named_parameters()返回迭代器 from torch import nn import torch.nn.f…...
Python 使用http时间同步设置系统时间源码
Python方式实现使用http时间同步设置系统时间源码,系统环境是ubuntu 12.04、Python2.7版本。需要使用到time、os及httplib方法。 Python使用http时间同步设置系统时间,源码如下: #-*-coding:utf8 -*- import httplib as client import time…...
golang sync.singleflight 解决热点缓存穿透问题
在 go 的 sync 包中,有一个 singleflight 包,里面有一个 singleflight.go 文件,代码加注释,一共 200 行出头。内容包括以下几块儿: Group 结构体管理一组相关的函数调用工作,它包含一个互斥锁和一个 map,map 的 key 是…...
4、Linux驱动开发:设备-设备号设备号注册
目录 🍅点击这里查看所有博文 随着自己工作的进行,接触到的技术栈也越来越多。给我一个很直观的感受就是,某一项技术/经验在刚开始接触的时候都记得很清楚。往往过了几个月都会忘记的差不多了,只有经常会用到的东西才有可能真正记…...
(十)学生端搭建
本次旨在将之前的已完成的部分功能进行拼装到学生端,同时完善学生端的构建。本次工作主要包括: 1.学生端整体界面布局 2.模拟考场与部分个人画像流程的串联 3.整体学生端逻辑 一、学生端 在主界面可以选择自己的用户角色 选择学生则进入学生登录界面…...
k8s从入门到放弃之Ingress七层负载
k8s从入门到放弃之Ingress七层负载 在Kubernetes(简称K8s)中,Ingress是一个API对象,它允许你定义如何从集群外部访问集群内部的服务。Ingress可以提供负载均衡、SSL终结和基于名称的虚拟主机等功能。通过Ingress,你可…...
LeetCode - 394. 字符串解码
题目 394. 字符串解码 - 力扣(LeetCode) 思路 使用两个栈:一个存储重复次数,一个存储字符串 遍历输入字符串: 数字处理:遇到数字时,累积计算重复次数左括号处理:保存当前状态&a…...
全球首个30米分辨率湿地数据集(2000—2022)
数据简介 今天我们分享的数据是全球30米分辨率湿地数据集,包含8种湿地亚类,该数据以0.5X0.5的瓦片存储,我们整理了所有属于中国的瓦片名称与其对应省份,方便大家研究使用。 该数据集作为全球首个30米分辨率、覆盖2000–2022年时间…...
P3 QT项目----记事本(3.8)
3.8 记事本项目总结 项目源码 1.main.cpp #include "widget.h" #include <QApplication> int main(int argc, char *argv[]) {QApplication a(argc, argv);Widget w;w.show();return a.exec(); } 2.widget.cpp #include "widget.h" #include &q…...
MODBUS TCP转CANopen 技术赋能高效协同作业
在现代工业自动化领域,MODBUS TCP和CANopen两种通讯协议因其稳定性和高效性被广泛应用于各种设备和系统中。而随着科技的不断进步,这两种通讯协议也正在被逐步融合,形成了一种新型的通讯方式——开疆智能MODBUS TCP转CANopen网关KJ-TCPC-CANP…...
ElasticSearch搜索引擎之倒排索引及其底层算法
文章目录 一、搜索引擎1、什么是搜索引擎?2、搜索引擎的分类3、常用的搜索引擎4、搜索引擎的特点二、倒排索引1、简介2、为什么倒排索引不用B+树1.创建时间长,文件大。2.其次,树深,IO次数可怕。3.索引可能会失效。4.精准度差。三. 倒排索引四、算法1、Term Index的算法2、 …...
是否存在路径(FIFOBB算法)
题目描述 一个具有 n 个顶点e条边的无向图,该图顶点的编号依次为0到n-1且不存在顶点与自身相连的边。请使用FIFOBB算法编写程序,确定是否存在从顶点 source到顶点 destination的路径。 输入 第一行两个整数,分别表示n 和 e 的值(1…...
代理篇12|深入理解 Vite中的Proxy接口代理配置
在前端开发中,常常会遇到 跨域请求接口 的情况。为了解决这个问题,Vite 和 Webpack 都提供了 proxy 代理功能,用于将本地开发请求转发到后端服务器。 什么是代理(proxy)? 代理是在开发过程中,前端项目通过开发服务器,将指定的请求“转发”到真实的后端服务器,从而绕…...
【数据分析】R版IntelliGenes用于生物标志物发现的可解释机器学习
禁止商业或二改转载,仅供自学使用,侵权必究,如需截取部分内容请后台联系作者! 文章目录 介绍流程步骤1. 输入数据2. 特征选择3. 模型训练4. I-Genes 评分计算5. 输出结果 IntelliGenesR 安装包1. 特征选择2. 模型训练和评估3. I-Genes 评分计…...
