AtCoder Beginner Contest 397(ABCDE)

目录

A - Thermometer

翻译:

思路:

实现:

B - Ticket Gate Log

翻译:

思路:

实现:

C - Variety Split Easy

翻译:

思路:

实现:

D - Cubes

翻译:

思路:

实现:


A - Thermometer

翻译:

        高桥测量了自己的体温,发现它是 X^0C

        体温分为以下几种:

  • 高于或等于 38.0^0C:"高烧"
  • 高于或等于 37.5^0C 和低于 38.0^0C:"发烧"
  • 低于 37.5^0C:"正常"

高桥的体温属于哪种分类?请根据输出部分以整数形式给出答案。

思路:

        先判断>=38.0再判断<37.5,都不对输出发烧。可以写快点。

实现:

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int MX = 1e5+10;void solve(){double n;cin>>n;if (n>=38){cout<<"1\n";}else if (n<37.5){cout<<"3\n";}else{cout<<"2\n";}
}int main(){// 关闭输入输出流同步ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);// 不使用科学计数法// cout<<fixed;// 中间填保留几位小数,不填默认// cout.precision();solve();return 0;
}



B - Ticket Gate Log

翻译:

        高桥汇总了检票口的使用记录。但是,他不小心删除了一些进出站记录。他正试图恢复被删除的记录。

        给你一个由 i 和 o 组成的字符串 S。我们想在 S 的任意位置插入 0 个或多个字符,这样得到的字符串就能满足以下条件:

  • 它的长度是偶数,每个奇数(第 1、第 3......个)字符都是 i,而每个偶数(第 2、第 4......个)字符都是 o。

        求需要插入的最少字符数。在此问题的约束条件下,可以证明通过插入适当数量的字符、 S 就能满足条件。

思路:

        字符串 io 是没问题,无需改变的。那么删除这些没问题的后剩下都是要在前后插入的字符了,统计一下剩下字符串长度即可。

实现:

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int MX = 1e5+10;void solve(){string s;cin>>s;int cnt = 0;for (int i=1;i<s.size();i++){if (s[i]=='o' && s[i-1]=='i') cnt++;}int n = s.size();cout<<n-2*cnt<<"\n";
}int main(){// 关闭输入输出流同步ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);// 不使用科学计数法// cout<<fixed;// 中间填保留几位小数,不填默认// cout.precision();solve();return 0;
}



C - Variety Split Easy

翻译:

        给你一个长度为 N 的整数序列:A=(A_1,A_2,...,A_N)

        当把 A 在一个位置分割成两个非空(连续)子数组时,求这两个子数组中不同整数的计数之和的最大值。

        更具体地说,对于整数 i,求以下两个值的最大和,使得 1≤i≤N-1:(A_1,A_2,...,A_i) 中不同整数的数量,和(A_{i+1},A_{i+2},...,A_N)中不同整数的数量。 

思路:

        前后缀分解,倒序遍历设立一个数组suffix,suffix[i]为[ i : n ]中A的不同整数数量。之后正序遍历求出以每个为分割点得到的和,比较下。

实现:

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int MX = 3e5+10;
int vis[MX];
void solve(){int n;cin>>n;vector<int> a(n+1);for (int i=1;i<=n;++i) cin>>a[i];vector<int> suffix(n+1);memset(vis,0,sizeof(vis));for (int cnt=0,i=n;i>=1;--i){vis[a[i]]++;if (vis[a[i]]==1) cnt++;suffix[i] = cnt;}int maxx = 0;memset(vis,0,sizeof(vis));for (int cnt=0,i=1;i<n;i++){vis[a[i]]++;if (vis[a[i]]==1) cnt++;maxx = max(maxx,cnt+suffix[i+1]);}cout<<maxx<<"\n";
}int main(){// 关闭输入输出流同步ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);// 不使用科学计数法// cout<<fixed;// 中间填保留几位小数,不填默认// cout.precision();solve();return 0;
}

D - Cubes

翻译:

        你被给予一个正整数N。决定是否存在一个正整数对(x,y)使得X^3-y^3=N。如果这个整数对,输出这样一个整数对(x,y)。

