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

SP6950 CTOI10D3 - A HUGE TOWER 题解

按照 $ h $ 降序依次放每个积木,此时如果有 \(2\) 块积木,那么一定满足条件。因为 \(h_{\text{now}} - h_{\text{pre}} \leq 0 \leq D\)

继续往下想,再加一块,也要满足 $ h_{\text{next}} - h_{\text{now}} \leq D $。一旦不满足这个条件,后续即使插入更小的积木,也不合法。

每个积木 $ x $ 可以在 $[h_x, h_x + D] $ 的积木中任意选择一个并插入在下方。每次操作基本独立,根据乘法原理,总方案数是每次选法的乘积。

总复杂度 $ O(n \log n) $,瓶颈在于排序。

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 6.2e5 + 5, mod = 1e9 + 9;
int n, D, a[N];
signed main() {ios::sync_with_stdio(false);cin.tie(0);cin >> n >> D;for (int i = 1; i <= n; i++) {cin >> a[i];}a[0] = 1;sort(a + 1, a + 1 + n);for (int i = 2, j = 1; i <= n; i++) {for (; a[i] - a[j] > D; j++);    //用双指针求出每次的选法数量a[0] = a[0] * (i - j + 1) % mod;}cout << a[0];return 0;
}
http://www.hskmm.com/?act=detail&tid=25660

相关文章:

  • 浅谈并查集
  • 16_AiAgentMCP简单教程
  • 17_AiAgentMCP实现技术选型
  • JVM_XMS 和 java_opts哪种写法对?如何在JVM中设置JVM_XMS和java_opts?
  • POLIR-Society-Philosophy-mind: 思想/精神
  • 鸿蒙编译ffmpeg库 - 详解
  • 知道却做不到
  • 题解:loj154 集合划分计数
  • 为什么 Java 中打印Object类型的变量无需强转,而从Object类型的数组中取元素却要强转?
  • WinReanimator恶意软件清除指南:详细步骤与工具使用
  • 251006
  • 2025国庆Day5
  • 字节跳动开源图标库:2000+图标一键换肤的魔法 - 教程
  • 换根DP学习笔记
  • 自动化数据操作平台获3000万美元融资
  • 模块
  • 实用指南:【相机基础知识与物体检测】更新中
  • AtCoder Beginner Contest 422 游记(VP)
  • 详细介绍:无人机光纤FC接口模块技术分析
  • 2025 --【J+S 二十连测】-- 第十三套 总结
  • 文件提供的基本操作
  • 深入解析:MySQL(50)如何使用UNSIGNED属性?
  • 迈向人机价值共生文明:AI元人文范式下的演化架构与协同治理
  • 10.6
  • 文件存储空间管理
  • 详细介绍:关于ios点击分享自动复制到粘贴板的问题
  • 新一代数据平台替代传统大数据技术栈
  • 攻击者如何绕过macOS内置安全防护机制
  • 在A列连续且相等行的最后插入空行,并求和
  • 10.6集训改错