首页 > 其他分享 >SMOI-R1 赛后若干个月的总结

SMOI-R1 赛后若干个月的总结

时间:2024-09-28 21:46:50浏览次数:10  
标签:frac R1 sum 我们 SMOI 计算 节点 赛后 半边

打得非常好的一场比赛,所以才来写总结。

T1 「SMOI-R1」Queue

打表找规律题,太签到了,不讲。

T2 「SMOI-R1」Company

首先,如果要使得 \(x,y\) 的距离最后是尽可能远的,我们就要考虑一些满足最优解的性质。

不难想到一个结论:如果将初始时每一棵树缩成一个节点,那么最优解形成的新的树必然是一条链,且链的两端分别是初始的第 \(1,2\) 棵树。因为只有这样才能保证每一棵树都对答案产生了影响,否则说明必然存在一棵树是对 \(x,y\) 的距离毫无影响的。下文记 \(t_i\) 表示初始第 \(i\) 棵树。

由于初始每棵树都有根,且题中的连边方式是让叶子节点与树根连边,也就是说最终形成的树也一定是一个有根树。我们不妨来探讨一下这个树根:

  • 如果树根为 \(t_1\) 或者 \(t_2\),这就很显而易见了。假设现在树根为 \(t_1\),那么就说明树中最深的节点就是 \(t_2\)。我们记录一个当前节点下标 \(j\),初始时 \(j=x\),每次我们找到 \(j\) 所在的树 \(t_i\) 中距离 \(j\) 最远的一个叶子节点 \(j\prime\),接着让 \(j\) 移动到 \(j\prime\) 处,这个时候我们再考虑跳到另一个树的根上。总的来说,我们到达的树的先后顺序是 \(1\to (3\to 4\to\dots\to n)\to 2\),括号中的可以任意改变顺序。因此,对于所有 \(i>2\) 的 \(t_i\),\(j\) 在其中移动的距离一定是树的深度;对于 \(t_1\),\(j\) 移动的距离是 \(x\) 到某一个叶子节点的最远距离;对于 \(t_2\),\(j\) 移动的距离则是 \(y\) 的深度。计算此类情况的答案时,只需要计算它们的和就行了。

  • 如果树根不是 \(t_1\) 或者 \(t_2\),则说明 \(j\) 的移动方向是先往上,后往下。我们考虑枚举这个树根 \(t_k\)(\(k>2\))。由于 \(j\) 在除了 \(t_1,t_2,t_k\) 以外的所有树中经过的距离都是其深度,所以这些树的排放并不重要。而对于 \(t_1,t_2\),\(j\) 的其中移动的距离分别是 \(x,y\) 在树中的深度;对于 \(t_k\),由于它肯定是选择了两个叶子节点进行连边,所以 \(j\) 在其中移动的最大距离就是最远的两个叶子节点之间的距离。由于枚举的时间复杂度是 \(O(n)\),我们记 \(d_i\) 表示第 \(i\) 棵树的最大深度,然后计算 \(sum=\sum_{i=3}^n d_i\),每次计算除了 \(t_1,t_2,t_k\) 之外的树的总代价时,我们只需要用 \(sum\) 减去 \(d_k\) 就行了。

综上,对于 \(t_1,t_2\),我们要计算 \(x,y\) 在其中的深度以及 \(x,y\) 到达某个叶子节点的最长距离。对于 \(t_i\)(\(i>2\)),我们要计算 \(d_i\) 以及其中最远的两个叶子节点的距离。然后按照上述方法计算就行了。

但是要注意,树与树之间的连边也会计入答案。考虑到最终的树的组成形态,我们可以知道一共会添加 \(n-1\) 条边,并且它们都会计入 \(x\to y\) 的最长距离。

T3 「SMOI-R1」Game

首先有一个非常常规的思路:枚举每一个数,求出其作为最大值的区间个数。这道题也是如此。

