Educational Codeforces Round 158 [Rated for Div. 2]

A. Line Trip

还算比较简单的,不过本蒟蒻一开始以为是二分答案,二分写到一半突然想到油量直接取两个加油站之间的最大距离就好了。

最大距离能过,剩下必然都能过,要特判a[n]~x距离是两倍,因为x没有加油站,车还要掉头回去。

同时题目要求的范围是n到50就行了,如果开到2e7+5这种庞大的范围并且还用上了,可能就会被大佬hack掉(虽然题目用不到50,但是大佬的hack数据里面用了2e7,那你这道题就没分了)

本蒟蒻读题实在是太慢了,罗里吧嗦讲一堆直接干蒙了。还得多练英文

B. Chip and Ribbon

题目有点长,大意就是有个芯片在a[1],每次可以选择往后走一个(比如到a[2],但是a[n]不能到a[1],还要移动必须瞬移)或者瞬移到某一个位置上(可以原位瞬移)。并且芯片到过的位置都会+1。问你把一个0 0 0 0 0 0序列变成目标序列C最少要瞬移几次。

分析

假设有操作序列A,可以将0 0 0 0 0 0序列变成目标序列C。

那么显然有操作序列A(里面全部变成减法,操作顺序不变),可以将目标序列C变成0 0 0 0 0 0序列。

那么执行整个区间都减1,如果区间中某个数被减到0了,那就必然需要多瞬移一次。

如果是区间两端被减到0了,就缩小区间两端的指针。

可以发现我们执行的次数就是区间减1的次数包括计算中间为0的数量。

每次都去减C序列的最小值,然后每减一次就去更新一次C序列。

可以发现的是每次都减最小值复杂度为n,更新一次复杂度为n,n*n刚好爆了。

由于每次更新的时候都是区间修改,我们考虑差分维护C序列。

在原序列中执行次数是区间减1的次数和计算中间为0的数量。

原序列[10,1,5]   差分序列[10,-9,4,-5](-5是n+1的部分)

可以发现差分序列中一旦有负数,那么就是0出现的次数和需要执行区间减1的次数。

因为第一次执行区间减1是免费的,所以输出ans-1

AC代码

#include <bits/stdc++.h>
#define int long long
#define fr first
#define se second
#define endl '\n'
using namespace std;

const int N=2e5+5;
int n,a[N],ans;

void solve(){
    cin>>n;
    for(int i=1,t;i<=n;++i){
        cin>>t;
        a[i]+=t;
        a[i+1]-=t;
    }
    for(int i=1;i<=n+1;++i)
        if(a[i]<0)ans+=-a[i];
    cout<<ans-1<<endl;
}

void init(){
    for(int i=1;i<=n+1;++i)
        a[i]=0;
    ans=0;
}
signed main(){
    ios::sync_with_stdio(false),cin.tie(nullptr);
    int t;
    cin>>t;
    while(t--)solve(),init();
    return 0;
}

C. Add, Divide and Floor

B题可能是我的思路有问题,所以想的特别复杂,感觉B题比C题难的多的多

C题就简单了,你每次可以选择一个数x,让序列中所有的数都执行(ai+x)/2,问执行几次序列相等。

只看一眼肯定蒙,是不是很难的数学题啊

随便举个例子就能做这道题:0 10

假设我们选x=20,那么下一个序列就会变成:0/2+20/2和10/2+20/2

可以发现我们选x=20没有使序列的差更小,反而公共的加上了20/2。

所以我们每次选x都选序列中的最小值就行了,直到最大值变成最小值。

AC代码

#include <bits/stdc++.h>
#define int long long
#define fr first
#define se second
#define endl '\n'
using namespace std;

const int N=2e5+5;
int n,minn=LONG_LONG_MAX,maxx=LONG_LONG_MIN,cnt;

void solve(){
    cin>>n;
    for(int i=1,t;i<=n;++i){
        cin>>t;
        minn=min(minn,t);
        maxx=max(maxx,t);
    }

    while(maxx!=minn){
        maxx=(maxx+minn)/2;
        cnt++;
    }

    if(cnt==0){
        cout<<0<<endl;
    }else if(cnt<=n){
        cout<<cnt<<endl;
        while(cnt--)cout<<minn<<" ";
        cout<<endl;
    }else{
        cout<<cnt<<endl;
    }
}

