首页 > 其他分享 >P10218 魔法手杖

P10218 魔法手杖

时间:2024-05-01 15:56:48浏览次数:33  
标签:左子 右子 那么 这位 魔法 mid P10218 son 手杖

感觉考场上做这题还是挺聪明的

答案显然满足二分的性质。考虑枚举答案mid,如果mid满足要求,那么就要满足如下条件:

\[\sum_{a_{i}\oplus x <mid} b^{i}<m \]

\[\forall i,a_{i}+ x >= mid \]

因为如果你这个\(a_{i}\)如果不能满足异或,那么肯定就需要加。
第一个条件即为:被定向加强的水晶在秘术后的魔力值大于等于 mid(对于未被定向加强的水晶,由于 \(a+x=(a\oplus x)+2(a\oplus x)≥(a\oplus x)≥mid\),其也满足该不等式。
第二个式子可以变成\(min\{ a_{i} \}+x>=mid\)将这个作为二分下界即可。然后对于这里,我们要搞的问题就变成了,找到一个x,使第一个式子尽量小。使用01trie,假设当前走到u(顶着走)
先要保证\(x>=mid-min\{ a_{i} \}\)

如果有两个儿子:

1.当前mid这位为1,如果我这位填0,那么左子树肯定都小于了,那么就将左子树的\(sum b_{i}\)加上,那后向右子树递归。如果这位填1,那么右子树肯定都小于,那么就将右子树加上,向左子树递归。所以这个子树的最小答案就是
\(min(sumb[son[u][0]]+dfs(son[u][1]),sumb[son[u][1]]+dfs(son[u][0]))\)
2.当前mid这位为0,如果我这位填0,那么右子树肯定都大于了,那么就向左子树递归。如果这位填1,那么左子树肯定都大于,向右子树递归。所以这个子树的最小答案就是
\(min(dfs(son[u][0]),dfs(son[u][1]))\)

如果只有左/右儿子:

1.当前mid这位为1,肯定要让异或起来更大,所以要相反着填,所以最小答案就是\(dfs(son[u][0/1])\)
1.当前mid这位为零,那么如果相反着填,那么就肯定是大于了,返回0即可。

如果没有儿子了:

根据建树代码可知,这是走到底层的情况,因为是顶着走的,那么就返回0即可。
所以我们就进行二分,然后每次跑一边trie树,这颗trie树应该是不变的。
时间复杂度 \(O(nk^{2})\) 期望得分 72 pts
————————————————————————————————————————————————
考虑如何优化。因为这个在trie上跑一遍是不太可能优化的,那么考虑怎么优化二分。考虑优先让高位为1,那么mid这一位就是1,然后跑一遍dfs,看下\(sumb_{i}\)是否小于m,如果小于,那么答案这位就是1,否则就是0。然后我们又得到了一个 \(O(nk^{2})\)算法 期望得分 72 pts。考虑贪心,在子树内,若当前填1,后面全填0,是否有解。
引理:首先我将这位和这位以后的所有位都填成0,那么sumb就是0

如果有两个儿子:

当前mid这位为1,后面都为0,那么如果我x填了1,那么右子树肯定都小于了,然后左子树是顶着的,根据引理,答案是0。所以答案就是sumb[son[u][1]]。如果我x填了0,那么左子树肯定都小于了,然后右子树是顶着的,根据引理,答案是0。所以答案就是sumb[son[u][0]] 然后看两个的min是否小于等于m,如果是,代表可行,m就减掉,这位是1,然后往下递归,否则mid这位就是0,往下递归。

如果只有左/右儿子:

只要反着填,这位mid肯定是1。然后向下递归

如果没有儿子了:

根据建树代码可知,这是走到底层的情况,因为是顶着走的,那么就返回0即可。
然后这题就做完了

标签:左子,右子,那么,这位,魔法,mid,P10218,son,手杖
From: https://www.cnblogs.com/wuhupai/p/18169310

相关文章

  • 【.NET】利用 IL 魔法实现随心随意的泛型约束
    众所周知,C#只支持对基类/接口/class/struct/new()以及一些IDE魔法的约束,比如这样publicstaticstringTest<T>(Tvalue)whereT:ITest{returnvalue.Test();}publicinterfaceITest{stringTest();}但是如果我们想要随心所欲的约束就不行了publicst......
  • vue3在构建时,使用魔法糖语法时defineProps和defineEmits的注意事项
    在Vue3.2+版本中,可以使用<scriptsetup>替代传统的script标签来编写组件,它提供了更简洁的语法来编写CompositionAPI代码。在<scriptsetup>中,使用defineProps和defineEmits时需要注意:如果显式地导入defineProps时,在编译时会提示以下wanning<scriptsteup>impo......
  • 2024年4月6日-UE5-等级、经验、血条、魔法消耗
    在01主角蓝图里,新建2个变量 新增一个类别叫玩家属性,然后把上面的拖进来 然后在角色总类里也新建这个类别,然后把生命值拖进来 这样在01主角里,就都有了在01玩家里再新建几个属性 把玩家等级改成1,魔法值调成默认100,当前经验值0,最大经验值100然后创建一个UI空间蓝图,战......
  • Python程序设计 魔法函数
    1.魔法方法Python中有一些特殊方法,它们允许我们的类和Python更好地集成。在标准库参考(StandardLibraryReference)中,它们被称为魔法方法(MagicMethods),是与Python的其他特性无缝集成的基础。例如,我们用字符串来表示一个对象的值。Object 基类包含了__repr__() 和__str__()......
  • 用JavaScript实现响应式设计的魔法
    在数字世界的迷宫中,响应式设计就像是一把万能钥匙,能打开任何大小屏幕的大门。不论是巨大的桌面显示器,还是袖珍的手机屏幕,响应式设计确保你的网站或应用能在任何设备上都提供优质的用户体验。但如何用JavaScript施展这种魔法呢?让我们一探究竟。使用媒体查询监听器在CSS中,我......
  • C语言链表:链式魔法,数据之美
    导入链表,作为C语言中一种基础且重要的数据结构,以其独特的方式组织和存储数据,成为了解决许多复杂问题的关键。下面,我们将更具体地探讨C语言链表的各个方面。一、链表的基本结构链表由一系列节点组成,每个节点通常包含两部分:数据域和指针域。数据域用于存储实际的数据,而指针域......
  • 掌握C#中异步魔法:同步方法如何优雅调用异步方法
     概述:上述C#示例演示了如何在同步方法中调用异步方法。通过使用`async`和`await`关键字,实现了同步方法对异步方法的调用。建议使用`await`而不是`Result`来避免潜在的死锁问题。这种模式在处理异步任务时能够提高代码的可读性和性能。在C#中,从同步方法调用异步方法的过程涉及......
  • 丁达尔效应在展厅照明设计中为何是魔法般的存在
    在展厅照明设计中,丁达尔效应以其独特的光影魅力,成为了魔法般的存在。它不仅能够创造出层次丰富、氛围独特的照明效果,还能够强化展品的展示效果,提升观众的参观体验。本文将从丁达尔效应的原理、在展厅照明设计中的应用、创造出的魔法般效果以及未来发展趋势等方面,深入探讨丁达尔......
  • 掌握C#中异步魔法:同步方法如何优雅调用异步方法
     概述:上述C#示例演示了如何在同步方法中调用异步方法。通过使用`async`和`await`关键字,实现了同步方法对异步方法的调用。建议使用`await`而不是`Result`来避免潜在的死锁问题。这种模式在处理异步任务时能够提高代码的可读性和性能。在C#中,从同步方法调用异步方法的过程涉及......
  • AI图片换脸技术:科技背后的魔法与伦理挑战
    引言:近年来,随着人工智能(AI)技术的迅猛发展,图片换脸技术作为其中一个引人瞩目的应用,已经成为了公众关注的焦点之一。这项技术利用深度学习和计算机视觉算法,能够将一个人的面部特征迁移到另一个人的脸上,产生逼真的效果。虽然在技术上令人叹为观止,但其背后也存在着诸多深层次的伦......