首页 > 其他分享 >JOISC 2022 飞机旅行

JOISC 2022 飞机旅行

时间:2024-11-07 17:57:53浏览次数:3  
标签:旅行 13 frac Alice 信息 JOISC 2022 大小 界点

一个基础做法

Alice 给点标号,Bob 可以传一个 \(2^{20}\) 的信息给 Alice,意味着 Alice 只能知道点的部分信息,然后根据部分信息得把剩余需要的信息传给 Bob。

考虑树分块,子树大小 \(\ge 7\) 的时候就划为一块,由于是二叉树(一开始以某个 \(\le 2\) 度点为根),那每个子树的大小在 \([7,13]\) 之间。

得到的块数为 \(c \le \lceil \frac n7 \rceil = 1429\),Bob 传两个点所属于哪两个块的信息,需要 \(\frac{c(c+1)}{2}=1021735 < 2^{20}\) 的信息,这是足够的。

Alice 把两个块的树形态传给 Bob(这可以双方先预处理所有的树形态,把每个树压缩成一个 ID),如果不在同一个块,还需要传两个块的界点是什么,两个界点之间的距离。

而 Alice 能传的信息个数是 \(\sum_{i=1}^{l} 2^i = 2^{l+1}-2\)。

优化

上述做法还有很大的优化空间!

优化 1

两人实际上不需要对 \([7,13]\) 的所有树都给一个 ID,只需要标号大小为 \(13\) 的树,Alice 传的时候,可以把更小的树加一些点变成大小 \(13\) 的树,然后只要传这个树的 ID。

进一步的,我们发现 Alice 并没有用满 \(2n+19\) 的标号空间,因为现在点的最大标号是 \(\lceil \frac n7 \rceil \times 13\),但我们可以用到 \(\lceil \frac n7 \rceil \times 14\)。

实际上,可以把大小为 \(13\) 的所有树再加一个点,也就是用若干个大小为 \(14\) 的树覆盖它们。

由于大小为 \(13\) 的树的形态只能是根节点连两个大小为 \(6\) 的儿子,我们通过 \(28\) 棵大小为 \(14\) 的树就覆盖了它们。

具体的,大小为 \(14\) 的树形态是:一边儿子大小为 \(6\),一边儿子大小为 \(7\)。只需要构造大小为 \(7\) 的树覆盖大小为 \(6\) 的树。

优化 2

我们真的关心整个树的形态吗?实际上,Alice 传 (树,界点) 的信息,Bob 只要知道界点到任意其他点的距离。

所以可以把 (树,界点) 的信息变成只传界点到其他点的 dis 数组。

优化 3

两个块的形态只可能是:

  • 祖先-后代,这样一个界点为根,一个界点不确定
  • 否则,两个界点都是根

在第一个情况下,“界点不确定”的那个界点一定只有 \(\le 1\) 的儿子,所以树上有 \(2\) 个儿子、且不是根的点可以不算。如果对于所有 \([7,13]\) 的树都可以不算,那这个点就可以不算进 dis 数组。

设界点为根的不同 dis 数组为 \(B_1\),界点不为根(且可能成为界点)的 dis 数组为 \(B_2\)。那这两部分只要传 \(B_1B_2 n+B_1^2 n\) 的信息。另外前面两个点在同一块内还有不同树个数的信息(只有 \(28\) 种)。

调整一下大小为 \(14\) 的树的顺序,可以得到 \(B_1=21,B_2=270\)。

优化 4

现在的做法已经能获得 \(99\) 分了。

如果我们枚举一个 \(\text{deg}\le 2\) 的点为根,最小化它到叶子节点的距离。我们发现这个距离是 \(\le \frac n2\) 的。

而在 祖先-后代 的情况里的 \(B_1B_2 n\) 个信息就可以优化成 \(B_1B_2 \frac n2\)。这样信息数量减半,可以获得 \(100\) 分。

标签:旅行,13,frac,Alice,信息,JOISC,2022,大小,界点
From: https://www.cnblogs.com/Rainbowsjy/p/18533466