void init(){
    minn=LONG_LONG_MAX;
    maxx=LONG_LONG_MIN;
    cnt=0;
}
signed main(){
    ios::sync_with_stdio(false),cin.tie(nullptr);
    int t;
    cin>>t;
    while(t--)solve(),init();
    return 0;
}

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

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

Spring Cache框架,实现了基于注解的缓存功能。

个人简介&#xff1a;Java领域新星创作者&#xff1b;阿里云技术博主、星级博主、专家博主&#xff1b;正在Java学习的路上摸爬滚打&#xff0c;记录学习的过程~ 个人主页&#xff1a;.29.的博客 学习社区&#xff1a;进去逛一逛~ Spring Cache框架 简介Spring Cache 环境准备S…

如何提高API性能

下图给出了提高API性能的5个常用技巧 分页 当结果很大时&#xff0c;这是一种常见的优化。结果会流回客户端以提高服务响应能力。 异步日志记录 同步日志记录每次调用都会处理磁盘&#xff0c;并且会降低系统速度。异步日志记录首先将日志发送到无锁缓冲区并立即返回。日志将…

【企业微信连接问题】

1、个人可以创建企业微信的企业账号么&#xff1f; 答&#xff1a;可以的&#xff0c;只是没法认证。不过基础的功能还是有的。 注册步骤&#xff1a;企业微信注册步骤 2、集简云链接企业微信&#xff0c;在授权之后&#xff0c;找不到集简云怎么办&#xff1f; 答&#xff1a…

git分支命名规范

https://www.cnblogs.com/wq-9/p/16968098.html

一. BEV感知算法介绍

目录 前言1. BEV感知算法的概念2. BEV感知算法数据形式3. BEV开源数据集介绍3.1 KITTI数据集3.2 nuScenes数据集 4. BEV感知方法分类4.1 纯点云方案4.2 纯视觉方案4.3 多模态方案 5. BEV感知算法的优劣6. BEV感知算法的应用介绍7. 课程框架介绍与配置总结下载链接参考 前言 自动…

电力感知边缘计算网关产品设计方案-网关软件设计方案

网关采用网络协议和软件技术在通信网络中针对工业协议、互联网通用协议进行分析和记录,提升工业控制系统环境的安全防护能力。A类和B类网关采用容器技术的软件架构,采用C/S架构软件客户端提供应用软件平台,为管理员提供功能丰富的图形管理控制界面。 因A类和B类网关在产品定…

ubuntu20.04打不开github网址的有效解决方案

问题描述&#xff1a;重装的ubuntu系统&#xff0c;chrome浏览器刚开始还能打开github网址&#xff0c;然后突然就打不开了&#xff0c;换网络也不行。 解决方案步骤 1&#xff0c;查询你的电脑IP对应的github网址信息 2&#xff0c;修改host文件&#xff0c;添加第1步查询到…

Spring Cloud Gateway 的简单介绍和基本使用

前言 本文主要对Spring Cloud Gateway进行简单的概念介绍&#xff0c;并通过多模块编程的方式进行一个简单的实操。 文章目录 前言1 什么是网关&#xff08;概念&#xff09;2 微服务中的网关2.1 问题12.2 问题2 3 网关作用4 Spring Cloud Gateway组成5 Spring Cloud Gateway基…

局域网的网络ip不稳定问题

在局域网的多个设备&#xff0c;互相通信时好时坏&#xff0c;不稳定。 遭遇过的情况如下&#xff1a; 用两个开发板&#xff1a;972开发板1和2&#xff0c;网口同时互相ping&#xff0c;出现1ping 2通--此时2ping 1不通&#xff0c;过段时间&#xff0c;1ping2不通--但2ping又…

美化wordpress复制文章内容弹出版权提示框的源码代码

通过SweetAlert美化的提示框 将下面代码添加到当前主题模板函数functions.php文件最后即可&#xff1a; function zm_copyright_tips() { echo <link rel"stylesheet" type"text/css" rel"external nofollow" target"_blank" href…