思路:

       N=x^3-y^3 \leq (y+1)^3-y^3=3y^2+3y+1如果y存在,可得y至少都为y<\sqrt\frac{N}{3}。而直接遍历明显不行。

        令d=x-y, 由N=x^3-y^3=(x-y)(x^2+xy+y^2)\geq (x-y)(x-y)^2=d^3可得d\leq \sqrt[3]N。那么如果(x,y)存在,则满足(d+y)^3-y^3=N=>d^3+3d^2y+3dy^2=N=>d^2+3dy+3y^2=\frac{N}{d}。(注意求幂使用pow返回的是浮点型存在精度问题)。且在d确定的情况下上式单调递增,可用二分判断在d确定下y是否存在。

        结论:先遍历d区间[1,\sqrt\frac{N}{3}),在内部二分搜索y是否有y满足d^2+3dy+3y^2=\frac{N}{d}。即可。时间复杂度为O(\sqrt[3]NlogN)。注意在此题中要注意整型越界问题。(纯纯数学题)

实现:

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
void solve(){ll n;cin>>n;for (ll d=1;d*d*d<=n;d++){if (n%d!=0) continue;ll l = 0,r = 900000010;while (l+1!=r){ll mid = (l+r)/2;if (d*d+3*d*mid+3*mid*mid>=n/d){r = mid;}else{l = mid;}}if (d*d+3*d*r+3*r*r==n/d){cout<<r+d<<" "<<r<<"\n";return;}}cout<<-1<<"\n";
}
int main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);solve();
}

E - Path Decomposition of a Tree

翻译:

        给你一颗有NK个点的树。点的编号为1,2,...,NK,并且第 i 条边(i=1,2,...,NK-1)连接点u_iv_i

        确定这棵树是否可以分解成 N 条路径,每条路径的长度为 K。更确切地说,确定是否存在满足以下条件的 N×K 矩阵 P:

  •  P_{1,1},...,P_{1,K},P_{2,1},...,P_{N,K}是一个由1,2,...,NK组成的排列。
  • 对于每个i=1,2,...,N和j=1,2,...,K-1它们间有边连接着点P_{i,j},P_{i,j+1}

思路:

        对于一个有NK个节点的树(以1为根节点),要求得到N个互不干扰大小为K的子树。

        如果一个子树的大小为k(当前树的根节点也算上)且子节点数量 <= 2。那么这颗子树为可用路径,删除它。

        如果子树大小 >k 或 子节点数量 >=3 或 子树大小 <k 且 子节点数量 >=2。那么答案就只能为No。对于上面子树的情况可以画图辅助思考下。  

实现:

#include<bits/stdc++.h>
using namespace std;
const int MX = 2e5+10;
int n,k;
vector<vector<int>> tree(MX);
int f = 1;
// 属于当前点的子树大小
int dfs(int now,int fa){int res = 1,cnt = 0;for (int& i:tree[now]){if (i==fa) continue;int tree_size = dfs(i,now);res += tree_size;if (tree_size) cnt++;}if (res>k || cnt>=3 || res<k && cnt>=2){f = 0;}if (res==k && cnt<=2){res = 0;}return res;
}
void solve(){cin>>n>>k;for (int x,y,i=1;i<n*k;i++){cin>>x>>y;tree[x].push_back(y);tree[y].push_back(x);}dfs(1,1);if (f){cout<<"Yes\n";}else{cout<<"No\n";}
}
int main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);solve();
}

  有建议可以评论,我会积极改进qwq。

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

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

相关文章

unserialize3 [有难度,序列化反序列化知识点]

详情: 地址:https://adworld.xctf.org.cn/challenges/list (unserialize3) 看到题目名称是反序列化 代码审计 <?php class xctf{// 定义一个公有属性$flag&#xff0c;通常CTF题目中需要获取该属性值public $flag 111; // 此处为示例值&#xff0c;实际可能为真实flag/*…