相关文章

  • 中国各省环境污染指数(原始数据、结果)(2008-2022年)
    环境污染综合指数利用熵值法计算得出的综合性评估指标,旨在全面反映中国各省区环境污染的整体状况。该指数的数据主要来源于《中国统计年鉴》及各省的统计年鉴,通过收集并分析多项环境污染相关指标(废水排放总量、废气中二氧化硫排放量、一般工业固体废物产生量),运用熵值法这一客观......
  • 国标GB28181视频平台LiteGBS国标GB28181-2022平台,实现视频统一集中管理的方法
    LiteGBS是一个遵循国家标准GB28181协议的视频云服务平台,它能够同时处理多台设备的接入,包括网络摄像机、NVR等,都能便捷地整合到LiteGBS平台。在视频流分发能力上,国标GB28181公网直播LiteGBS能够向多个平台和终端提供RTSP、RTMP、FLV、HLS、WebRTC等多种视频流格式,满足用户在不同场......
  • # 20222326 2024-2025-1 《网络与系统攻防技术》实验四实验报告
    1.实验内容一、恶意代码文件类型标识、脱壳与字符串提取对提供的rada恶意代码样本,进行文件类型识别,脱壳与字符串提取,以获得rada恶意代码的编写作者,具体操作如下:(1)使用文件格式和类型识别工具,给出rada恶意代码样本的文件格式、运行平台和加壳工具;(2)使用超级巡警脱壳机等脱壳软件,......
  • WebAPI 初学 Visual Studio 2022,.NET 6.0(EF 代码迁移)
    按照一步一步来,您将能够创建api选择C#、Windows和WebApi 创建API后,单击绿色按钮运行应用程序,现在我们可以看到Demo项目正在运行。尽管所有结构都是自动创建的,以运行API。此版本已自动配置Swagger。这是演示API。VisualStudio会自动添加所需的库。现......
  • 20222317 2024-2025-1 《网络与系统攻防技术》实验四实验报告
    1.实验内容1.1恶意代码文件类型标识、脱壳与字符串提取对提供的rada恶意代码样本,进行文件类型识别,脱壳与字符串提取,以获得rada恶意代码的编写作者,具体操作如下:(1)使用文件格式和类型识别工具,给出rada恶意代码样本的文件格式、运行平台和加壳工具;(2)使用超级巡警脱壳机等脱壳软件,......
  • 20222307 2024-2025-1 《网络与系统攻防技术》实验四实验报告
    1.实验内容1.1本周所学IDApro、ProcessExplorer、peid、超级巡警等软件的学习与使用PE文件、蜜罐技术、tcpdump等专业知识的学习对于wireshark的抓包的深入分析1.2实验环境主机kali虚拟机安装winXP虚拟机实现xp与主机的ping通,参照:关闭xp虚拟机防火墙1.3实践内容......
  • SQL Server 2022 RTM Cumulative Update 15 发布下载 (累积更新包)
    SQLServer2022RTMCumulativeUpdate15发布下载(累积更新包)最新的累积更新(CU)下载,包含自SQLServer2022RTM发布以来的所有更新。请访问原文链接:https://sysin.org/blog/sql-server-2022/查看最新版。原创作品,转载请保留出处。作者主页:sysin.orgSQLServer202......
  • [NOIP2022] 比赛 随机排列 部分分
    看到最大值,考虑使用单调栈搞出\([la_i,ra_i],[lb_i,rb_i]\)表示这一段区间\(i\)是\(a,b\)的最大值。预处理是简单的。inlinevoidinit(){staticautof=[](inta[],intl[],intr[])->void{staticintstack[N],top;top=0,a[n+......
  • 20222323 2024-2025-1 《网络与系统攻防技术》实验四实验报告
    一、实验内容(一)恶意代码文件类型标识、脱壳与字符串提取对提供的rada恶意代码样本,进行文件类型识别,脱壳与字符串提取,以获得rada恶意代码的编写作者,具体操作如下:(1)使用文件格式和类型识别工具,给出rada恶意代码样本的文件格式、运行平台和加壳工具;(2)使用超级巡警脱壳机等脱壳软件,......
  • 249 旅行商
    /*http://oj.daimayuan.top/course/5/problem/249蜗蜗的世界里有n个城市,城市两两之间通过高速公路连接,从第i个城市走到第j个城市需要花费ai,j的时间。现在蜗蜗想从1号城市出发旅游,他想把每个城市都玩个遍,但又不想在一个城市玩两遍,玩完以后蜗蜗需要回到1......