当前位置: 首页 > news >正文

23.8.15 杭电暑期多校9部分题解

1002 - Shortest path

题目大意

对于一个数 x x x,可以进行以下三种操作:

1.将 x x x 变成 2 ∗ x 2*x 2x

2.将 x x x 变成 3 ∗ x 3*x 3x

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 a1a2,再推三个人,四个人,发现结果刚好是 ∑ i = 1 n ∑ j = i + 1 n a i ∗ a j \sum_{i=1}^n\sum_{j=i+1}^na_i*a_j i=1nj=i+1naiaj

听说题解讲了鞅的停时定理,咱也不会,但是其实不难发现每两个人之间的游戏其实是独立事件,也可以推出结论

注意卡亿下时间就好了

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&#xff0c;可以进行以下三种操作&#xff1a; 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&#xff0c;问最少操作几次才能将 1 1 1 变成…...

四个BY的区别 HIVE中

在Hive中&#xff0c;有四个BY比较&#xff1a;Order By、Sort By、Distribute By和Cluster By。 Order By是全局排序&#xff0c;只有一个Reducer。它可以按照升序&#xff08;ASC&#xff09;或降序&#xff08;DESC&#xff09;对结果进行排序。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…...

自身免疫疾病诊断原料——博迈伦

自身免疫疾病是一类由免疫系统攻击正常组织和器官而引起的疾病。为了准确地诊断和监测自身免疫疾病&#xff0c;需要使用特定的诊断原料来进行实验室检测。这些诊断原料主要包括抗体试剂、抗原试剂和试剂盒等。 抗体试剂是用于检测和定量分析体内免疫系统产生的抗体的化学试剂。…...

cpu温度监测 Turbo Boost Switcher Pro for mac最新

Turbo Boost Switcher Pro是一款Mac电脑上的应用程序&#xff0c;旨在帮助用户控制和管理CPU的Turbo Boost功能。Turbo Boost是Intel处理器中的一项技术&#xff0c;可以在需要更高性能时自动提高处理器的频率。然而&#xff0c;这可能会导致电池消耗更快和温度升高。 以下是T…...

spring 请求 出现实体类大小写不一致 出现的问题

目录 1.问题背景 2.解决方法 但是会存在返回的既有大写也有小写的问题&#xff0c;需要在get方法也添加对应的注解 3.相关资料 1.问题背景 因数据库某字段存储的为json 格式&#xff0c;且数据库字段要求都有客户指定&#xff0c;因为该功能需要和其他项目进行对接。然后出现…...

zaabix实现对nginx监控

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

基于AI视觉的表面缺陷检测设备优势显著,加速制造业数智化转型

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

操作系统权限提升(二十六)之数据库提权-MySQL UDF提权

MySQL UDF提权 MySQL介绍 MySQL是最流行的开放源码SQL数据库管理系统&#xff0c;相对于Oracle&#xff0c;DB2等大型数据库系统&#xff0c;MySQL由于其开源性、易用性、稳定性等特点&#xff0c;受到个人使用者、中小型企业甚至一些大型企业的广泛欢迎&#xff0c;MySQL具有…...

基于 IntelliJ 的 IDE 将提供 Wayland 支持

导读对于使用 IntelliJ 开发环境的用户&#xff0c;JetBrains 一直致力于提供原生 Wayland 支持。 JetBrains 正在致力于为基于 IntelliJ 的 IDE 提供 Wayland 支持&#xff0c;以增强 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 基本构建块的事件 通用块&#xff08;Chunk&#xff09;功能 段落&#xff08;Paragraph&#xff09;事件 章节&#xff08;Chapter&#xff09;和 区域&#xff08;…...

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 集成安装环境&#xff0c;是一组常用来…...

Elasticsearch 入门 索引、分词器

term, match_phrase, match查询 参考 ElasticSearch match, match_phrase, term的区别 term是对输入不分词&#xff0c;进行全文索引查询。存储时是否启用分词器&#xff0c;会影响查询效果match_phase对输入分词&#xff0c;但要求查询时将每个term都搜到&#xff0c;且顺序…...

Android NDK 中有导出 sp智能指针吗?如果没有,可以用什么方法代替 android::sp 智能指针

Android NDK 中有导出 sp智能指针吗&#xff1f;如果没有&#xff0c;可以用什么方法代替 android::sp 智能指针 Author: Lycan Note: 以下问题解答通过大模型生成&#xff0c;主要用于个人学习和备忘&#xff0c;仅供参考&#xff0c;若有错误或者侵权&#xff0c;请联系我修…...

