AtCoder Beginner Contest 385(A~F)题解

A - Equally

思路:由题可知最多只能分成三组,我们只需要判断是否三个数都相等,或者两个数相加等于另外一个数即可

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n;
string s;
int a,b,c;
signed main()
{cin>>a>>b>>c;if(a==b+c||b==a+c||c==a+b||(a==b&&b==c)){cout<<"Yes\n";}else{cout<<"No\n";}return 0;
}

 B - Santa Claus 1

思路:数据很小,直接暴力模拟即可

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,m,x,y;
char c[105][105];
int vis[105][105];
string t;
int ans=0;
signed main()
{cin>>n>>m>>x>>y;for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){cin>>c[i][j];}}cin>>t;if(vis[x][y]==0&&c[x][y]=='@'){vis[x][y]=1;ans++;}for(int i=0;i<t.size();i++){if(t[i]=='U'&&c[x-1][y]!='#'&&x-1>=1&&x-1<=n){x-=1;if(c[x][y]=='@'&&vis[x][y]==0){vis[x][y]=1;ans++;}}else if(t[i]=='D'&&c[x+1][y]!='#'&&x+1>=1&&x+1<=n){x+=1;if(c[x][y]=='@'&&vis[x][y]==0){vis[x][y]=1;ans++;}}else if(t[i]=='L'&&c[x][y-1]!='#'&&y-1>=1&&y-1<=m){y-=1;if(c[x][y]=='@'&&vis[x][y]==0){vis[x][y]=1;ans++;}}else if(t[i]=='R'&&c[x][y+1]!='#'&&y+1>=1&&y+1<=m){y+=1;if(c[x][y]=='@'&&vis[x][y]==0){vis[x][y]=1;ans++;}}}cout<<x<<" "<<y<<" "<<ans;return 0;
}

C - Illuminate Buildings

 思路:用map去存储每一个高度的大楼,然后去寻找每一个高度内的最长等差数列即可

#include <bits/stdc++.h>  
using namespace std;  
#define int long long  signed main() {  int n;  cin >> n;  vector<int> heights(n);  for (int i = 0; i < n; i++) {  cin >> heights[i];  }  unordered_map<int, vector<int>> index_map;  for (int i = 0; i < n; i++) {  index_map[heights[i]].push_back(i + 1);  }  int max_count = 1;  for (auto& entry : index_map) {  vector<int>& indices = entry.second;  int size = indices.size();  if (size <= 2) {  max_count = max(max_count, size);  continue;  }  unordered_set<int> index_set(indices.begin(), indices.end());  for (int i = 0; i < size; i++) {  for (int j = i + 1; j < size; j++) {  int d = indices[j] - indices[i];int count = 2;   int next_index = indices[j] + d;  while (index_set.count(next_index)) { count++;  next_index += d;  }  max_count = max(max_count, count);  }  }  }  cout << max_count << endl;  return 0;  
}

D - Santa Claus 2

 思路:这题和b题唯一的区别就是数据量很大,因此我们在处理这种问题可以考虑将其一行和一列存储起来,因此我们可以用一个map<int,set<int>>去存储,前面的键值表示的是当前行/列,后面的键值表示在当前行/列,set[i]位置上有一个房子,我们去用二分寻找区间,如果碰到房子,就将房子从这两个map的set里面弹出,然后个数+1

