首页 > 其他分享 >【解题报告】P8477 「GLR-R3」春分

【解题报告】P8477 「GLR-R3」春分

时间:2024-09-30 09:50:11浏览次数:6  
标签:frac R3 P8477 板子 空白 污染 此时 GLR 我们

P8477 「GLR-R3」春分

题目看起来比较魔怔,考虑怎么搞一下。

首先,一个最简单的想法,每对溶液组都配一个板子,可以用 \(n^2\) 个板子解决,看得出来很不优啊,但是可以得到 Sub1 的分数。

节俭一点,我们如果把每个板子都拿出来一面用来对应一种溶液,此时就可以拼起来,只需要 \(2n\) 个板子解决,可以获得 Sub1,Sub2 的分数。

我们发现,上面的做法有一个很严重的缺陷:每个板子都有一面是没有接触过溶液的,我们考虑对这里进行优化。

考虑 \(X\) 没有接触过溶液的背面有什么用,我们把 \(X\) 平均分成两组,一组是 \(X_1 = \{x_1,x_2,\cdots,x_{\lfloor \frac{n}{2}\rfloor}\}\),一组是 \(X_2=\{x_{\lfloor \frac{n}{2}\rfloor+1},x_{\lfloor \frac{n}{2}\rfloor+2},\cdots,x_n\}\)。

我们现在为每个 \(X_1\) 的板子都和 \(Y\) 的分割板子去做实验,此时需要共 \(n+\lceil\frac{n}{2}\rceil\) 个

我们发现此时对于剩下的那一部分我们可以通过对板子进行组合来实现全部覆盖,那么总共需要的就是 \(\lceil\frac{n}{2}\rceil+ n\),通过计算我们可以发现正好多 \(1\),不能通过 Sub3。

因此我们需要对这个算法进行优化,发现其实我们对于奇数的情况完全不需要单独的一个板子,我们在完成翻转后的实验前,可以先让 \(x_n\) 和 \(Y\) 组实验,这样在最后可以减少一块额外的分隔板,因此可以优化到 \(\lfloor \frac{n}{2} \rfloor+n\),完全可以通过 Sub3。

考虑如何通过 Sub4,我们发现 Sub3 里用干净的板子去接触了不干净的板子导致干净的板子被污染了,如果能利用干净的板子就可以更优一点。

如果我们先把 \(X\) 和 \(Y\) 都平均分成三部分,然后先用 \(X_1\) 和 \(Y_{1\sim 3}\) 全部贴一次,此时我们会得到 \(\frac{n}{3} + n\) 个板子。

那么就会形成一个这样的图。

我们此时拿出 \(Y_3\) 翻转用没有染上的那面去染上灰色(灰色那里没有板子),此时我们在 \(Y_3\) 这里直接把 \(X_1\) 被污染的一面的和 \(Y_3\) 被污染的一面拼起来,此时就剩下没有被污染的两面,直接进行 \(X_2\) 与 \(Y\) 的配置即可。

在染上之后我们的 \(X_1\) 两面都被污染了,但是容易发现 \(Y_1\) 和 \(Y_2\) 依然没有被污染。

我们直接把 \(Y_2\) 翻面给 \(X_3\),这样我们就能得到一个左侧 \(X_3\) 右侧 \(Y_2\) 的板子。

我们把原本有一面没被污染的 \(Y_1\) 和 \(Y_3\) 拼过来就行,需要 \(\frac{4n}{3}\) 个板子,能过 Sub4。

看一下 Sub5,我们发现 Sub4 有一些非常不优的地方导致了还可以进一步优化,可以发现在 Sub4 中我们的思路是保证那么一大片全都是空白的才能拼。

但是我们发现事实上我们只需要一个空白板即可。

我们对左边分成 \(4\) 份,对右边分成 \(4\) 份,此时只对于左边的 \(X_1\) 配板,对于右边全部配板。

然后把 \(X_1\) 与 \(Y_{\{1\sim 4\}}\) 全部反应一次,我们把 \(X_1\) 反过来放 \(X_2\),中间隔一个空白板,直接和 \(Y_{\{i\sim 4\}}\) 全部反应一次。

然后用类似上一步的方法进行反应即可,需要 \(\frac{n}{4}+n+1\) 块,可以通过 Sub5。

此时我们发现一件事,诶我们这里 \(X\) 和 \(Y\) 分的总量都是相同的,我们对于左侧分成两部分 \(X_1,X_2\),对于右侧分为三个部分 \(Y_1,Y_2,Y_3\),其中对于 \(X_1\) 配板,同时 \(Y_1,Y_2\) 配板。

我们先对于 \(X_1\) 和 \(Y_1,Y_2\) 进行实验,在试验后我们加入一个空白隔板,让 \(Y_1\) 翻面,此时隔着空白隔板进行 \(Y_3\) 的实验,空白隔板的一面会和 \(Y_1\) 接触导致污染。