如果最终的序列 \(a\) 长度够小,那么我们可以利用单调栈得出每一个数 \(a_i\) 向前和向后的第一个 \(>a_i\) 的数 \(a_{l_i}\) 和 \(a_{r_i}\),如果找不到则分别为 \(0,|a|+1\),那么 \(a_i\) 作为最大值的区间就有 \((i-l_i)(r_i-i)\) 个。

但是需要注意,有的区间是会被算重的,比如 \(a=\{1,2,1,2\}\),两个 \(2\) 分别计算得到的区间都包含 \([2,4],[1,4]\)。这个时候考虑更改 \(l_i\) 的定义为向前找到的第一个 \(≥a_i\) 的数的下标,如果找不到则为 \(|a|+1\),计算方式仍然是 \((i-l_i)(r_i-i)\)。这样就可以保证不会重复计算了,原因显然,因此把它当成一个 Trick 掌握就行了。

但是出题人非常可爱啊!这个 \(a\) 的长度可以达到 \(10^{15}\),不可能直接计算。但是 \(n\) 的范围倒是很合理。这就说明我们要找到 \(a\) 序列的计算规律。

我们将 \(a\) 视为 \(n\) 个形如 \(\{1,2,\dots,b_i-1,b_i\}\) 的子段前后拼接得到的序列,记 \(s_{i,j}\) 表示第 \(i\) 个子段中的第 \(j\) 个数在 \(a\) 中的下标。

先考虑 \(s_{i,b_i}\) 的代价该怎么计算。由于各个子段的单调性,我们可以知道其向前能够找到的第一个 \(≥b_i\) 的数的下标一定是 \(s_{j,b_j}\)(\(j<i\)),向后能够找到的第一个 \(> b_i\) 的数的下标一定是 \(s_{k,b_i+1}\)(\(i<k\),注意是 \(b_i\) 而不是 \(b_k\))。可以发现 \(b_j\) 是 \(b_i\) 向前第一个大于等于它的数,\(b_k\) 是 \(b_i\) 向后第一个大于它的数。可以通过这个结论,利用单调栈找到 \(j,k\)。我们找到这两个 \(j,k\) 记为 \(L(i),R(i)\)(如果不存在满足条件的 \(j\) 或 \(k\),则分别变为 \(0,n+1\)),则 \(s_{i,b_i}\) 的区间个数就是 \((s_{i,b_i}-s_{L(i),b_{L(i)}})(s_{R(i),b_{i}+1}-s_{i,b_i})\),可以利用 \(b_i\) 的前缀和解决。

我们记 \(sum_i=\sum _{j=1}^ib_j\),那么:

\[(s_{i,b_i}-s_{L(i),b_{L(i)}})(s_{R(i),b_{i}+1}-s_{i,b_i})=(sum_i-sum_{L(i)})(sum_{R(i)-1}-sum_i+1+[R(i)\leq n]) \]

每一个子段的顶点值我们就算完了,我们考虑将这种做法拓展到其它数上面。其实我们可以利用图像去思考:

我们知道对于每一个数,要去找前面和后面比自己大的,由于除了顶点以外,每个数的后面都有一个比自己大一的数,所以右侧比较好找。而对于左侧,我们结合上图去思考,不难发现最终形成的 \(a\) 序列就是若干个等腰直角三角形排在一起,那么每个数作为最大值的区间可以延展到的左端点一定是在 \(s_{k,b_k}\) 的位置。因此我们像之前那样用一个单调栈就行了。

但是对于每个数都用单调栈的话显然会寄。

我们可以找一下规律:

考虑对第 \(3\) 个子段的每个元素的答案进行统计,我们发现 \(IK\) 这一段对应过去的线段是 \(EF\),这说明 \(1\leq j\leq |IK|\) 的元素 \(s_{3,j}\) 可以向左延伸的最远点都是 \(F\),即 \(s_{2,b_2}\)。而 \(GL\) 对应过去是 \(CD\) 的一个子线段,这说明 \(|IK|<j\leq |GH|\) 的元素 \(s_{3,j}\) 向左延伸的最远点都是 \(s_{1,b_1}\)。这启示我们将每一个子段中的元素分成若干个子部分进行处理,并且要保证每个部分的 \(s_{i,j}\) 对应的左侧端点是相同的。