【Linux-传输层协议TCP】TCP协议段格式+确认应答+超时重传+连接管理机制(三次握手、四次挥手、理解TIME_WAIT + CLOSE_WAIT)

TCP协议 TCP全称为“传输控制协议&#xff08;Transmission Control Protocol&#xff09;”人如其名&#xff0c;要对数据的传输进行一个详细的控制。 1.TCP协议段格式 下面是TCP报头各个字段的表格形式&#xff1a; 字段名称字段大小描述源端口16位发送端TCP端口号。目的端…

《AI大模型趣味实战》No2 : 快速搭建一个漂亮的AI家庭网站-相册/时间线/日历/多用户/个性化配色(中)

快速搭建一个漂亮的AI家庭网站-相册/时间线/日历/多用户/个性化配色(中) 摘要 在上一篇文章中&#xff0c;我们介绍了如何搭建一个基础的家庭网站&#xff08;V1.0版本&#xff09;&#xff0c;包含了用户管理、相册管理、时间线和日历等功能。本文将继续深入&#xff0c;详细…

React(二):JSX语法解析+综合案例

事件绑定 this绑定方式 问题&#xff1a;在事件执行后&#xff0c;需获取当前类的对象中相关属性&#xff0c;此时需要this——当打印时&#xff0c;发现this为undefined,这又是为啥&#xff1f; 假设有一个btnClick函数&#xff0c;但它并不是我们主动调用的&#xff0c;而是…

One of the configured repositories failed (未知), and yum doesn‘t have enough cached data to continue

centos操作系统运行yum命令是出现如下报错&#xff1a; 解决办法&#xff1a; 由于CentOS的源地址内容已移除&#xff0c;CentOS 操作系统结束了生命周期&#xff0c;源地址内容已移除。 只需要将它的base源换成其他可用源&#xff0c;我这里将它换成了阿里的base源 备份原来…

【蓝图使用】绘制mesh顶点的法线

文章目录 绘制法线Normal准备工作UE5资源制作蓝图制作 参考 绘制法线Normal 参考[1]打算用蓝图走一遍渲染管线&#xff0c;还是可以的 准备工作 Blender制作一个三个顶点的模型 要不要材质无所谓&#xff0c;就一个三个顶点的mesh即可&#xff0c;参考[2] 找到一个法线贴…

202503执行jmeter压测数据库(ScyllaDB,redis,lindorm,Mysql)

一、Mysql 1 、 准备MySQL 连接内容 2 、 下载连接jar包 准备 mysql-connector-java-5.1.49.jar 放到 D:\apache-jmeter-5.6.3\lib\ext 目录下面; 3 、 启动jmeter ,配置脚本 添加线程组---》JDBC Connection Configuration---》JDBC Request---》查看结果树。 1)测…

f-string高级字符串格式化与string Template()

f-string 高级字符串格式化 f-string无法替换带有${name}的字符串&#xff0c;会保留\$ def test_fstring():"""f-string&#xff0c;高级字符串格式化的方式"""s "my name is {name}".format(name李白)print(s)# 无法替换$s &quo…

【Java 优选算法】分治-归并排序

欢迎关注个人主页&#xff1a;逸狼 创造不易&#xff0c;可以点点赞吗~ 如有错误&#xff0c;欢迎指出~ 数组分块如二叉树的前序遍历, 而归并排序就如二叉树的后序遍历 912. 排序数组 解法 使用归并算法 根据中间点划分区间, mid (right left ) / 2将左右区间排序合并两个有…

docker入门篇

使用docker可以很快部署相同的环境,这也是最快的环境构建,接下来就主要对docker中的基础内容进行讲解.Docker 是一个用于开发、交付和运行应用程序的开源平台&#xff0c;它可以让开发者将应用程序及其依赖打包到一个容器中&#xff0c;然后在任何环境中运行这个容器&#xff0…

Learning vtkjs之ContourLoopExtraction

过滤器 等高线轮廓提取 介绍 这个过滤器可以获取一个cut的相交的循环的线&#xff0c;目前这个案例cut是一个平面&#xff0c;应该是可以支持更多隐式公式 效果 可以设置这个平面的原点Origin 法线方向Normal&#xff0c;然后就可以求交了 核心代码 需要实现这个代码主要…