网络爬虫-----爬虫的分类及原理

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

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题–回文子串 ​ 逻辑梳理清楚了&#xff0c;就还行。没有想象中那么难。注意遍历顺序&#xff0c;i从大到小。 class Solution { public:int countSubstrings(string …...

dll文件找不到,微软官方地址

dll文件找不到&#xff0c;微软官方地址 文件地址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…...

线程与协程

1. 线程与协程 1.1. “函数调用级别”的切换、上下文切换 1. 函数调用级别的切换 “函数调用级别的切换”是指&#xff1a;像函数调用/返回一样轻量地完成任务切换。 举例说明&#xff1a; 当你在程序中写一个函数调用&#xff1a; funcA() 然后 funcA 执行完后返回&…...

学习STC51单片机31(芯片为STC89C52RCRC)OLED显示屏1

每日一言 生活的美好&#xff0c;总是藏在那些你咬牙坚持的日子里。 硬件&#xff1a;OLED 以后要用到OLED的时候找到这个文件 OLED的设备地址 SSD1306"SSD" 是品牌缩写&#xff0c;"1306" 是产品编号。 驱动 OLED 屏幕的 IIC 总线数据传输格式 示意图 …...

css的定位(position)详解:相对定位 绝对定位 固定定位

在 CSS 中&#xff0c;元素的定位通过 position 属性控制&#xff0c;共有 5 种定位模式&#xff1a;static&#xff08;静态定位&#xff09;、relative&#xff08;相对定位&#xff09;、absolute&#xff08;绝对定位&#xff09;、fixed&#xff08;固定定位&#xff09;和…...

SiFli 52把Imagie图片,Font字体资源放在指定位置,编译成指定img.bin和font.bin的问题

分区配置 (ptab.json) img 属性介绍&#xff1a; img 属性指定分区存放的 image 名称&#xff0c;指定的 image 名称必须是当前工程生成的 binary 。 如果 binary 有多个文件&#xff0c;则以 proj_name:binary_name 格式指定文件名&#xff0c; proj_name 为工程 名&…...

scikit-learn机器学习

# 同时添加如下代码, 这样每次环境(kernel)启动的时候只要运行下方代码即可: # Also add the following code, # so that every time the environment (kernel) starts, # just run the following code: import sys sys.path.append(/home/aistudio/external-libraries)机…...

并发编程 - go版

1.并发编程基础概念 进程和线程 A. 进程是程序在操作系统中的一次执行过程&#xff0c;系统进行资源分配和调度的一个独立单位。B. 线程是进程的一个执行实体,是CPU调度和分派的基本单位,它是比进程更小的能独立运行的基本单位。C.一个进程可以创建和撤销多个线程;同一个进程中…...

免费数学几何作图web平台

光锐软件免费数学工具&#xff0c;maths,数学制图&#xff0c;数学作图&#xff0c;几何作图&#xff0c;几何&#xff0c;AR开发,AR教育,增强现实,软件公司,XR,MR,VR,虚拟仿真,虚拟现实,混合现实,教育科技产品,职业模拟培训,高保真VR场景,结构互动课件,元宇宙http://xaglare.c…...

jmeter聚合报告中参数详解

sample、average、min、max、90%line、95%line,99%line、Error错误率、吞吐量Thoughput、KB/sec每秒传输的数据量 sample&#xff08;样本数&#xff09; 表示测试中发送的请求数量&#xff0c;即测试执行了多少次请求。 单位&#xff0c;以个或者次数表示。 示例&#xff1a;…...

算法打卡第18天

从中序与后序遍历序列构造二叉树 (力扣106题) 给定两个整数数组 inorder 和 postorder &#xff0c;其中 inorder 是二叉树的中序遍历&#xff0c; postorder 是同一棵树的后序遍历&#xff0c;请你构造并返回这颗 二叉树 。 示例 1: 输入&#xff1a;inorder [9,3,15,20,7…...

JDK 17 序列化是怎么回事

如何序列化&#xff1f;其实很简单&#xff0c;就是根据每个类型&#xff0c;用工厂类调用。逐个完成。 没什么漂亮的代码&#xff0c;只有有效、稳定的代码。 代码中调用toJson toJson 代码 mapper.writeValueAsString ObjectMapper DefaultSerializerProvider 一堆实…...