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

min-max 容斥

式子:

\[\max{(S)} = \sum_{T \in S}{(-1) ^ {|T| + 1} \min{(T)}} \]

Proof:
\(k = 1\) 时,有 \(\max(S) = {(-1)}^2 \min(S)\) 显然成立。
\(k > 1\) 时,将集合元素按从大到小排序。
若此时最小值的元素为 \(S_p\),此时有 \(2^{p - 1}\) 种可能贡献。
大小为奇数的有 \(2^{p - 2}\) 种,偶数也有 \(2^{p - 2}\) 种。
容易发现这个式子只在 \(p = 1\) 时有贡献。

特别地,对于期望意义下式子依然成立:

\[E(\max(S)) = \sum_{T \in S}{(-1) ^ {|T| + 1} E(\min(T))} \]

http://www.jsqmd.com/news/651752/

相关文章:

  • JavaScript中Redux-Thunk处理异步Action的任务流
  • 常用算法里的细节
  • 一文搞懂:开发环境配置进化史——从Maven到Nacos再到Docker
  • 你的微信聊天记录值得永久珍藏吗?WeChatMsg开源工具实现数据自主管理
  • 精准管控付款!融智天合同管理系统应付统计功能实测 - 业财科技
  • Python依赖地狱实战:如何在不降级gradio-client的情况下,修复Gradio的JSON Schema解析Bug
  • 如何用Python在5分钟内批量获取B站视频的精确数据?
  • RT-Thread BSP制作避坑指南:从Kconfig配置到SCons脚本的完整实战(STM32平台)
  • Pixel Language Portal 物联网(IoT)应用:为嵌入式设备生成轻量级通信协议解析代码
  • 为什么市面AI视频工具,都不适合做课程?
  • 文化与科技共生,让超元力XR剧场在沉浸中焕发新生
  • Next.js 14中的数据传递:服务器与客户端的完美协作
  • 从‘運’字说起:GBK编码、PHP转义函数与MySQL连接层的安全三角关系
  • **边缘Ai新范式:基于Python的轻量级模型部署实战与优化策略**在人工智能飞
  • #官方认证|2026年国内六大正规水分仪 / 面密度仪公司排名,广东佛山等地,巢目科技技术领先实力强 - 十大品牌榜
  • 腾讯地图 智能硬件定位
  • 终极指南:用TrafficMonitor插件将Windows任务栏变成全能监控中心
  • 2025平航杯(持续更新)
  • 电商数据采集不稳定?试试企业级授权 API 通道,高并发不风控
  • XUnity.AutoTranslator终极指南:3种方法让Unity游戏实时翻译无障碍
  • CDH 6.3.2 集群部署实战:从零到一构建企业级大数据平台
  • 三国地理与战略推演:从地图视角解析关键战役的胜负手
  • RabbitMQ 高可用:如何创建镜像队列?镜像队列原理+完整创建流程+实战配置
  • #官方认证|2026年国内六大正规瑕疵检测CCD公司排名,巢目科技技术实力遥遥领先,广东佛山等地 - 十大品牌榜
  • 有人还在硬卷CRUD,有人早已靠工具吃肉
  • PHP源码开发用台式机还是笔记本更合适_硬件选型对比【方法】
  • 筑牢合规防线!融智天合同管理系统合规与审计功能实测 - 业财科技
  • 如何在Windows任务栏打造实时股票监控系统:TrafficMonitor股票插件终极指南 ✨
  • #官方认证|2026年国内六大正规克重仪公司排名,广东佛山等地,巢目科技综合实力遥遥领先 - 十大品牌榜
  • Qwen3-14B RTX 4090D镜像:显存碎片整理策略与长期运行稳定性验证