#include<bits/stdc++.h>
using namespace std;#define int long long
#define rep(i,n) for(int i=0;i<(int)(n);i++)
void solve()
{int n, m;int sx, sy;cin >> n >> m >> sx >> sy;map<int, set<int> > mx, my;rep(i, n) {int x, y;cin >> x >> y;mx[x].insert(y);my[y].insert(x);}map<char, int> dx, dy;dx['U'] = 0, dx['D'] = 0, dx['L'] = -1, dx['R'] = 1;dy['U'] = 1, dy['D'] = -1, dy['L'] = 0, dy['R'] = 0;int x = sx, y = sy;rep(tt, m) {char d;int c;cin >> d >> c;int nx = x + dx[d] * c;int ny = y + dy[d] * c;if (d == 'U' || d == 'D') {if (!mx.count(nx)) {x = nx;y = ny;continue;}int st = y, ed = ny;if (st > ed) swap(st, ed);auto l = mx[nx].lower_bound(st);auto r = mx[nx].upper_bound(ed);if (r == mx[nx].begin()) {x = nx;y = ny;continue;}vector<int> v;for (auto i = l; i != r; i++) {v.push_back(*i);}for (auto i : v) {mx[x].erase(i);if (my.count(i)) my[i].erase(nx);}}if (d == 'L' || d == 'R') {if (!my.count(ny)) {x = nx;y = ny;continue;}int st = x, ed = nx;if (st > ed) swap(st, ed);auto l = my[ny].lower_bound(st);auto r = my[ny].upper_bound(ed);if (r == my[ny].begin()) {x = nx;y = ny;continue;}vector<int> v;for (auto i = l; i != r; i++) {v.push_back(*i);}for (auto i : v) {my[y].erase(i);if (mx.count(i)) mx[i].erase(ny);}}x = nx;y = ny;}int sum = 0;for (auto i : mx) sum += i.second.size();cout << x << " " << y << " " << n - sum;
}signed main()
{solve();
}

 E - Snowflake Tree

这题其实并未涉及算法,更多的是思维,首先我们可以发现,根节点连接的点x上的连接的点都是相同的,因此我们的雪花树的深度最大为2(设我们的根节点深度为1),因此我们可以将每一个点的度统计出来,然后遍历每一个点,让每一个点都去当一次根节点,然后,用set去存储其子节点的度-1(表示孙子节点的度),然后从大到小排序,j*(当前节点的度+1),就是能够连接的最多的节点,然后去不断更新最大值即可

#include <bits/stdc++.h>  
using namespace std;  
#define int long long  
int n;  
vector<int> e[300005];  
signed main() {  cin >> n;  for(int i = 1; i < n; i++) {  int u, v;  cin >> u >> v;  e[u].push_back(v);  e[v].push_back(u);  }  int ans = 0;  for(int i = 1; i <= n; i++) {  vector<int> a;  for(int u : e[i]) {  a.push_back(e[u].size() - 1);  }  sort(a.rbegin(), a.rend());   for(int j = 0; j < a.size(); j++) {  ans = max(ans, (j + 1) * (a[j]+1) + 1);  }  }  cout << n - ans;  return 0;  
}

总体来说这场难度不高,f有一个卡精度问题,要用long double,后续更新,最重要的是e的思维 

F - Visible Buildings

 

思路:我们直接从斜率入手算出在y轴上的截距即可, 我们去取y轴上的截距,如果截距最大值都小于0,那么就输出-1,否则就输出截距的最大值

