23.8.15 杭电暑期多校9部分题解
1002 - Shortest path
题目大意
对于一个数 x x x,可以进行以下三种操作:
1.将 x x x 变成 2 ∗ x 2*x 2∗x
2.将 x x x 变成 3 ∗ x 3*x 3∗x
3.将 x x x 变成 x + 1 x+1 x+1
给定一个数 n n n,问最少操作几次才能将 1 1 1 变成 n n n
解题思路
最开始想法是建图跑最短路,然后发现空间显然不够,换思路
可以倒过来考虑,最优操作必然是找不大于本身的最大的 2 2 2 或 3 3 3 的倍数除以 2 2 2 或 3 3 3
很容易可以想到暴力搜索,但是会超时,考虑记忆化优化就可以了
code
#include <bits/stdc++.h>
using namespace std;
int t, ans;
long long n;
unordered_map <long long, int> v;
int dfs(long long x) {if (v.find(x) != v.end()) return v[x];return v[x] = min(dfs(x / 2) + x % 2, dfs(x / 3) + x % 3) + 1;
}
int main() {ios::sync_with_stdio(0);cin.tie(0);cin >> t;v[1] = 0;v[2] = v[3] = 1;while (t --) {cin >> n;cout << dfs(n) << "\n";}return 0;
}
1008 - Coins
题目大意
有 n n n 个人,每个人有 a i a_i ai 个硬币,每次操作可以选择任意 A , B A,\space B A, B 两个人,将 A A A 的 1 1 1 枚硬币给 B B B,如果这次操作后 A A A 没有硬币,则 A A A 退出游戏,问最后将所有硬币集中到一个人手上的期望操作次数
解题思路
先试试模拟,只有两个人的时候答案是 a 1 ∗ a 2 a_1*a_2 a1∗a2,再推三个人,四个人,发现结果刚好是 ∑ i = 1 n ∑ j = i + 1 n a i ∗ a j \sum_{i=1}^n\sum_{j=i+1}^na_i*a_j ∑i=1n∑j=i+1nai∗aj
听说题解讲了鞅的停时定理,咱也不会,但是其实不难发现每两个人之间的游戏其实是独立事件,也可以推出结论
注意卡亿下时间就好了
code
#include <bits/stdc++.h>
using namespace std;
int t, n, a;
__int128 ans, sum;
inline void write(__int128 x) {if (x > 9) write(x / 10);cout << (char)(x % 10 + '0');
}
signed main() {ios::sync_with_stdio(0);cin.tie(0);cin >> t;while (t --) {cin >> n; sum = ans = 0;for (int i = 1; i <= n; ++ i)cin >> a, ans += sum * a, sum += a;write(ans); cout << "\n";}return 0;
}
相关文章:
23.8.15 杭电暑期多校9部分题解
1002 - Shortest path 题目大意 对于一个数 x x x,可以进行以下三种操作: 1.将 x x x 变成 2 ∗ x 2*x 2∗x 2.将 x x x 变成 3 ∗ x 3*x 3∗x 3.将 x x x 变成 x 1 x1 x1 给定一个数 n n n,问最少操作几次才能将 1 1 1 变成…...
四个BY的区别 HIVE中
在Hive中,有四个BY比较:Order By、Sort By、Distribute By和Cluster By。 Order By是全局排序,只有一个Reducer。它可以按照升序(ASC)或降序(DESC)对结果进行排序。Order By子句通常用在SELECT语…...
计时函数与float32 float16 int8 数据转换
个人整理常用 部分来自 ncnn 计时函数 // window 平台 #include <windows.h>double get_current_time() {LARGE_INTEGER freq; // 频率LARGE_INTEGER pc; // 计数QueryPerformanceFrequency(&freq);QueryPerformanceCounter(&pc);return pc.QuadPart * 1000…...
自身免疫疾病诊断原料——博迈伦
自身免疫疾病是一类由免疫系统攻击正常组织和器官而引起的疾病。为了准确地诊断和监测自身免疫疾病,需要使用特定的诊断原料来进行实验室检测。这些诊断原料主要包括抗体试剂、抗原试剂和试剂盒等。 抗体试剂是用于检测和定量分析体内免疫系统产生的抗体的化学试剂。…...