于是我们用单调栈去储存 \(b_i\),维护一个单调递减的子序列的下标。当我们要处理第 \(i\) 个子段时,我们就在栈中从后往前遍历,设当前遍历的元素为 \(p\),上一个遍历的元素是 \(q\),那么我们就将 \([s_{i,b_q+1},s_{i,b_p}]\) 的答案进行加和,下文令 \(t=sum_{i-1}-sum_p+b_q\),\(m=b_p-b_q\),则:

\[\begin{aligned} \sum _{j=b_q+1}^{b_p}j(s_{i,j}-s_{p,b_p})&=\sum _{j=b_q+1}^{b_p}j(sum_{i-1}-sum_p+j)\\ &=\sum _{j=1}^{m}(b_q+j)(sum_{i-1}-sum_p+b_q+j)\\ &=mb_qt+\dfrac{m(b_q+t)(m+1)}{2}+\dfrac{m(m+1)(2m+1)}{6} \end{aligned} \]

这样就可以 \(O(1)\) 计算这一段的答案之和了。

根据单调栈的性质,可以推断 \(n\) 个子段分成的子部分的个数和是 \(O(n)\) 级别的,可以跑过。

T4 「SMOI-R1」Apple

听网友说是个 CF 里面经典的 Trick,但是我不知道,不然我应该可以拿 \(10\) 块钱了。。。

不过不要慌,只要我现在会了就行。

对于这种进制上的子集问题,我们难以使用线段树这一类树形数据结构进行维护,所以我们可以考虑这样一个 Trick:对于一个 \(2^n\) 不可过但是 \(2^{\lfloor \frac{n}{2}\rfloor}\) 可过的题,我们把所有进制位分为前 \(\lfloor \frac{n}{2}\rfloor\) 位和后 \(n-\lfloor \frac{n}{2}\rfloor\) 位,然后对左半边的 \(2^{\lfloor \frac{n}{2}\rfloor}\) 个状态维护信息。

由此,我们设 \(sum_i\) 表示 \(i\) 的子集中,所有右半边与 \(i\) 相同的状态 \(j\) 的权值之和。那么对于每次的修改操作,如果是对状态 \(i\) 进行修改,则我们找到所有满足 \(i\subseteq j\) 且 \(i,j\) 右半边相同的状态 \(j\),然后对 \(sum_j\) 进行修改,由于右半边固定,我们只需要枚举左半边,这样每次的时间复杂度就是 \(O(2^{\lfloor \frac{n}{2}\rfloor})\)。对于每次的询问操作,我们就找到所有满足 \(j\subseteq i\) 且 \(i,j\) 左半边相同的状态 \(j\),然后对所有的 \(sum_j\) 进行加和,由于左半边固定,我们只需要枚举右半边的子集,这样每次的时间复杂度就是 \(O(2^{n-\lfloor \frac{n}{2}\rfloor})\)。

因此总时间复杂度就是 \(O(q2^{\frac{n}{2}})\)。

整体来说,感觉和 meet in the middle 的结构是差不多的,都是做到了把时间复杂度上的指数减少一半。

标签:frac,R1,sum,我们,SMOI,计算,节点,赛后,半边
From: https://www.cnblogs.com/SuporShoop/p/18438473

