The 2024 CCPC Online Contest (C I J三题思路)

写在前面

因为学弟已经问了几个题了,于是乎这场没有vp,准备直接开写了

题目

C. 种树(树形dp)

题解

只有两种情况,

一种是1-2-3,1是2的父亲,2是3的父亲

另一种是1-2-3,2同时是1和3的父亲

所以树形dp从底往上合并即可

I. 找行李(线性dp)

题解

J. 找最小(线性基 分治)

题解

将ai^bi插入线性基,然后从高位往低位贪心,如果能令max(f(a),f(b))变小,则交换

证明

学弟的这个做法并不同官方题解,一开始学弟找了一个反例,

后来发现suma末位是1、sumb末位是0,没法做到让基里不出现1

于是,开始思考这样的正确性,是数据水了还是这个做法是正确的

想了近乎一天,最终认为它是对的,给一个证明

因为对称性,也就是说,

如果我用一些操作使得最终suma≤sumb,

我一定可以反选所有操作使得suma≥sumb

这意味着a和b的所有位都是可以互换的,只是有些位会有联动

从高到低,忽略不可操作的位后,遇到a和b都是1的,都消成0

而遇到a和b一个0一个1时,第一次不管换没换都是其中一个1一个0,

不妨是a为1,那么第二次以后全令b为1令a为0,

这样的贪心最小是可得的,并且只要第二次以后没按这个操作来,就会违反不等式

跃迁佬的补充:

只关心sa^sb的最高1位那步的正确性(其他显然)
由于sa^sb可被线性基表示,这组线性基(R)全反选相当于sa,sb互换(无效果)
于是这步可以直接乱选,反正万一选错了R内的其他基也反选就是

所以在sa^sb的最高1位那步可以直接rand

代码

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

Meta AI 发布 Llama 3.2

