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

题目记录(Before NOIP2025 ver)

T1. Beautiful Sequence Unraveling

定义 \(dp_{i,j}\) 表示长度为 \(i\),值域在 \([1,j]\) 之间的好序列的个数。发现好序列不好刻画,所以转化为所有序列的数量减去不是好序列的数量。前者很显然,即 \(i^j\)。接下来考虑后者怎么求。

考虑一个不好的序列 \(a\),假设 \(p\) 为最后一个 \(\max(a_1,a_2 \cdots,a_p) = \min(a_{p+1},a_{p+2},\cdots,a_n)\) 的位置,那么我们有一个重要的观察就是 \(a_{p+1},a_{p+2},\cdots,a_n\) 一定是一个好序列不然 \(p\) 就不是最大的。那么我们可以直接枚举位置 \(p\)\(a_p\) 的值 \(m\) 就可以了:

\[dp_{i,j} = j^i - \sum^{i-1}_{p=1}\sum^j_{m=1}(m^p - (m-1)^p)(dp_{i-p,j-m+1} - dp_{i-p,j-m}) \]

使用前缀和优化后可以做到 \(n^3\)

那么接下来考虑设 \(g_i\) 表示长度为 \(n\) 的序列,值域为 \([1,i]\) 的好排列数量,则我们有递推式:

\[g_i=dp_{n,i} - \sum^{i-1}_{j=1}\dbinom{i}{j}g_j \]

那么答案就是 \(\sum^n_{i=1} \dbinom{k}{i}g_i\)

T2. Lockout vs tourist

太牛了!

看到 \(n \le 22\),考虑使用状压 dp。此时设 \(m = |S|\),其中第 \(i\) 题的分数为 \(a_i\)\(S\) 去掉 \(i\) 后的期望最大的分为 \(b_i\),Tourist 有 \(p_i\) 的概率选择第 \(i\) 题,那么期望最大的分就是:

\[\max(p_i \times b_i + (1 - p_i) \times a_i) \]

考虑去二分答案 \(C\),那么我们现在就是需要找到一个 \(p\) 使得所有的 \(a_i + (b_i - a_i)p_i = C\)\(\sum p_i = n\)。那么此时考虑定义 \(d_i = \frac{C - a_i}{b_i - a_i}\),那么如果 \(b_i > a_i\) 则有 \(p_i \le d_i\) 否则 \(p_i \ge d_i\)。由于至少存在一个 \(b_i < a_i\),那么我们可以将判断条件改写为 \(\sum_{b_i < a_i}\max(0,d_i) \le 1\)\(\forall i(b_i \ge a_i),C \ge a_i\)

其实条件 \(2\) 只是给 \(C\) 定了一个下界,我们还是考虑条件 \(1\):我们注意到由于 \(b_i < a_i\),所以当 \(d_i > 0\) 的时候,\(C < a_i\),所以在这里我们只需要考虑所有大于 \(C\)\(a_i\)。这也告诉了我们 \(\sum \max(0,d_i)\) 其实是一个关于 \(C\) 的分段一次函数。那么我们其实可以直接去掉二分,直接在分段后在每一段上求一个最值就可以了,复杂度为 \(\mathrm O(n2^n)\)

T3. 巴蜀中学 NOIP 模拟赛 旋转

你发现有一些点是必须删的,比如 \((x_i,y_i)\)。那么我们定义一个格子 \((x,y)\) 是可选择的当且仅当 \((x,y)\) 是一个合法格子且 \((x,y)\) 不是必须删的。

考虑一次对于 \((x,y)\) 的操作,检查 \((x,y)\) 的左右两边的格子:

  • 两个格子都是可选的,则在两个格子间连一条无向边。
  • 恰一个格子是可选择的,在这个格子上连一个自环。
  • 否则无解。

现在考虑给无向边定向,代表指向的格子被这次操作选择。那么我们的任务就是所有格子的入度均不超过 \(1\) 的方案数,然后对于每一个连通块大力分讨即可。

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

相关文章:

  • 专业修复sqlserver master 数据库损坏。
  • jenkins job的configure中配置git时 选择的credential为什么不能选择secret认证方式的数据
  • Day21继承
  • C# Avalonia 15- Animation- ImageWipe
  • 题解:P8067 [BalkanOI 2012] balls
  • 题解:P8300 [COCI 2012/2013 #2] INSPEKTOR
  • SuperHarness-3D低压柜机电协同设计方案!
  • 详细介绍:.NET驾驭Word之力:打造专业文档 - 页面设置与打印控制完全指南
  • 使用.NET标准库实现多任务并行处理的详细过程 - 实践
  • 模型训练中 平均损失值和平均准确率的深入理解
  • torch.max函数在分类问题中的使用 学习
  • godot3.6字典遍历
  • 国产DevOps工具链崛起:Gitee领衔的本土化技术生态全景解读
  • 安装 elasticsearch-9.1.4的 IK分词器
  • react性能优化
  • 从研发效能到知识中枢:Gitee Wiki如何重塑企业知识管理范式
  • Gitee DevSecOps平台:军工软件研发的智能化革命
  • 杆状病毒表达系统为何成为蛋白表达首选
  • 日记3
  • Gitee如何重塑中国开发者的代码托管体验
  • 模块化面向对象 2章
  • css `isolation: isolate` - 详解
  • Debezium + Kafka + Flink/Doris Stream Load 实时数仓
  • Gitee DevOps平台:中国企业数字化转型的代码管理新范式
  • Ansible + Docker 部署 Zookeeper 集群
  • 幂运算与航班中转的奇妙旅行:探索算法世界的两极 - 实践
  • Gemini CLI 配置问题
  • 本土化与全球化博弈下的项目管理工具选型:Gitee如何为中国企业破局?
  • 论Linux安装后需要进行的配置
  • 51单片机-驱动DS1302时钟芯片模块教程 - 实践