注意精度问题,用long double即可轻易ac掉这道题

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n;
long double x[200005];
long double h[200005];
signed main()
{cin>>n;for(int i=1;i<=n;i++){cin>>x[i]>>h[i];}long double ans=-LLONG_MAX;for(int i=2;i<=n;i++){long double xie=(h[i]-h[i-1])/(x[i]-x[i-1]);long double jie=h[i]-xie*x[i];ans=max(ans,jie);}if(ans<0){cout<<"-1";}else{cout<<fixed<<setprecision(10)<<ans<<"\n";}return 0;
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/495130.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

STM32串口第一次接收数据时第一个字节丢失的问题

解决方法&#xff1a;开启中断之前&#xff0c;先清除标志位【1】。 串口清除标志位&#xff1a; __HAL_UART_CLEAR_PEFLAG(&huart1); HAL_UART_Receive_IT(&huart1,&RxUart, 1); 定时器清除标志位&#xff1a; __HAL_TIM_CLEAR_FLAG(&htim3,TIM_FLAG_UPDATE);…

Unity3d 基于UGUI和VideoPlayer 实现一个多功能视频播放器功能(含源码)

前言 随着Unity3d引擎在数字沙盘、智慧工厂、数字孪生等场景的广泛应用&#xff0c;视频已成为系统程序中展示时&#xff0c;不可或缺的一部分。在 Unity3d 中&#xff0c;我们可以通过强大的 VideoPlayer 组件和灵活的 UGUI 系统&#xff0c;将视频播放功能无缝集成到用户界面…

第22天:信息收集-Web应用各语言框架安全组件联动系统数据特征人工分析识别项目

#知识点 1、信息收集-Web应用-开发框架-识别安全 2、信息收集-Web应用-安全组件-特征分析 一、ICO图标&#xff1a; 1、某个应用系统的标示&#xff0c;如若依系统有自己特点的图标&#xff1b;一旦该系统出问题&#xff0c;使用该系统的网站都会受到影响&#xff1b; 2、某个公…

我的 2024 年终总结

2024 年&#xff0c;我离开了待了两年的互联网公司&#xff0c;来到了一家聚焦教育机器人和激光切割机的公司&#xff0c;没错&#xff0c;是一家硬件公司&#xff0c;从未接触过的领域&#xff0c;但这还不是我今年最重要的里程碑事件 5 月份的时候&#xff0c;正式提出了离职…

acme ssl证书自动续签 nginx

参考 github 官方操作 &#xff0c;acme操作说明 说下我的操作 安装 acme.sh curl https://get.acme.sh | sh source ~/.bashrc 2.注册 acme.sh --register-account -m 123qq.com 如果你在配置 acme.sh 时选择了其他 CA&#xff08;如 Let’s Encrypt&#xff09;&#xff…

sentinel学习笔记6-限流降级(上)

本文属于sentinel学习笔记系列。网上看到吴就业老师的专栏&#xff0c;写的好值得推荐&#xff0c;我整理的有所删减&#xff0c;推荐看原文。 https://blog.csdn.net/baidu_28523317/category_10400605.html sentinel 实现限流降级、熔断降级、黑白名单限流降级、系统自适应…

简单了解函数递归

函数递归 一 了解函数递归二 深入理解函数递归的思想三 函数递归的优缺点 一 了解函数递归 首先&#xff0c;我们通过一个简单的代码来理解函数递归。 #include<stdio.h> int Func() {return Func(n1); } int main() {int n 5;Func(n);return 0; }这个就是函数递归&am…

QT的前景与互联网岗位发展

qt是用来干什么的 --》桌面应用开发&#xff08;做电脑的应用程序&#xff0c;面对客户端&#xff09;。 主要用于开发跨平台的应用程序和用户界面&#xff08;UI&#xff09;。它是一个全面的C库集合&#xff0c;提供了构建软件应用所需的各种工具和功能。 客户端开发的重…

重温设计模式--2、设计模式七大原则

文章目录 1、开闭原则&#xff08;Open - Closed Principle&#xff0c;OCP&#xff09;定义&#xff1a;示例&#xff1a;好处&#xff1a; 2、里氏替换原则&#xff08;Liskov Substitution Principle&#xff0c;LSP&#xff09;定义&#xff1a;示例&#xff1a;好处&#…

第十五章 C++ 数组

C 支持数组数据结构&#xff0c;它可以存储一个固定大小的相同类型元素的顺序集合。数组是用来存储一系列数据&#xff0c;但它往往被认为是一系列相同类型的变量。 数组的声明并不是声明一个个单独的变量&#xff0c;比如 number0、number1、...、number99&#xff0c;而是声…

企业数字化转型加速,现代 IT 如何用 Datadog 全面提升可观测性?

作为 Gartner 可观测平台魔力象限的领导者&#xff0c;Datadog 凭借全面的功能、直观的用户界面和强大的产品路线图赢得了全球企业的信任。 企业 IT 架构正变得日益复杂&#xff0c;从本地服务器到云端部署&#xff0c;从单体应用向微服务&#xff0c;还有容器、 Kubernetes 等…

渗透Vulnhub-DC-9靶机

本篇文章旨在为网络安全渗透测试行业靶机教学。通过阅读本文&#xff0c;读者将能够对渗透Vulnhub系列DC-6靶机有定的了解 一、信息收集阶段 DC-9靶场信息: DC-9靶场介绍&#xff1a; https://www.vulnhub.com/entry/dc-9,412/ DC-9靶场下载&#xff1a; https://download.vu…

[WASAPI]从Qt MultipleMedia来看WASAPI

[WASAPI] 从Qt MultipleMedia 来看WASAPI 最近在学习有关Windows上的音频驱动相关的知识&#xff0c;在正式开始说WASAPI之前&#xff0c;我想先说一说Qt的Multiple Media&#xff0c;为什么呢&#xff1f;因为Qt的MultipleMedia实际上是WASAPI的一层封装&#xff0c;它在是线…

Linux下编译安装Kokkos

本文记录在Linux下编译安装Kokkos的流程。 零、环境 操作系统Ubuntu 22.04.4 LTSVS Code1.92.1Git2.34.1GCC11.4.0CMake3.22.1oneAPI2024.2.1 一、安装依赖 二、编译安装 参考文献 Mills R T. PETSc/TAO Developments for Early Exascale Systems[J]. 2024.Josef R. A Stud…

HTMLCSS:惊!3D 折叠按钮

这段代码创建了一个具有 3D 效果和动画的按钮&#xff0c;按钮上有 SVG 图标和文本。按钮在鼠标悬停时会显示一个漂浮点动画&#xff0c;图标会消失并显示一个线条动画。这种效果适用于吸引用户注意并提供视觉反馈。按钮的折叠效果和背景渐变增加了页面的美观性。 演示效果 HT…

容器技术所涉及Linux内核关键技术

容器技术所涉及Linux内核关键技术 一、容器技术前世今生 1.1 1979年 — chroot 容器技术的概念可以追溯到1979年的UNIX chroot。它是一套“UNIX操作系统”系统&#xff0c;旨在将其root目录及其它子目录变更至文件系统内的新位置&#xff0c;且只接受特定进程的访问。这项功…

Git远程仓库的多人协作

目录 一.项目克隆 二.多人协作 1.创建林冲仓库 2.协作处理 3.处理冲突 三.分支推送协作 四.分支拉取协作 五.远程分支的删除 一.项目克隆 我们可以把远程项目克隆到本地形成一个本地的仓库 git clone https://github.com/txjava-teach/txjava-code.git //链接你自己的远…

Docker 部署 plumelog 最新版本 实现日志采集

1.配置plumelog.yml version: 3 services:plumelog:#此镜像是基于plumelog-3.5.3版本image: registry.cn-hangzhou.aliyuncs.com/k8s-xiyan/plumelog:3.5.3container_name: plumelogports:- "8891:8891"environment:plumelog.model: redisplumelog.queue.redis.redi…

Spring常见面试题总结

关于详细介绍&#xff0c;可以看我写的 ( Spring知识点) 这篇文章。 Spring 基础 什么是 Spring 框架? Spring 是一款开源的轻量级 Java 开发框架&#xff0c;旨在提高开发人员的开发效率以及系统的可维护性。 我们一般说 Spring 框架指的都是 Spring Framework&#xff0c…

Mac系统下 IDEA配置Maven本地仓库

1.为什么需要配置本地仓库&#xff1f; 在软件开发过程中&#xff0c;使用Maven工具进行依赖管理是常见的做法。Maven通过集中管理各种依赖库&#xff0c;能够帮助开发者在项目中轻松地引入所需的第三方库&#xff0c;并确保项目能够顺利构建和部署。然而&#xff0c;在使用Mav…