【题解】P11830 [省选联考 2025] 幸运数字-北京尧图网络

P11830 [省选联考 2025] 幸运数字 - 洛谷 (luogu.com.cn)看到中位数就应该想到分为小于中位数、等于中位数和大于中位数。题目中中位数的位置显然和这三种数值的数量有关系设它们的数量分别为。设当前数值为我们强制让成为中位数应该满足1如果的话中位数将大于。2如果的话中位数将小于。我们该如何想到这些条件反推中位数不等于的情况即可前半部分过多中位数变小后半部分过多中位数变大那么对于我们就有同时可以选中位数的尽量多选。也就是让变大这样一定会让该中位数被选择的概率增大。我们发现每个值的可以差分处理也就是对于值区间为的值。我们统一让它们的贡献加上对应前文中的要尽量大。对于当前值区间作为我们则在上差分因为用到这个就代表着一定比大。对于当前值区间作为我们则在上差分因为用到这个就代表着一定比小。#includebits/stdc.h using namespace std; typedef long long LL; const int N 2e5 10; const int M 2 * N; int n, ln, cf, ans; // ln:离散化后点数, cf:当前覆盖 x 的区间数 int l1[N], r1[N], l2[N], r2[N]; // 输入的四元组 int dc[M]; // 离散化坐标所有 l2 和 r21 LL sumb, mna, mxa, mnc, mxc, sumf; // 当前扫描到的累计值 LL bs[M], al[M], ar[M], cl[M], cr[M], f[M]; // 差分数组 // bs: 等于 x // al: amin // ar: amax // cl: cmin // cr: cmax // f: 覆盖x的区间数量的差分 (用于判断是否有区间包含x) void solve() { cin n; for (int i 1; i ln; i ) { bs[i] al[i] ar[i] cl[i] cr[i] f[i] 0; } ln sumb mna mxa mnc mxc sumf ans 0; for (int i 1; i n; i ) { cin l1[i] r1[i] l2[i] r2[i]; dc[ ln] l2[i]; dc[ ln] r2[i] 1; // 我们将全闭区间变为左闭右开区间方便计算差分 } sort(dc 1, dc 1 ln); ln unique(dc 1, dc 1 ln) - dc - 1; // 构建差分数组每个区间对四个量产生影响 for (int i 1; i n; i ) { // 这里的 x 和 y 对应着当前区间可选的最小值和最大值 int x lower_bound(dc 1, dc 1 ln, l2[i]) - dc; // 左端点位置 int y lower_bound(dc 1, dc 1 ln, r2[i] 1) - dc; // 右端点 1 位置 // 等于当前值的区间贡献在 [l2, r2] 内增加 r1 bs[x] r1[i]; bs[y] - r1[i]; // 当前值区间作为别人的 a al[y] l1[i]; // 当别人的 amin取最少的数量 ar[y] r1[i]; // 当别人的 amax取最多的数量 // 当前值区间作为别人的 c cl[1] l1[i]; // 当别人的 cmin取最少的数量 cl[x] - l1[i]; // 只有比 x 小的才能选为 c cr[1] r1[i]; // 当别人的 cmax取最多的数量 cr[x] - r1[i]; // 只有比 x 小的才能选为 c // 覆盖当前值的区间数量计数 f[x] ; f[y] --; } for (int i 1; i ln; i ) { // 累计当前点的值 sumb bs[i]; // 等于 x 的个数总和 mna al[i]; // 小于 x 的最小可能个数 mxa ar[i]; // 小于 x 的最大可能个数 mnc cl[i]; // 大于 x 的最小可能个数 mxc cr[i]; // 大于 x 的最大可能个数 sumf f[i]; // 覆盖 x 的区间数量 // 必须有区间覆盖 x否则 x 不会出现在集合中 if (sumf 0) continue; LL lef max(mna - sumb 1, mnc); LL rig min(mxa sumb, mxc); if (lef rig) { // 这段区间内所有整数点都满足条件加入长度 ans dc[i 1] - dc[i]; } } cout ans \n; } int main () { ios::sync_with_stdio(false); cin.tie(0); int c, T; cin c T; while(T --) { solve(); } return 0; }

【题解】P11830 [省选联考 2025] 幸运数字

相关推荐

AI力场二次开发教程（03）：第一个AI力场分子——SMILES 到 OpenMM System 全流程

【C++ 入门】类与对象：class 定义、类域、实例化与 this 指针

Anthropic估值2万亿美元是如何推演的？AI大模型估值框架与Python模拟

更多资讯

用Cloudflare Workers构建云桌面：cloudflare-os架构与实现解析

MATLAB集成量子计算BQP后端的工程实践指南

MATLAB量子模块实战：BQP算法工程化集成与工作流改造

从通用Agent到专用Skills：AI开发范式转变与实践

量化交易中加密API的痛点与高频数据解决方案

Java老人健康管理系统：架构设计与技术实现

今日更新

微信个人号API开发案例：图片/语音/视频消息怎么下载解析存到本地？

Python股票自动交易系统源码解析：从行情获取到风控的完整链路

视酷酷信IM源码部署指南：Java 17+MySQL 8.0.33实战配置

本周精选

防幻觉智能体架构：电源硬件设计中的大模型编排与工具化实践

OpenGL面试核心考点：渲染管线、矩阵变换与性能排查全解析

全国计算机二级C语言真题PDF高效刷题指南

本月热门

我发现了一个新思路：用 Remotion + Claude Code 像写代码一样自动化生成短视频

Windows下 Codex 中 Chrome 和 Computer Use 插件不可用问题排查及解决参考方式：TaoToken 统一 Key 配置与验证

2026 大模型集体涨价：用 Python 做企业 Token 成本测算与选型避坑（附配置）

读完文章，想聊聊您的网站？