此时我们翻转 \(X_1\) 进行 \(X_2\) 的实验,把空白隔板被污染的一面给到 \(X_1\) 被翻转的一面,然后进行实验 \(X_2\) 与 \(Y\) 的实验,由于 \(Y_2\) 还有一面没有被污染,所以刚好能行。

可通过 Sub7。

标签:frac,R3,P8477,板子,空白,污染,此时,GLR,我们
From: https://www.cnblogs.com/Vsinger-LuoTianYi/p/18441246

相关文章

  • 微服务JSR303解析部署使用全流程
    目录1、什么是JSR303校验2、小试牛刀【2.1】添加依赖【2.2】添加application.yml配置文件修改端口【2.3】创建实体类User【2.4】创建控制器【2.5】创建启动类【注意】不必创建前端页面3、规范返回值格式:3.1添加ResultCode工具类3.2添加Result类3.3添加ValidationEx......
  • Arduino UNO R3自学笔记6 之 Arduino引脚(IO)功能介绍
    注意:学习和写作过程中,部分资料搜集于互联网,如有侵权请联系删除。前言:ArdunioUNOR3有很多引脚,接下来主要介绍它们都可以用做什么。从上图不难看出开发板引脚也不是有多少,分类来看也就以下种类型:                ●数字IO               ......
  • P8475 「GLR-R3」雨水 题解
    关于这道题目卡\(O(n\logn)\)但是放\(O(n^2)\)我也是很疑惑。我们发现,题目要求的是字典序最小的序列。但凡涉及了字典序最小,答案或多或少的都会带点贪心思想。那我们也来贪一贪。考虑当前枚举到第\(i\)个点,如果后面有比它更小的数,那显然把它们交换过来是更优的。如果有多......
  • P8474 「GLR-R3」立春 题解
    俗话说的好:“打表出奇迹”,所以我们这一题打表计算。其实确实可以打表来找规律。通过打表,我们可以获得如下的结果:1 12 33 214 3155 9765…… ……然后观察可得:\[1\times3=1\times(2^2-1)=3\]\[3\times7=3\times(2^3-1)=21\]\[21\times15=21\t......
  • Android 10.0 Launcher3禁止改变density等系统密度导致布局变化hotseat靠右边显示功能
    1.前言在10.0的系统rom定制化开发中,在进行launcher3的定制化功能中,在有些项目修改系统密度density的值,以后导致launcher3的布局变乱,hotseat布局成一行竖屏显示看的很不美观,接下来就看如何分析解析禁止density改变导致布局变动的功能分析2.Launcher3禁止改变density等系统密......
  • 如何修复user32.dll缺失问题:利用免费DLL修复工具解决电脑报错(全面)
    如何修复user32.dll缺失问题?小编在玩梦幻西游时空手游桌面版时,遇到如上图的系统提示“user32.dll文件丢失或损坏”的错误。这一错误可能导致应用程序无法正常运行,甚至影响系统的稳定性。我立马查询了相关资料,也询问了懂电脑的同时,他们都说有多种方法可以帮助我解决这一问题,包......
  • EtherCAT(以太网控制自动化技术)协议以其高带宽、低延迟特性,在工业自动化领域占据重要地
    一、MR30分布式IO模块概述EtherCAT(以太网控制自动化技术)协议以其高带宽、低延迟特性,在工业自动化领域占据重要地位。明达技术自主研发的MR30分布式IO模块作为EtherCAT协议的杰出应用,集成了多种输入输出功能,通过EtherCAT总线实现与主站的高效通信与控制,为纸巾包装行业带来革新。二、......
  • JEDEC DDR3 SRAM standard
    DDR=DoubleDataRate双倍速率,DDRSDRAM=双倍速率同步动态随机存储器,人们习惯称为DDR,其中,SDRAM是SynchronousDynamicRandomAccessMemory的缩写,即同步动态随机存取存储器。而DDRSDRAM是DoubleDataRateSDRAM的缩写,是双倍速率同步动态随机存储器的意思。DDR内存是在SDR......
  • opencascade Adaptor3d_Curve源码学习
    opencascadeAdaptor3d_Curve前言用于几何算法工作的3D曲线的根类。适配曲线是曲线提供的服务与使用该曲线的算法所需服务之间的接口。提供了两个派生具体类:GeomAdaptor_Curve,用于Geom包中的曲线Adaptor3d_CurveOnSurface,用于Geom包中表面上的曲线。用于评估BSpline曲线......
  • opencascade Adaptor3d_CurveOnSurface源码学习
    opencascadeAdaptor3d_CurveOnSurface前言用于连接由Geom包中表面上的曲线提供的服务,以及使用这条曲线的算法所要求的服务。该曲线被定义为一个二维曲线,来自Geom2d包,位于表面的参数空间中方法1默认构造函数Standard_EXPORTAdaptor3d_CurveOnSurface();2通过给定的表面......