首页 > 其他分享 >第十三节 小组学习

第十三节 小组学习

时间:2023-07-24 10:34:13浏览次数:40  
标签:le 第十三 更优 小组 long 学习 STR 操作 EXP

AT_abc180_d 题解

洛谷链接&Atcoder 链接

本篇题解为此题较简单做法较少码量,并且码风优良,请放心阅读。

题目简述

现有 \(STR\) 和 \(EXP\) 两个变量,初始化分别为 \(X\) 和 \(0\),可对变量 \(STR\) 做以下两种操作:

  1. 将 \(STR\) 乘 \(A\),并将 \(EXP\) 自加 \(1\)。

  2. 将 \(STR\) 加上 \(B\),并将 \(EXP\) 自加 \(1\)。

在 \(STR < Y\) 的情况下,求 \(EXP\) 的最大值。

思路

本蒟蒻读完题目后:“贪心!”

那么贪心该怎么贪?通过题意我们很容易想到,无论是执行第一个造作还是第二个操作对 \(EXP\) 的影响不变,故就需要我们衡量操作一或二的优势。

如执行操作一比执行操作二更优,则有:

\[STR \times A < STR + B \]

同时需满足:

\[STR \times A < Y \]

而自信提交的我结果就可想而知了,重新看了一遍题目,发现数据范围:\(1 \le X < Y \le 10^{18}\),\(2 \le A \le 10\),\(1 \le B \le 10^9\)。

那么 \(STR \times A\) 就有爆 \(\text{long long}\) 的可能,通过简单的不等式移项可变化为:

\[STR < Y / A \]

这样操作一比操作二更优的情况就解决了。又因为贪心思想,当操作二更优时可直接计算还可加多少 \(B\),直接加到 \(ans\) 里即可,因为此时再进行操作一必定超过 \(Y\) 或 \(STR \times A \ge STR + B\)。

经过以上分析,即可得到以下代码:

#include<iostream>
using namespace std;

long long x, y, a, b, ans = 0; // 开 long long

int main() {
    cin >> x >> y >> a >> b; // 输入
    while(x < y) {
        if(x < y / a && x * a < x + b) x *= a, ans ++; // 操作一比操作二更优,防止爆 long long 优化
        else break; // 操作二更优
    }
    ans += (y - x - 1) / b; // 计算操作二还可执行多少次
    cout << ans << endl; // 输出,换行好习惯
    return 0; 
}

提交记录

\(\text{The End!!!}\)

提交了 \(5\) 次,我崩溃了 qwq。。

标签:le,第十三,更优,小组,long,学习,STR,操作,EXP
From: https://www.cnblogs.com/So-noSlack/p/17576582.html

相关文章

  • Django学习笔记:第四章django的视图
    1.视图函数用于处理客户端的请求并生成响应数据。在属兔中使用函数处理请求的方式,被称为视图函数,也叫作FBV(FunctionBaseViews).一个简单的视图函数:在views.py里面配置fromdjango.httpimportHttpResponse#导入HttpResponse类defindex(request):#接收HttpRequest......
  • 深度学习——多模态
    什么是多模学习?我们平常使用的如图像识别,语音识别这种输入单个样本x(尽管样本可能有多个特征),但是输出对应的y值(结果)就是比较简单的单模态模型。即单个模型对输入的信息进行线性或者非线性的映射。多模态可以指的是通过多个模型的组合来让深度学习学习到更多不同的特征。如我们生......
  • spartan-6 ax309学习日记合集1
    一、环境安装配置两个开发环境ISE和modelsim,我安装的是ISE14.7(最新版,不再更新,由于Spartan-7及以上才可以使用vivado,故只能使用ISE)和modelsim10.1c(注意一定有c)二、流水灯程序编写学习因为我没有verilog基础,并且是初次接触FPGA开发板,没找到直接的教程,故开始打算先学一点verilog......
  • ChatGPT学习笔记1
    目录前言《原则一:明确具体的指令》《技巧1:使用区分符》《技巧2:结构化输出》《技巧3:条件是否满足》《技巧4:少样本提示》《原则二:给模型思考时间》《技巧1:给定步骤来补全》《技巧2:让模型先梳理再给结论》结语前言今天是我参加知识星球打卡的第七天了,感觉还是同时发来做自己的博客......
  • 高级系统架构师学习(一)系统工程与信息系统基础
    一、前言已经有一段时间没有写博客了,最近事情比较多,工作和家里的事情也比较忙,慢慢的就没写了,不写博客以后人就懒了,故今天下定决心,重新开始强迫自己提升,挤时间学习一些新的东西!这次的专题就不写应用技术了,写一写我学习高级系统架构师的一些心得吧。我是去年报名学习高级......
  • node的一部分知识(还在学习)
    node.js一,node最基础一,为什么要学node.js1.可以让每个人都访问到我们的网页2.为了学习vue二,node是什么一款应该程序,是一个软件,可以运行javascript三,node的作用1.开发服务器端应用2.开发工具类应用3.开发桌面端应用四,node的安装之前安装过二,命令的相关知识一,认识命令......
  • spring6 ioc aop 从入门到精通零基础进阶学习路线?
    当你已经掌握了Spring框架的基础知识以及IoC和AOP的核心概念后,可以进一步深化你的学习。以下是更详细的学习路线:1.IoC容器进阶:-学习如何自定义Bean的初始化和销毁方法,并了解Bean生命周期的各个阶段。-深入了解Spring的作用域(Scope)概念,如单例模式、原型模式、会话模式和请求模......
  • 学习MySQL,创建表,数据类型
    连接本地mysql语句mysql-hlocalhost-uroot-prootMySQL通用语法DDL数据库操作DDL:数据定义语言,用来定义数据库对象(数据库,表,字段)查询所有数据库showdatabases;创建数据库语法:createdatabase[ifnotexists]数据库名称[defaultcharset字符编码];createdat......
  • 无法注册程序集“D:\JAVA学习之路\jni4netTest\FanucDataCollectionAPI\FanucData
    无法注册程序集"D:\JAVA学习之路\jni4netTest\FanucDataCollectionAPI\FanucData"在Java开发中,我们经常需要与其他语言进行集成,以实现更复杂的功能或访问底层资源。JNI(JavaNativeInterface)是一种机制,允许Java代码调用本地代码(通常是C或C++编写的)。然而,在使用JNI时,有时会遇到无......
  • 初识机器学习及机器学习线性拟合的实现
    从最小二乘法到机器学习1,什么是机器学习?机器学习有下⾯⼏种定义:机器学习是⼀⻔⼈⼯智能的科学,该领域的主要研究对象是⼈⼯智能,特别是如何在经验学习中改善具体算法的性能。机器学习是对能通过经验⾃动改进的计算机算法的研究。机器学习是⽤数据或以往的经验,以此优化计算机程......