cpu温度监测 Turbo Boost Switcher Pro for mac最新
Turbo Boost Switcher Pro是一款Mac电脑上的应用程序,旨在帮助用户控制和管理CPU的Turbo Boost功能。Turbo Boost是Intel处理器中的一项技术,可以在需要更高性能时自动提高处理器的频率。然而,这可能会导致电池消耗更快和温度升高。 以下是T…...
spring 请求 出现实体类大小写不一致 出现的问题
目录 1.问题背景 2.解决方法 但是会存在返回的既有大写也有小写的问题,需要在get方法也添加对应的注解 3.相关资料 1.问题背景 因数据库某字段存储的为json 格式,且数据库字段要求都有客户指定,因为该功能需要和其他项目进行对接。然后出现…...

zaabix实现对nginx监控
本文使用监控模板net.tcp.listen[port]实现监听端口 实验环境: 首先搭建好zabbix-server ,zabbix-agenthttps://mp.csdn.net/mp_blog/creation/editor/132622769?spm1001.2014.3001.9457 而后在zabbix-agent主机上下载一个nginx 登录zabbix网站创建主…...

基于AI视觉的表面缺陷检测设备优势显著,加速制造业数智化转型
作为生产制造过程中不可缺少的一步,表面缺陷检测广泛应用于工业领域,包括3C电子、芯片半导体、食品医药、木材等行业。但随着智能化进程加快,制造工厂生产线的质量检测压力加剧,传统人工表面缺陷检测已经无法满足当前社会较高的检…...

操作系统权限提升(二十六)之数据库提权-MySQL UDF提权
MySQL UDF提权 MySQL介绍 MySQL是最流行的开放源码SQL数据库管理系统,相对于Oracle,DB2等大型数据库系统,MySQL由于其开源性、易用性、稳定性等特点,受到个人使用者、中小型企业甚至一些大型企业的广泛欢迎,MySQL具有…...

基于 IntelliJ 的 IDE 将提供 Wayland 支持
导读对于使用 IntelliJ 开发环境的用户,JetBrains 一直致力于提供原生 Wayland 支持。 JetBrains 正在致力于为基于 IntelliJ 的 IDE 提供 Wayland 支持,以增强 Linux 桌面体验以及在 Windows Subsystem for Linux 下运行。 Wayland 支持功能尚未完成&…...

誉天在线项目~ElementPlus Tag标签用法
效果图 页面展现 <el-form-item label"课程标签"><el-tagv-for"tag in dynamicTags":key"tag"class"mx-1"closable:disable-transitions"false"close"handleClose(tag)"style"margin:5px;">…...