如何高效解决 Java 内存泄漏问题方法论

目录 一、系统化的诊断与优化方法论 二、获取内存快照&#xff1a;内存泄漏的第一步 &#xff08;一&#xff09;自动生成 Heap Dump &#xff08;二&#xff09;手动生成 Heap Dump 三、导入分析工具&#xff1a;MAT 和 JProfiler &#xff08;一&#xff09;MAT (Memor…

新手村:数据预处理-异常值检测方法

机器学习中异常值检测方法 一、前置条件 知识领域要求编程基础Python基础&#xff08;变量、循环、函数&#xff09;、Jupyter Notebook或PyCharm使用。统计学基础理解均值、中位数、标准差、四分位数、正态分布、Z-score等概念。机器学习基础熟悉监督/无监督学习、分类、聚类…

大模型-提示词调优

什么是提示词 提示词&#xff08;Prompt&#xff09;在大模型应用中扮演着关键角色&#xff0c;它是用户输入给模型的一段文本指令 。简单来说&#xff0c;就是我们向大模型提出问题、请求或描述任务时所使用的文字内容。例如&#xff0c;当我们想让模型写一篇关于春天的散文&a…

VS2022输入 scanf 报错解决方法

1.第一种解决办法&#xff08;不推荐&#xff09; •将 scanf 替换为 scanf_s •scanf_s 是VS提供的一个函数&#xff0c;scanf_s函数的使用和scanf是有区别的 •scanf_s 是VS提供的一个函数&#xff0c;其他的编译器可能不认识这个函数&#xff0c;那么我们所写的代码就存在跨…

鸿蒙开发-一多开发之媒体查询功能

在HarmonyOS中&#xff0c;使用ArkTS语法实现响应式布局的媒体查询是一个强大的功能&#xff0c;它允许开发者根据不同的设备特征&#xff08;如屏幕尺寸、屏幕方向等&#xff09;动态地调整UI布局和样式。以下是一个使用媒体查询实现响应式布局的实例&#xff1a; 1. 导入必要…

火语言RPA--列表项内容获取

【组件功能】&#xff1a;获取列表中某项数据内容 配置预览 配置说明 获取 获取数据方式 首项&#xff1a;列表第一条数据 末项&#xff1a;列表最后一条数据 随机项&#xff1a;随机获取列表中一条数据 指定索引项&#xff1a;根据索引获取列表对象中数据。 索引项目位置 …

基于Python+Flask+MySQL+HTML的爬取豆瓣电影top-250数据并进行可视化的数据可视化平台

FlaskMySQLHTML 项目采用前后端分离技术&#xff0c;包含完整的前端&#xff0c;以flask作为后端 Pyecharts、jieba进行前端图表展示 通过MySQL收集格列数据 通过Pyecharts制作数据图表 这是博主b站发布的详细讲解&#xff0c;感兴趣的可以去观看&#xff1a;【Python爬虫可…

解锁MySQL 8.0.14源码调试:Mac 11.6+CLion 2024.3.4实战指南

文章目录 解锁MySQL 8.0.41源码调试&#xff1a;Mac 11.6CLion 2024.3.4实战指南前期准备环境搭建详细步骤安装 CLion安装 CMake 3.30.5准备 MySQL 8.0.14 源码配置 CMake 选项构建 MySQL 项目 调试环境配置与验证配置 LLDB 调试器启动调试验证调试环境 总结与拓展 解锁MySQL 8…

81.HarmonyOS NEXT 状态管理与响应式编程:@Observed深度解析

温馨提示&#xff1a;本篇博客的详细代码已发布到 git : https://gitcode.com/nutpi/HarmonyosNext 可以下载运行哦&#xff01; HarmonyOS NEXT 状态管理与响应式编程&#xff1a;Observed深度解析 文章目录 HarmonyOS NEXT 状态管理与响应式编程&#xff1a;Observed深度解析…