当前位置: 首页 > news >正文

广二联考题解补全计划:


第十七套:
T1:取模性质,倍增
T2: DP优化,状态优化
T3:容斥原理,数位DP

T1:

首先先提一个关于取模的性质,一个数对一个比它小的数取模,大小一定减半,考虑对 $ \frac {n}{2}$ 分治即可。

我们先预处理出来每个数后面第一个比他小的位置,这样形成一个树形结构。

根据前面的性质,有:
\(S_p(x) = \lfloor \dfrac{x}{a_q} \rfloor S_q(a_q-1) + S_q(x \bmod a_q)\),预处理出 \(S_p(a_p-1)\) 就可以做到只处理log次,每次还需要树上倍增找下一个比他小的,那么两只log即可快速查询

T2:
萌熊原题,写一下思考过程:

  1. 因为只关心英雄集合,我们贪心地让所选英雄集合去对抗尽可能小的
    怪兽

  2. 于是 \(n^{3}\) 式子很好想,我们枚举集合大小 $k $ ,那么设计 \(f_{i,j}\) 枚举到第i个英雄,赢了j场,转移就不写了

  3. 优化前途在于枚举状态,我们发现我们 \(k\) 是必须要枚举的,前面设计的状态如果我们要求英雄输就很不好处理,我们考虑前后两端枚举,前面枚举赢的集合,后面枚举输的集合,最后再拼起来

  4. 发现不能直接拼,我们找到这样一个位置 \(a_k < b_p < a_{k+1}\),这样我们发现前面没赢的都能在后面输,后面没输的都能在前面赢。在这个位置拼起来就行了

T3:

UNR好题

之前学容斥有一个式子是 $ x_i \le b_i \ \ \ 求 \sum x_i=m$ 的方案数,那我们容斥做就好了

这个题是小于等于,那我们新加一个盒子,表示在这个盒子里的我们扔掉。

\[Ans=\sum_{S \in \left \{ 1,...m \right \} } (-1)^{|S|} \binom{n+m-(\sum_{i \in S} b^i-c+1)}{m} \]

设 $ A=n+m+k(c-1) $,把后面那一坨拆拆,得到一个下降幂形式,把它看做多项式:

拆一下系数,有

\[g_{0,0}=1,g_{i,j}=g_{i-1,j} \times (A-i+1) - g_{i-1,j-1} \]

下面你要求后面那一坨 \(b^i\) 的和

设计 \(f_{}\)

http://www.hskmm.com/?act=detail&tid=12465

相关文章:

  • Chapter 8 Contour / Shape Detection
  • 【左程云算法笔记016】双端队列-双链表和固定数组实现 - 教程
  • java相关问题:面向对象入门2与类的识别
  • EXCEL自动调整列宽的快捷键
  • 【C++实战⑬】解锁C++文件操作:从基础到实战的进阶之路 - 实践
  • 破解塔吊顶升高危难题!让事故率降 50%、审批快 70%
  • logicFlow________文档2
  • CF2086D Even String
  • logicflow___文档3
  • 2025年运营商API安全建设最佳实践:某头部省级电信案例解析与方案推荐
  • 软件工程第二次作业-第一次个人编程作业
  • 面向对象入门2与类的识别
  • 202508_天山固网_to
  • jmeter分布式压测
  • 怎么屏蔽 ahref.com 上你不想看到的网站链接(垃圾外链)
  • 浅谈字典树
  • go-mapus为局域网地图协作而生
  • 《手搓动态顺序表:从数组到自动扩容的华丽转身》 - 详解
  • 板子大全
  • 通过人大金仓数据库的逻辑备份与还原功能实现数据迁移
  • 第十二节:订单普通下单、支付回调、退款、退款回调详解
  • 《原子习惯》-读书笔记7
  • 第3周预习作业
  • 《原子习惯》-读书笔记6
  • Java LTS版本进化秀:从8到21的欢乐升级之旅
  • 201912_EASER
  • 搜索百科(3):Elasticsearch — 搜索界的“流量明星”
  • 打印机漏洞、匿名协议与AWS安全:一周技术热点解析
  • 从零开始训练推理模型:GRPO+Unsloth改造Qwen实战指南
  • ALLinSSL,开源免费的SSL证书自动化管理平台