首页 > 其他分享 >CTS2024 投票游戏

CTS2024 投票游戏

时间:2024-03-10 11:23:32浏览次数:29  
标签:结点 游戏 text 票数 儿子 投票 CTS2024 取值 节点

首先手玩可以发现求出两人谁先被票出是困难的,但如果我们能求出两人各票出时的票数,那么只要比较一下票数的大小就可以直到票出的顺序,然而一个点的票数的大小与其子结点有关,如果我们能确定子结点最终票出时的票数,那么只要处理当且菊花图的一个问题即可,将子节点的最终票数从大到小排序依次与该节点比较即可做到 \(O(nq \log n)\),但不够优秀。

优化这个 \(\text{dp}\) 式子的想法是很直接的,考虑树剖维护动态 \(\text{dp}\),不难发现我们只要维护出子结点们的最终票数的从大到小顺序,令当前节点 \(x\) 的票数为 \(res\),每次如果对于其的一个子结点 \(y\),那么 \(res\leqslant dp_{y}\) 时可以删去 \(y\),并将 \(res\) 减去 \(b_{y}\),可以发现这其实就是一个 \(\text{monster hunter}\) 的模型,每次当其 \(\leqslant\) 一个节点的等级时可以让自己的等级减少,那么实际上按照等级从大到小刚好是最优顺序,所以我们就将其可以看作一个最优化问题。

在修改一个节点时,一个点的更新可能来自于重儿子和轻儿子,对于轻儿子可以维护其平衡树,但对于重儿子由于一整条重链都会影响,所以是不能实时维护出来的。但是我们还是可以采用矩阵乘法维护 \(\text{ddp}\) 的方式,由于重儿子被删与不被删只对应两种取值,所以可以预处理每一种取值之后会到达哪一种取值,这些取值的临界点都可以在轻儿子的平衡树上二分得到,每次修改时动态更新重儿子,自己和父亲的矩阵,父亲的轻儿子平衡树即可,于是可以做到 \(O(n\log^2 n)\)。

标签:结点,游戏,text,票数,儿子,投票,CTS2024,取值,节点
From: https://www.cnblogs.com/zhouhuanyi/p/18063881

相关文章

  • 原神游戏排行榜为什么超越了王者荣耀 ?
    《原神》游戏排行榜超越《王者荣耀》的现象,可能是由多个因素共同作用导致的。以下是一些可能的原因:全球化的影响:《原神》作为一款全球发行的游戏,其受众群体相对更广泛。与此同时,《王者荣耀》虽然在国内拥有庞大的用户基础,但在国际市场的推广和接受度上可能相对有限。因此,从全球范......
  • 8000MHz高频内存也赢不了AMD!锐龙7 7800X3D VS. i9-14900K网游与单机游戏性能对比
    一、前言:i9-14900K配8000MHz内存能否战胜锐龙77800X3D如今的Intel似乎有些魔怔,为了冲击高频而不顾一切。此前i9-14900K的满载功耗已经高达360W,而即将到来的i9-14900KS据闻峰值功耗已经超过400W,频率也来到了前所未有6.2GHz。与之形成强烈反差的是AMD的锐龙77800X3D,这款当前游戏......
  • 王者荣耀游戏需要用到哪些IT技术?
    《王者荣耀》作为一款备受欢迎的多人在线战术竞技游戏(Moba),其背后涉及了众多IT技术的运用。以下是一些关键的技术领域和具体的应用:游戏引擎:游戏引擎是开发游戏的核心工具。对于《王者荣耀》这样的3D游戏,通常会使用如Unity3D这样的游戏引擎。Unity3D提供了丰富的功能和工具,帮助开......
  • C语言0基础入门游戏辅助开发—学习笔记02
    C语言0基础入门游戏辅助开发—学习笔记02PS:这里仅作为本人学习过程中的随笔。数据类型、sizeof运算符数据类型数据类型是在关键字内的,或者说关键字包含数据类型。数据类型有哪些程序中的代码和数据都是以二进制的形式存储的,对计算机系统和硬件而言,数据类型的概念不存在,这......
  • 洛谷P4069 [SDOI2016] 游戏
    题目描述我们要操作的是一条在树上的路径\(s\)->\(t\)。(1)查询\(s\)->\(t\)最大的数字。(2)在\(s\)->\(t\)上增加一个数字,输入\(a\),\(b\),对于路径上的一个点\(u\)增加的数字是\(dis(s,u)\timesa+b\)。解题思路直接查询一条从\(s\)到\(t\)的路径是十分不方便的,所以我们......
  • c语言 推箱子小游戏二次开发
    内容来源:CSDN(额………………):https://blog.csdn.net/m0_71832999/article/details/128050830?ops_request_misc=&request_id=&biz_id=102&utm_term=c++推箱子小游戏&utm_medium=distribute.pc_search_result.none-task-blog-2allsobaiduweb~default-2-128050830.142v99pc_se......
  • 飞机大战小游戏改进与创新
    飞机大战小游戏来源:[https://github.com/WindrunnerMax/AirplaneWar]运行环境:visualstudio2019运行截图如下:对源文件的各项代码,我进行了一些修改和创新,Bomb.cpp文件中,我发现以下问题:魔法数值硬编码:在Draw函数中出现了数字12和10,应该将这些魔法数值定义成常量或者宏以提高......
  • C语言扫雷游戏
    在给出的代码中,使用了以下库来实现游戏功能和图形界面:graphics.h:这是一个基于BGI(BorlandGraphicsInterface)库的图形库,用于创建图形窗口、绘制图形等操作。stdlib.h:这是C标准库中的一个头文件,提供了一些常用函数,例如srand()和rand()用于生成随机数,NULL用于表示空指针。time.h:......
  • 基于蜘蛛纸牌游戏的二次开发
    摘要:蜘蛛纸牌是一款广为人知的单人纸牌游戏,但在实践中发现了一些存在的缺陷。本文将首先介绍蜘蛛纸牌游戏的规则,然后列举其存在的缺陷,最后提出了针对这些缺陷的二次开发解决方案,旨在提升游戏体验。引言蜘蛛纸牌游戏是一种使用两副牌(共104张扑克牌)进行的单人纸牌游戏,其目标是通......
  • C语言-猜拳游戏二次开发
    引言当探究猜拳游戏的魅力时,人们往往会陶醉于其古老的历史和简单的规则之中。作为一种源远流长的竞技娱乐活动,猜拳游戏早已深入人们的生活,成为一种普遍且愉快的社交互动方式。然而,这看似简单的游戏背后却蕴含了深刻的智慧。在短暂的选择过程中,参与者不仅在思考自己的选择,更需要推......