iText实战--Table、cell 和 page event
5.1 使用表和单元格事件装饰表 实现PdfPTableEvent 接口 实现PdfPCellEvent 接口 合并表格和单元格事件 5.2 基本构建块的事件 通用块(Chunk)功能 段落(Paragraph)事件 章节(Chapter)和 区域(…...

WampServer下载安装+cpolar内网穿透实现公网访问本地服务【内网穿透】
文章目录 前言1.WampServer下载安装2.WampServer启动3.安装cpolar内网穿透3.1 注册账号3.2 下载cpolar客户端3.3 登录cpolar web ui管理界面3.4 创建公网地址 4.固定公网地址访问 前言 Wamp 是一个 Windows系统下的 Apache PHP Mysql 集成安装环境,是一组常用来…...
Elasticsearch 入门 索引、分词器
term, match_phrase, match查询 参考 ElasticSearch match, match_phrase, term的区别 term是对输入不分词,进行全文索引查询。存储时是否启用分词器,会影响查询效果match_phase对输入分词,但要求查询时将每个term都搜到,且顺序…...
Android NDK 中有导出 sp智能指针吗?如果没有,可以用什么方法代替 android::sp 智能指针
Android NDK 中有导出 sp智能指针吗?如果没有,可以用什么方法代替 android::sp 智能指针 Author: Lycan Note: 以下问题解答通过大模型生成,主要用于个人学习和备忘,仅供参考,若有错误或者侵权,请联系我修…...

网络爬虫-----爬虫的分类及原理
目录 爬虫的分类 1.通用网络爬虫:搜索引擎的爬虫 2.聚焦网络爬虫:针对特定网页的爬虫 3.增量式网络爬虫 4.深层网络爬虫 通用爬虫与聚焦爬虫的原理 通用爬虫: 聚焦爬虫: 爬虫的分类 网络爬虫按照系统结构和实现技术&#…...

uniapp级联菜单地点区域使用label值,web端el-cascader绑定的value
效果图 一、uniapp uniapp级联菜单地点区域使用label值 1.ui使用 <uni-forms-item label="地址" name="userArea" required><view class="" style="height: 100%;display: flex;align-items: center;">...

合肥先进光源国家重大科技基础设施项目及配套工程启动会纪念
合肥先进光源国家重大科技基础设施项目及配套工程启动会纪念 卡西莫多 合肥长丰岗集里 肥鸭从此别泥塘 先平场地设围栏 进而工地筑基忙 光阴似箭指日争 源流汇智山水长 国器西北扩新地 家校又添新区园 重器托举有群力 大步穿梭两地间 科教兴邦大国策 技术盈身坦荡行…...
力扣第47天--- 第647题、第516题
# 力扣第47天— 第647题、第516题 文章目录 一、第647题--回文子串二、第516题--最长回文子序列 一、第647题–回文子串 逻辑梳理清楚了,就还行。没有想象中那么难。注意遍历顺序,i从大到小。 class Solution { public:int countSubstrings(string …...
dll文件找不到,微软官方地址
dll文件找不到,微软官方地址 文件地址dllMicrosoft Visual C 2008 Redistributable Package ATL 安全更新https://www.microsoft.com/zh-cn/download/details.aspx?id10430Visual C Redistributable for Visual Studio 2012 Update 4https://www.microsoft.com/zh…...

eNSP-Cloud(实现本地电脑与eNSP内设备之间通信)
说明: 想象一下,你正在用eNSP搭建一个虚拟的网络世界,里面有虚拟的路由器、交换机、电脑(PC)等等。这些设备都在你的电脑里面“运行”,它们之间可以互相通信,就像一个封闭的小王国。 但是&#…...

业务系统对接大模型的基础方案:架构设计与关键步骤
业务系统对接大模型:架构设计与关键步骤 在当今数字化转型的浪潮中,大语言模型(LLM)已成为企业提升业务效率和创新能力的关键技术之一。将大模型集成到业务系统中,不仅可以优化用户体验,还能为业务决策提供…...
React Native 开发环境搭建(全平台详解)
React Native 开发环境搭建(全平台详解) 在开始使用 React Native 开发移动应用之前,正确设置开发环境是至关重要的一步。本文将为你提供一份全面的指南,涵盖 macOS 和 Windows 平台的配置步骤,如何在 Android 和 iOS…...
MySQL 隔离级别:脏读、幻读及不可重复读的原理与示例
一、MySQL 隔离级别 MySQL 提供了四种隔离级别,用于控制事务之间的并发访问以及数据的可见性,不同隔离级别对脏读、幻读、不可重复读这几种并发数据问题有着不同的处理方式,具体如下: 隔离级别脏读不可重复读幻读性能特点及锁机制读未提交(READ UNCOMMITTED)允许出现允许…...
【HTTP三个基础问题】
面试官您好!HTTP是超文本传输协议,是互联网上客户端和服务器之间传输超文本数据(比如文字、图片、音频、视频等)的核心协议,当前互联网应用最广泛的版本是HTTP1.1,它基于经典的C/S模型,也就是客…...

QT: `long long` 类型转换为 `QString` 2025.6.5
在 Qt 中,将 long long 类型转换为 QString 可以通过以下两种常用方法实现: 方法 1:使用 QString::number() 直接调用 QString 的静态方法 number(),将数值转换为字符串: long long value 1234567890123456789LL; …...

企业如何增强终端安全?
在数字化转型加速的今天,企业的业务运行越来越依赖于终端设备。从员工的笔记本电脑、智能手机,到工厂里的物联网设备、智能传感器,这些终端构成了企业与外部世界连接的 “神经末梢”。然而,随着远程办公的常态化和设备接入的爆炸式…...

OPENCV形态学基础之二腐蚀
一.腐蚀的原理 (图1) 数学表达式:dst(x,y) erode(src(x,y)) min(x,y)src(xx,yy) 腐蚀也是图像形态学的基本功能之一,腐蚀跟膨胀属于反向操作,膨胀是把图像图像变大,而腐蚀就是把图像变小。腐蚀后的图像变小变暗淡。 腐蚀…...

用机器学习破解新能源领域的“弃风”难题
音乐发烧友深有体会,玩音乐的本质就是玩电网。火电声音偏暖,水电偏冷,风电偏空旷。至于太阳能发的电,则略显朦胧和单薄。 不知你是否有感觉,近两年家里的音响声音越来越冷,听起来越来越单薄? —…...

论文笔记——相干体技术在裂缝预测中的应用研究
目录 相关地震知识补充地震数据的认识地震几何属性 相干体算法定义基本原理第一代相干体技术:基于互相关的相干体技术(Correlation)第二代相干体技术:基于相似的相干体技术(Semblance)基于多道相似的相干体…...