相关文章

  • Linux系统更换镜像源的方法 触觉智能Purple Pi R1双网口开发板演示
    本文适用于触觉智能的SigmaStar、瑞芯微、全志等所有芯片方案产品,搭载Linux系统(Ubuntu/Debian/Buildroot)均可。本次使用到的是触觉智能的PurplePiR1双网口开发板,搭载了SigmaStarSSD201/SSD202D芯片,类树莓派设计,双核A7,带WiFi功能,是嵌入式新人入门学习的高性价比开发板!什么......
  • MindFusion Pack for Java Swing 2024.R1 Crack
    MindFusionPackforJavaSwingJavaDiagramDiagrammingJavaSwingSchedulerSchedulingJavaSwingSpreadsheetSpreadsheetJavaSwingChartCharts&GaugesJavaSwingVirtualKeyboardVirtualKeyboardDiagramsIfyourJavaapplicationneedstodrawaflow......
  • 使用cifar100上训练的resnet18进行ood测试
    以cifar100作为闭集(closed-set)数据集,使用resnet18模型进行训练,然后在常见的开集(out-of-distribution)数据集上进行OOD检测。使用MSP(MaximumSoftmaxProbability)作为OOD检测的依据。开集噪声数据集使用gaussian,rademacher,blob,svhn四种类型。其中gaussian、rademacher......
  • NOIP2024模拟赛8 赛后总结
    前言真正的宝石纵使无光,亦能闪耀。今天的纯唐氏题目我居然不会做。考试的时候脑子跟生锈了一样。考虑到\(1,2\)题都太一眼了,这里就只总结一下最后两道题。多重集这道题目的重点是去观察对于\(a_x,b_x,a_y,b_y\)什么条件下\(a_x+a_y\)更小,以及什么条件下\(b_x+b_y\)......
  • 为什么iTunes提示找不到msvcr100.dll?彻底解决iTunes找不到msvcr100.dll的五种方法
    iTunes提示找不到msvcr100.dll的原因通常是由于电脑系统中缺失了这个必要的动态链接库文件(DLL)。msvcr100.dll是MicrosoftVisualC++2010RedistributablePackage的一部分,许多软件(包括iTunes)都依赖于它来运行。当这个文件丢失或损坏时,iTunes等程序就无法正常启动。以下是彻......
  • Marvelous Designer12 激活版下载及安装教程 (3D服装设计软件)
    下载地址: 破姐客栈,点击搜索Matlab即可免费下载解压文件,解压后点击执行选择安装路径点击【Install】安装中,大概需要2-5分钟,耐心等待…安装完成,取消下面勾选,点击【Finish】安装完成先不要启动,把补丁里面的文件覆盖程序安装位置即可完成激活。点击桌面图标启动运行......
  • 微信小程序基于uniapp的团购系统 a6zr1
    目录技术介绍具体实现截图微信开发者工具HBuilderX+uniappmysql数据库与主流编程语言java类核心代码部分展示登录的业务流程的顺序是:实现思路操作可行性技术可行性系统安全性数据完整性数据库设计系统实现系统测试详细视频演示源码获取技术介绍微信小程序指的是在微......
  • P9705 「TFOI R1」Unknown Graph题解
    思路题目给出了每个点的初度和入度,由于图是无重边无自环的有向图。要求满足限制的图有多少条边与建图方案。我们可以考虑使用网络流中的最大流。我们知道这是一道网络流后,题目的难点就转移到网络流的建模以及输出方案的办法。网络流的建模:题目所给的条件没有源点汇点并指出......
  • C++Builder11的静态连接问题的解决
    1、问题用C++Builder11写了一个小程序,想将所有的运行包放在一个exe文件中,方便分发。但就是找不到原来版本中的Static-LinkC++RuntimeLibrary选项。2、经历(1)选择菜单project-options-C++linker去掉LinkwithDynamicRTL右边的√去掉>LinkwiththeDelphiRuntimeLibra......
  • P11071 「QMSOI R1」 Distorted Fate
    介绍一种好想、在线、空间小、跑的还挺快的做法(?)先暂时不考虑修改,只考虑怎么快速求解询问。询问相当于区间内前缀按位或的和。根据按位或的性质,当区间内某个值在某一位下是\(1\),那么所有包含这个值的前缀的按位或结果在该位下都为\(1\)。考虑拆位,单独考虑每一位对答案的贡献,......