Llama 3.2新闻 Meta公司在其Connect大会上宣布了Llama 3.2的发布,这是其首款能够理解图像和文本的旗舰视觉模型。Llama 3.2包含中型和小型两个版本(分别拥有11B与90B参数),以及更轻量化的纯文本模型(分别拥有1B与3B参数…

基于 RealSense D435相机实现手部姿态检测

基于 RealSense D435i相机进行手部姿态检测,其中采用 Mediapipe 进行手部检测,以下是详细步骤: Mediapipe 是一个由 Google开发的开源框架,专门用于构建多媒体处理管道,特别是计算机视觉和机器学习任务。它提供了一系列…

并查集 (Union-Find) :从基础到优化

并查集 (Union-Find) 并查集是一种树形数据结构,主要用于处理不相交集合(Disjoint Set)的合并和查询问题。它特别适用于解决有关连通性的问题,比如在图论中判断两点是否在同一个连通分量中。并查集可以高效地支持以下两种操作&am…

C++--C++11(下)

目录 7.5 完美转发 8 新的类功能 9 可变参数模板 10 lambda表达式 11 包装器 7.5 完美转发 模板中的 && 万能引用 void Fun(int &x){ cout << "左值引用" << endl; } void Fun(const int &x){ cout << "const 左值引用…

java开发jmeter采样器

目录 1.前言 2.新建一个springboot工程 2.1 引入相关依赖 2.2 编写核心代码 2.2.1 取样器代码 2.2.2 取样器界面 2.2.3 sdk接口封装 3.源码打包 3.1 将sdk源码和采样器源码打成jar包 3.2 拷贝引用包 4.配置jmeter脚本 4.1 选择自定义采样器 4.2 界面里面配置参数 1.…

小柴冲刺软考中级嵌入式系统设计师系列二、嵌入式系统硬件基础知识(3)嵌入式系统的存储体系

目录 感悟 一、存储系统的层次结构 存储器系统 二、内存管理单元 三、RAM和ROM的种类与选型 1、RAM RAM分类 2、ROM ROM分类 四、高速缓存Cache 五、其他存储设备 flechazohttps://www.zhihu.com/people/jiu_sheng 小柴冲刺软考中级嵌入式系统设计师系列总目录https…

CTF-SSH私钥泄露

CTF-SSH私钥泄露 一.信息探测--查看开放的服务--分析探测结果-- 探测大端口的信息 深入挖掘ssh信息![在这里插入图片描述](https://i-blog.csdnimg.cn/blog_migrate/6baf0b5de72d537c7093d3e2394d93cd.png#pic_center)解密ssh秘钥信息 工具&#xff1a;kali Linux 一.信息探测…

17.第二阶段x86游戏实战2-线程发包和明文包

免责声明&#xff1a;内容仅供学习参考&#xff0c;请合法利用知识&#xff0c;禁止进行违法犯罪活动&#xff01; 本次游戏没法给 内容参考于&#xff1a;微尘网络安全 本人写的内容纯属胡编乱造&#xff0c;全都是合成造假&#xff0c;仅仅只是为了娱乐&#xff0c;请不要…

Feign:服务挂了也不会走fallback

Feign 本质上是一个 HTTP 客户端&#xff0c;用于简化微服务之间的 HTTP 通信。它允许开发者通过定义接口和注解来声明式地编写 HTTP 客户端&#xff0c;而无需手动编写 HTTP 请求和响应处理的代码。 今天在模拟微服务A feign调用微服务B的时候&#xff0c;把微服务B关了&#…

C高级(Day22)

一、学习内容 shell指令 文件相关的指令 重定向 > >> echo :打印字符串 cat: 在终端打印文件的内容 链接文件 硬链接文件&#xff1a;文件的inode号是一样的。 查看文件inode号&#xff1a; ls -i 格式&#xff1a;ln 被链接的文件 创建硬链接文件 1 硬链接的文件…

计算机毕业设计 基于Python的医疗预约与诊断系统 Django+Vue 前后端分离 附源码 讲解 文档

&#x1f34a;作者&#xff1a;计算机编程-吉哥 &#x1f34a;简介&#xff1a;专业从事JavaWeb程序开发&#xff0c;微信小程序开发&#xff0c;定制化项目、 源码、代码讲解、文档撰写、ppt制作。做自己喜欢的事&#xff0c;生活就是快乐的。 &#x1f34a;心愿&#xff1a;点…

通用型pdf合并工具,分享7款简单易学的pdf处理软件,日常电脑必备!

日常学习和工作中&#xff0c;我们难免会遇到需要编辑pdf文件的情况。熟悉pdf格式文档的小伙伴都知道&#xff0c;pdf不易于编辑&#xff0c;需要借助专业的pdf编辑软件才能实现。现在pdf编辑、pdf转word、pdf合并、pdf拆分等功能都可以轻松实现。尽管如此&#xff0c;也有不少…

《动手学深度学习》笔记2.1——神经网络从基础→进阶 (层和块 - 自定义块)

目录 0. 前言 原书正文&#xff08;第五章&#xff09; 第五章 - 第一节 - 层和块 - 自定义块 1. Sequential() PyTorch高级API 2. MLP() 无传入参数 3. MySequential() 传入任意层(块) 4. FixedHiddenMLP() 无传入参数-固定隐藏层 5. NestMLP() 传入嵌套块-多次嵌套 …

Vue之axios请求

Vue之axios请求 axios请求, 是Vue前端框架非常重要的一部分, 今天我们就讲解axios请求, 到底有什么作用, 以及会告诉大家axios的常见用法。 axios请求, 是网页向后端发起请求, 后端吧数据给我们网页, 这是一个前后端交互的过程。当我们学会了axios, 我们可以实现前端和后端练…

【算法篇】二叉树类(2)(笔记)

目录 一、Leetcode 题目 1. 左叶子之和 &#xff08;1&#xff09;迭代法 &#xff08;2&#xff09;递归法 2. 找树左下角的值 &#xff08;1&#xff09;广度优先算法 &#xff08;2&#xff09;递归法 3. 路径总和 &#xff08;1&#xff09;递归法 &#xff08;2…

H. Sakurako‘s Test

H. Sakurakos Test 原题 本题通过前缀和和二分可以解决, 原理并不是很困难, 但是比较难想到 我们只需要对每一个 x, 二分求出中位数, 预处理好即可, 二分的检查通过求k倍的x可以在调和级数的时间内实现 代码 #include <bits/stdc.h> #define int long longusing name…

mysql索引 -- 聚簇索引,非聚簇索引,如何查看linux下的数据库文件,普通/辅助索引(回表查询)

目录 聚簇索引和非聚簇索引 聚簇索引 介绍 示例 查看当前的数据库数据目录 表文件 非聚簇索引 介绍 myisam 示例 普通(辅助)索引 引入(回表查询) mysql索引结构详细介绍 -- mysql索引 -- 索引的硬件理解(磁盘,磁盘与系统),软件理解(mysql,与系统io,buffer pool),索…

基于SpringBoot的新冠检测信息管理系统的设计与实现

文未可获取一份本项目的java源码和数据库参考。 国内外在该方向的研究现状及分析 新型冠状病毒肺炎疫情发生以来&#xff0c;中国政府采取积极的防控策略和措施&#xff0c;经过两个多月的不懈努力&#xff0c;有效控制了新发病例的増长&#xff0c;本地传播已经趋于完全控制…

【Java】六大设计原则和23种设计模式

目录 一、JAVA六大设计原则 二、JAVA23种设计模式 1. 创建型模式 2. 结构型模式 3. 行为型模式 三、设计原则与设计模式 1. 设计原则 2. 设计模式 四、单例模式 1. 饿汉式 2. 懒汉式 四、代理模式 1. 什么是代理模式 2. 为什么要用代理模式 3. 有哪几种代理模式 …

并发面试合集

1.创建线程的方式 区分线程和线程体的概念&#xff0c;线程体通俗点说就是任务。创建线程体的方式&#xff1a;像实现Runnable、Callable接口、继承Thread类、创建线程池等等&#xff0c;这些方式并没有真正创建出线程&#xff0c;严格来说&#xff0c;Java就只有一种方式可以…