当前位置: 首页 > 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…...

K8S认证|CKS题库+答案| 11. AppArmor

目录 11. AppArmor 免费获取并激活 CKA_v1.31_模拟系统 题目 开始操作&#xff1a; 1&#xff09;、切换集群 2&#xff09;、切换节点 3&#xff09;、切换到 apparmor 的目录 4&#xff09;、执行 apparmor 策略模块 5&#xff09;、修改 pod 文件 6&#xff09;、…...

SciencePlots——绘制论文中的图片

文章目录 安装一、风格二、1 资源 安装 # 安装最新版 pip install githttps://github.com/garrettj403/SciencePlots.git# 安装稳定版 pip install SciencePlots一、风格 简单好用的深度学习论文绘图专用工具包–Science Plot 二、 1 资源 论文绘图神器来了&#xff1a;一行…...

CMake基础:构建流程详解

目录 1.CMake构建过程的基本流程 2.CMake构建的具体步骤 2.1.创建构建目录 2.2.使用 CMake 生成构建文件 2.3.编译和构建 2.4.清理构建文件 2.5.重新配置和构建 3.跨平台构建示例 4.工具链与交叉编译 5.CMake构建后的项目结构解析 5.1.CMake构建后的目录结构 5.2.构…...

[ICLR 2022]How Much Can CLIP Benefit Vision-and-Language Tasks?

论文网址&#xff1a;pdf 英文是纯手打的&#xff01;论文原文的summarizing and paraphrasing。可能会出现难以避免的拼写错误和语法错误&#xff0c;若有发现欢迎评论指正&#xff01;文章偏向于笔记&#xff0c;谨慎食用 目录 1. 心得 2. 论文逐段精读 2.1. Abstract 2…...

Frozen-Flask :将 Flask 应用“冻结”为静态文件

Frozen-Flask 是一个用于将 Flask 应用“冻结”为静态文件的 Python 扩展。它的核心用途是&#xff1a;将一个 Flask Web 应用生成成纯静态 HTML 文件&#xff0c;从而可以部署到静态网站托管服务上&#xff0c;如 GitHub Pages、Netlify 或任何支持静态文件的网站服务器。 &am…...

微服务商城-商品微服务

数据表 CREATE TABLE product (id bigint(20) UNSIGNED NOT NULL AUTO_INCREMENT COMMENT 商品id,cateid smallint(6) UNSIGNED NOT NULL DEFAULT 0 COMMENT 类别Id,name varchar(100) NOT NULL DEFAULT COMMENT 商品名称,subtitle varchar(200) NOT NULL DEFAULT COMMENT 商…...

3403. 从盒子中找出字典序最大的字符串 I

3403. 从盒子中找出字典序最大的字符串 I 题目链接&#xff1a;3403. 从盒子中找出字典序最大的字符串 I 代码如下&#xff1a; class Solution { public:string answerString(string word, int numFriends) {if (numFriends 1) {return word;}string res;for (int i 0;i &…...

【HTTP三个基础问题】

面试官您好&#xff01;HTTP是超文本传输协议&#xff0c;是互联网上客户端和服务器之间传输超文本数据&#xff08;比如文字、图片、音频、视频等&#xff09;的核心协议&#xff0c;当前互联网应用最广泛的版本是HTTP1.1&#xff0c;它基于经典的C/S模型&#xff0c;也就是客…...

Swagger和OpenApi的前世今生

Swagger与OpenAPI的关系演进是API标准化进程中的重要篇章&#xff0c;二者共同塑造了现代RESTful API的开发范式。 本期就扒一扒其技术演进的关键节点与核心逻辑&#xff1a; &#x1f504; 一、起源与初创期&#xff1a;Swagger的诞生&#xff08;2010-2014&#xff09; 核心…...

Maven 概述、安装、配置、仓库、私服详解

目录 1、Maven 概述 1.1 Maven 的定义 1.2 Maven 解决的问题 1.3 Maven 的核心特性与优势 2、Maven 安装 2.1 下载 Maven 2.2 安装配置 Maven 2.3 测试安装 2.4 修改 Maven 本地仓库的默认路径 3、Maven 配置 3.1 配置本地仓库 3.2 配置 JDK 3.3 IDEA 配置本地 Ma…...