【新手解答2】深入探索 C 语言:一些常见概念的解析

C语言的相关问题解答 写在最前面问题1变量名是否有可能与变量重名&#xff1f;变量名和变量的关系变量名与变量是否会"重名"举例说明结论 变量则是一个地址不变&#xff0c;值时刻在变的“具体数字”变量的地址和值变量名与数据类型具体化示例结论 问题2关于你给我的…

电商项目高级篇-03 商品上架

商品上架 1、商品上架1.1、设计&#xff1a;宽表设计 1、商品上架 上架的商品才可以在网站展示。 上架的商品需要可以被检索。 1.1、设计&#xff1a;宽表设计 优点&#xff1a;方便检索 缺点&#xff1a;数据冗余 商品数据模型设计&#xff1a; PUT product {"mappi…

tidyverse数据特征学习

目录 特征缩放 1&#xff0c;标准化-scale 2&#xff0c;归一化-rescale 3&#xff0c;行规范化 4&#xff0c;数据平滑 特征变换 1. 非线性特征 2. 正态性变换 3. 连续变量离散 特征降维 特征缩放 不同数值型特征的数据量纲可能相差多个数量级&#xff0c;这对很多…

【Web】/proc利用相关例题wp

先贴一篇文章一起学习一下 [CTF]proc目录的应用 - CodeAntenna ①[HDCTF 2023]YamiYami 点击Read somethings直接跳转到了百度 从url中发现存在任意文件读取&#xff0c;因为不知道flag在哪&#xff0c;所以考虑读环境变量 payload: ?urlfile:///proc/1/environ 拿到fla…

短视频获客系统成功分享,与其开发流程与涉及到的技术

先来看实操成果&#xff0c;↑↑需要的同学可看我名字↖↖↖↖↖&#xff0c;或评论888无偿分享 一、短视频获客系统的开发流程 1. 需求分析&#xff1a;首先需要对目标用户进行深入了解&#xff0c;明确系统的功能和目标&#xff0c;制定详细的需求文档。 2. 系统设计&#…

Python教程:DataFrame列数据类型的转换

Pandas提供了多种数据类型转换方法。可以使用astype()函数来转换数据类型。例如&#xff0c;可以将字符串类型的列转换为整数类型的列&#xff1a; # Author : 小红牛 # 微信公众号&#xff1a;wdPython import pandas as pd# 创建包含字符串类型列的DataFrame df pd.DataFra…

VBA技术资料MF86:将PPT文件批量另存为PDF文件

我给VBA的定义&#xff1a;VBA是个人小型自动化处理的有效工具。利用好了&#xff0c;可以大大提高自己的工作效率&#xff0c;而且可以提高数据的准确度。我的教程一共九套&#xff0c;分为初级、中级、高级三大部分。是对VBA的系统讲解&#xff0c;从简单的入门&#xff0c;到…

YOLO目标检测——二维码检测数据集下载分享【含对应voc、coco和yolo三种格式标签】

实际项目应用&#xff1a;二维码识别、追踪与管理系统数据集说明&#xff1a;二维码检测数据集&#xff0c;真实场景的高质量图片数据&#xff0c;数据场景丰富标签说明&#xff1a;使用lableimg标注软件标注&#xff0c;标注框质量高&#xff0c;含voc(xml)、coco(json)和yolo…

快速解决Navicat连接数据库报错:10061

目录 问题原因&#xff1a; 错误提示&#xff1a; 解决方案&#xff1a; 问题1&#xff1a;如何进入指定目录&#xff1f; 问题2&#xff1a;若出现&#xff1a;“服务名无效” 将MySQL注册到win服务中 问题原因&#xff1a; mysql服务没有开启&#xff08;可能会在更新windows…

人工智能入门教学——AI代理(AI Agent)

目录 一、简介 二、特征 三、结构 四、工作流程 五、类型 六、应用 一、简介 AI代理 (Artificial Intelligence Agent)是指使用人工智能技术和算法来执行特定任务、解决问题或实现目标的程序或系统。这些代理可以是简单的程序&#xff0c;也可以是复杂的系统&#xff0c…